List of Top Theory of Computation Questions on Pushdown Automata - Teaching

A pushdown automaton behaves like a Turing machine when the number of total memory is:

What language is accepted by the pushdown automation

M = ({q ₀, q ₁, q2}, {a, b}, {a, b, z}, δ, q ₀, z, {q ₂})

with δ(q ₀, a, a) = {(q ₀, aa)}; δ(q ₀, b, a) = {(q ₀, ba)}

δ(q ₀, a, b) = {(q ₀, ab)}; δ(q ₀, b, b) = {(q ₀, bb)}

δ(q ₀, a, z) = {(q ₀, az)}; δ(q ₀, b, z) = {(q ₀, bz)}

δ(q ₀, λ, b) = {(q ₁, b)}; δ(q ₀, λ, a) = {(q ₁, a)}

δ(q ₁, a, a) = {(q ₁, λ)}; δ(q ₁, b, b) = {(q ₁, λ)}

δ(q ₁, λ, z) = {(q ₂, z)}?

Consider the grammer S → SbS | a.

Consider the following statements:

The string abababa has

(A) two parse trees

(B) two left most derivations

(C) two right most derivations

Which of the following is correct?

Consider the following NPDA = ({q 0, q 1, q f}, {a, b}, {1, z}, δ, q 0, z, {q f})

δ(q 0, λ, z) = {(q f, z)}

δ(q 0, a, z) = {(q 1, 11z)}

δ(q 1, a, 1) = {(q 1, 111)}

δ(q 1, b, 1) = {(q 1, λ)}

δ(q 1, λ, z) = {(q f, z}

Which of the following Language L is accepted by NPDA?