1
40kviews
Construct a CFG to over {a,b} to accept a set of all palindromes
1 Answer
2
5.2kviews

Sample strings for palindromes:

abba

baab

bbbb

aaaa

So, our CFG has to provide a looping condition such that the palindrome is constructed

S =>abSBA|baSAB|ε

A =>a

B =>b

We break this grammar even more to simplify it further

We can do so by having more non-terminals involved in the grammar

Final CFG is

S =>DSE|ESD|FSF|GSG| ε

D =>AB

F =>AA

E =>BA

G =>BB

A =>a

B =>b

Please log in to add an answer.