1

24kviews

Construct a CFG to over {a,b} to accept a set of all palindromes

**1 Answer**

1

24kviews

Construct a CFG to over {a,b} to accept a set of all palindromes

1

2.6kviews

written 4.8 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

ADD COMMENT
EDIT

Please log in to add an answer.