Select all the grammars below which correctly generate the language: L = {a^n ww

Question

Select all the grammars below which correctly generate the language: L = {a^n ww^R c^n + 2 bb:w elementof {a, b}*, n greaterthanorequalto 0} Assume that the start variable is S. {S rightarrow Accbb A rightarrow aAc|B B rightarrow bBb|aBa|lambda {S rightarrow Abb A rightarrow aACC|B B rightarrow aBa|bBb|lambda {S rightarrow Abb A rightarrow aAc|Bcc B rightarrow aBa|bBb|lambda {S rightarrow Accbb A rightarrow aAc|bAb|aAa|lambda {S rightarrow aSc|A A rightarrow Bccbb B rightarrow aBa|bBb|lambda {S rightarrow Acbb A rightarrow aAc|Bc B rightarrow aBa|bBb|lambda

Explanation / Answer

A)

S->Accbb

A->aAc|B

B->aba|bBb|

Langauage generated by gramer:

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAc|B {aBc,aaBcc,aaaBccc……}->anBcn->{an wwr cn    n>0}

S->Accbb generates

when A=B= then s=ccbb it is in the form an wwr cn+2 bb and n=0 other wise

S->an wwr cn cc bb

->an wwr cn+2 bb    where n>=0

So this is Answer

B)

S->Abb

A->aAcc|B

B->aba|bBb|

Langauage generated by gramer:

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAcc|B generates grammer {aBcc,aaBcccc,aaaBcccccc,……….}

    =>anwwrc2n where n>1

S->Abb generates anwwrc2nbb where n>=0

it is not an answer

C)

S->Abb

A->aAc|Bcc

B->aba|bBb|

Langauage generated by gramer:

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAc|Bcc generates garmer like {aBccc,aaBcccc,aaaBccccc,……………..}

   ={anwwrcn+2 where n>1}

S->Abb generates grammer anwwrcn+2bb where n>1

SO it is not required grammar

D)
S->Accbb

A->aAc|bAb|aAa|

Let

A->aAc|bAb|aAa|

Can be written as

A->aAc|B

B->bBb|aBa|

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAc|B generate { , aBc, aaBcc,aaaBccc………} => {anwwrcn where n>1}

So A->aAc|bAb|aAa| generates => {anwwrcn where n>=0}

S->Accbb genearates { anwwrcn+2 bb where n>=0}

So it is a answer

E)
S->aSc|A

A->Bccbb

B->bBb|aBa|

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

Let

s-> a S c

   ->aAc                (A->Bccbb)

   -> aBccbbc        (B-> )

   ->Accbbc

Accbbc is not in the given grammar because each string in required grammar ended with bb

F)
S->Acbb

A->aAc|Bc

B->bBb|aBa|

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAc|Bc        {c,aBcc,aaBccc,aaaBcccc……….}=>{ an wwrcn+1where n>=0}

S->Acbb generates grammar

an wwrcn+1cbb where n>=0

an wwrcn+2bb where n>=0

So it is also an answer                              

Answers: A,D,F

A)

S->Accbb

A->aAc|B

B->aba|bBb|

Langauage generated by gramer:

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAc|B {aBc,aaBcc,aaaBccc……}->anBcn->{an wwr cn    n>0}

S->Accbb generates

when A=B= then s=ccbb it is in the form an wwr cn+2 bb and n=0 other wise

S->an wwr cn cc bb

->an wwr cn+2 bb    where n>=0

So this is Answer

B)

S->Abb

A->aAcc|B

B->aba|bBb|

Langauage generated by gramer:

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAcc|B generates grammer {aBcc,aaBcccc,aaaBcccccc,……….}

    =>anwwrc2n where n>1

S->Abb generates anwwrc2nbb where n>=0

it is not an answer

C)

S->Abb

A->aAc|Bcc

B->aba|bBb|

Langauage generated by gramer:

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAc|Bcc generates garmer like {aBccc,aaBcccc,aaaBccccc,……………..}

   ={anwwrcn+2 where n>1}

S->Abb generates grammer anwwrcn+2bb where n>1

SO it is not required grammar

D)
S->Accbb

A->aAc|bAb|aAa|

Let

A->aAc|bAb|aAa|

Can be written as

A->aAc|B

B->bBb|aBa|

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAc|B generate { , aBc, aaBcc,aaaBccc………} => {anwwrcn where n>1}

So A->aAc|bAb|aAa| generates => {anwwrcn where n>=0}

S->Accbb genearates { anwwrcn+2 bb where n>=0}

So it is a answer

E)
S->aSc|A

A->Bccbb

B->bBb|aBa|

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

Let

s-> a S c

   ->aAc                (A->Bccbb)

   -> aBccbbc        (B-> )

   ->Accbbc

Accbbc is not in the given grammar because each string in required grammar ended with bb

F)
S->Acbb

A->aAc|Bc

B->bBb|aBa|

B->aBa|bBb| generate { ,aa,bb,aabb,abba,baba,….} ==>{ wwr | w {a+b}* }

A->aAc|Bc        {c,aBcc,aaBccc,aaaBcccc……….}=>{ an wwrcn+1where n>=0}

S->Acbb generates grammar

an wwrcn+1cbb where n>=0

an wwrcn+2bb where n>=0

So it is also an answer                              

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.