engineering recuitment GATE CSE 2023-24 Test Series Theory of Computation Regular Languages and Finite Automata Finite Automata
Consider the transition diagram of a PDA given below with input alphabet Σ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.
Which one of the following is TRUE?
1
L = {anbn|n ≥ 0} and is not accepted by any finite automata
2
L = {an|n ≥ 0} ∪ {anbn|n ≥ 0} and is not accepted by any deterministic PDA
3
L is not accepted by any Turing machine that halts on every input
4
L = {an|n ≥ 0} ∪ {anbn|n ≥ 0} and is deterministic context – free