peter linz chapter 5 ex 5.1 q#19

Question

S->AB | €,

A->aB,

B->Sb.

Give a verbal description of the language generated by this grammar.

Comments

$L=\left \{ a^{n}b^{2n} :n\geq 0 \right \}$

Answer 1

Given grammar :

         S  -->  A B  |  ϵ                                                                                                                                                                      A  -->  a B                                                                                                                                                                            B  -->  S b

Substituting B in A production and in S production ,we have :

         S  -->  aSbSb  |  ϵ                                                                                                                                                              

which is the production of our interest as far as generation of strings is concerned as A does not produce any strings on its own as there is no terminating production in A..

So considering  :      S  -->  aSbSb  |  ϵ    

After epsilon , minimal string generated   :   abb

Now we have 2 S's in the RHS of production , so we can substitute any of the 2 S's with epsilon or abb..So say first S is substituted with epsilon and second one with "abb" , we get the string generated : ababbb

If we do substitution other way , we get :  aabbbb

So we can see that it need not be the case that all a's followed by b's which is twice the number of a's..But this is for sure that the number of b's is twice the number of a's..

Bt in that also strings like : abbbba  , abbabb etc are not covered ..

Hence the description of the language that L = {aⁿ b²ⁿ | n >= 0} or L = {strings belonging to Σ* | number of b's = twice the number of a's}  is not true..

All we can say is the language being generated is a proper subset of  L = {strings belonging to Σ* such that number of b's = twice the number of a's} . 

Comments

But this wont be a regular language @stblue bro as there is relation between number of a's and no of b's..

Answer 2

This grammar can be simplified as:

S→aBB|λ

B→Sb

or even more simply, as

S→aSbSb|λ

This grammar produces the strings of the form $a^{n}b^{2n}$ , n ≥ 0,

i.e., it generates the language L(G) = {$a^{n}b^{2n}$ : n ≥ 0}

Using the simplified version, we can see that we always generate twice as many b’s as a’s.But it is in a limited form.

Each a has two matching b’s to its right.

Simply stated it is the set of strings over a and b such that each a has two matching b’s to its right.

Comments

But the string ababbb is also derivable from this grammar

---

yes the string ababbb is also derivable from this grammar as for one 'a' , two 'b' are required and the given string has 2a and 4b.

The given Language generated from the grammer L(G)={ $a^{n}b^{2n}$ : n>=0 } means for 1 'a' , 2 'bs' are required and for 2 'a' , 4 'bs' are required and so on.

---

This is not correct language, it misses certain strings, which is present in language, but your language is not generating.
@joshi_nitish @just_bhawna @Habibkhan @shubanshu @manu00x please have a look at this question.

---

what i think it is generating something like,

balanced paranthesis(a denotes '(' and b denotes ')') followed by b as many times as a valid paranthesization combination is present..

for eg:

()())) ---> ababbb, here 2 valid parenthasization is there followed by 2 b's

()) ---> abb, here 1 valid parenthasization is there followed by 1 b.

(()))) ---> aabbbb, here 2 valid parenthasization is there followed by 2 b's.

())()) ---> abbabb , this string is not in language because above rule can't be applied on it..

though i think this is correct, but once check it.