The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

+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 = {a^{n} b^{2n} | 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} . **

+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.

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.

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.

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.

@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:

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

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

**(())**)) ---> **aabb**bb, 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.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 398
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,715 questions

40,263 answers

114,377 comments

38,899 users