Let M = ({q0, q1}, {0, 1}, {z0, X}, δ, q0, z0, ∅) be a pushdown automaton…

PYQ GATE 1998

Let M = ({q0, q1}, {0, 1}, {z0, X}, δ, q0, z0, ∅) be a pushdown automaton where δ is given by

δ(q0, 1, z0) = {(q0, Xz0)}

δ(q0, ε, z0) = {(q0, ε)}

δ(q0, 1, X) = {(q0, XX)}

δ(q1, 1, X) = {(q1, ε)}

δ(q0, 0, X) = {(q1, X)}

δ(q0, 0, z0) = {(q0, z0)}

(a) What is the language accepted by this PDA by empty stack?

(b) Describe informally the working of the PDA.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…