0
4.6kviews
Design a PDA corresponding to the grammar $S =>aSa|bSb|\epsilon$
1 Answer
0
542views

This grammar can be used to generate strings such as :

S =>aSa

S =>abSba (as S =>bSb)

S =>abba ($as S =\gt\epsilon)$

So the strings that are found have the same number of a‟s as that of b‟s

So, the PDA should perform push operation on encountering „a‟, and pop operation on encountering „b‟

enter image description here

$δ(q_0,a,z_0) =(q_0,az_0)$

$δ(q_0,a,a) =(q_0,aa)$

$δ(q_0,b,a) =(q_1,\epsilon)$

$δ(q_0,\epsilon, z_0) =(q_f,\epsilon)$

Please log in to add an answer.