1

14kviews

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

written 3.6 years ago by | • modified 3.6 years ago |

**Mumbai University > Informatica Technology > Sem 4 > Automata Theory**

**Marks: 10M**

ADD COMMENT

**1 Answer**

1

14kviews

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

written 3.6 years ago by | • modified 3.6 years ago |

**Mumbai University > Informatica Technology > Sem 4 > Automata Theory**

**Marks: 10M**

ADD COMMENT

1

281views

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

Please log in to add an answer.