Home Automata NPDA for accepting the language L = {am bn cp dq | m+n=p+q ; m,n,p,q>=1}

NPDA for accepting the language L = {am bn cp dq | m+n=p+q ; m,n,p,q>=1}

NPDA for accepting the language L = {am b(2m) | m>=1}

Construct Pushdown automata for L = {0n1m2m3n | m,n ≥ 0}

Pushdown automata

Pushdown automata acceptance by final state

Problem –

L = {abcd, abbcdd, abbccd, abbbccdd, ......}

Explanation –

 = { 1, z }

Approach used in the construction of PDA –

Stack transition functions –

(q0, a, z)  (q0, 1z)
(q0, a, 1)  (q0, 11)
(q0, b, 1)  (q1, 11)
(q1, b, 1)  (q1, 11)
(q1, c, 1)  (q2, )
(q2, c, 1)  (q2, )
(q2, d, 1)  (q3, )
(q3, d, 1)  (q3, )
(q3, , z)  (qf, z)

Tags:

#GATE CS #Theory of Computation

NPDA for accepting the language L = {am b(2m) | m>=1}

Construct Pushdown automata for L = {0n1m2m3n | m,n ≥ 0}

NPDA for accepting the language L = {am bn cp dq | m+n=p+q ; m,n,p,q>=1}

Contact Us