The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
90 views
S->AB | €,

A->aB,

B->Sb.

Give a verbal description of the language generated by this grammar.
asked in Theory of Computation by (51 points) | 90 views
$L=\left \{ a^{n}b^{2n} :n\geq 0 \right \}$

2 Answers

+3 votes
Best answer

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 = {an b2n | 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} . 

answered by Veteran (96.7k points)
selected by
But this wont be a regular language @stblue bro as there is relation between number of a's and no of b's..
+1 vote
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.
answered by Boss (5.5k points)
edited by
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.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,157 questions
36,984 answers
92,154 comments
34,823 users