0
4.6kviews
Design a PDA corresponding to the grammar $S =>aSa|bSb|\epsilon$
1 Answer
written 6.9 years ago by | • modified 6.9 years ago |
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‟
$δ(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)$