1
40kviews
Construct a CFG to over {a,b} to accept a set of all palindromes
1 Answer
written 6.9 years ago by |
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