Give CFG for the following languages, a n b m where m = n-1 and n = 1,2,3… Some

Question

Give CFG for the following languages,
anbm where m = n-1 and n = 1,2,3…
Some words belonging to this language are, a , aab , aaabb , aaaabbb , ….
anb2n where n = 1,2,3…
Some words belonging to this language are, abb , aabbbb , aaabbbbbb , ….

Explanation / Answer

a) S -> aT T -> aTb | e where S is the start symbol, e is the null string Basically, we start with the symbol S and use the transition rules stated above to generate the strings of the grammar. So, for example, say we need to generate aaabb. This is how that proceeds: S -> aT -> aaTb (using T -> aTb) -> aaaTbb (using T -> aTb) -> aaabb (using T -> e) b) S -> aSbb | e where S is the start symbol, e is the null string So, for example, say we need to generate aabbbb. This is how that proceeds: S -> aSbb -> aaSbbbb (using S -> aSbb) -> aabbbb (using S -> e)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.