Question: Design PDA for odd length palindrome, let $\sum$ = { 0,1 }, L = { W x $W^R$ where W $\epsilon$ ${\sum}^*$ }
0

Mumbai University > Information Technology > Sem 4 > Automata Theory

Marks: 10M

automata theory • 359 views
 modified 4 months ago by RB ♦♦ 110 written 7 months ago by
0

PDA for $W \times W^R$

$\delta (q_0, qz_0) = (q_0, qz_0), (q, qz_0)$

$\delta (q_0, b, z_0) = (q_0, bz_0) (q, z_0)$

$\delta (q_0, a,a) = (q_0, b), (q_1, a)$

$\delta(q_0, b,b) = (q_0, b, b), (q_1, b)$

$\delta (q_0, a, b) = (q_0, b) (q, b)$

$\delta (q_0, ba) = (q_0, b_a) (q, b,a)$

$\delta [( q, a, a ), = (q, \epsilon)$

$\delta [( q, b, b ), = (q, \epsilon)$

$(q, \epsilon, z_0) = (q_z, z_0)$