Consider the CFG S bS aa Prove that this generates the lan

Consider the CFG
S -> bS | aa
Prove that this generates the language defined by the regular expression: b*aa

Solution

regular expression: b*aa will generates string like: aa,baa,bbaa,bbbaa,bbbbaa..etc

And,

the CFG
S -> bS | aa

generats the same strings:

For string \'aa\'

S -> aa

For string \'baa\'

S-> bS by replacing S->aa

->baa

Similarly for sring \'bbaa\'

S-> bS by replacing S->bS

->bbS by replacing S->aa

->bbaa

Hence,

We can say that all the strings generated by regular expression : b*aa

will also generated by the CFG : S -> bS | aa