Q95 — Theory of Computation

Theory of Computation

Q95. Marks: +2.0 UGC NET Paper 2: Computer Science 26th Nov 2021

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)}?

1.L = {w | n_a(w) = n_b(w), w Є {a, b}⁺}}

2.L = {w | n_a(w) <= n_b(w), w Є {a, b}⁺}}

3.L = {w | n_b(w) <= n_a(w), w Є {a, b}⁺}}

4.L = {ww^R | w Є {a, b}⁺} ✓ Correct

← Previous 8 / 8 in this subject • Back to paper Next →

🏷 Change Tag for this Question ▶