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

Mumbai University > Informatica Technology > Sem 4 > Automata Theory

Marks: 10M

1 Answer
1
281views

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.

Continue reading...

The best way to discover useful content is by searching it.

Search