Context free grammar language Consider the language anb2n 1

Context free grammar language

Consider the language {a^nb^2n + 1 | n greaterthanorequalto 0}, that is, the set L of all words made of a number n of a\'s followed by 2n + 1 b\'s. Examples of words in L are: b, abbb, aabbbbb, aaabbbbbbb, ... Write a set of production rules with start symbol S for the language L. Argue informally but convincingly that every word generated by your rules is in L. Argue informally but convincingly that every word in L is generated by your rules.

Solution

(a)

Let us build Context free grammar or production rules for above given grammar rule.

Start with S and proceed to next a\'s and b\'s production.
Capital letters will be non-terminal and small letters are terminal symbols.

S -> Ab | be
A -> aAbb | ab | e

------------------------------------------------------------------------------------------------------------------------------------------------------------------

(b)

Condier this language which is generated above.
S -> Ab | be
A -> aAbb | ab | e

Consider one level grammar...
S -> b (valid)

Now for two step... n = 1

S-> Ab
S -> aaAbbb
S -> aabbb (valid)

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

(c)

consider grammar
aabbbbb

==> aAbbb
==> Ab
==> S
we reproduce the grammar with above gramamr. Hence our grammar is valid.