Consider the transition diagram of a PDA given below with input alphabet \(Σ =…

GATE · 2016 · CS · Set 1 · Computer Science & IT

Consider the transition diagram of a PDA given below with input alphabet Σ={a,b}Σ = \{a,b\} and stack alphabet Γ={X,Z}Γ = \{X,Z\}. ZZ is the initial stack symbol. Let LL denote the language accepted by the PDA.

Which one of the following is TRUE?

  1. A.

    L={anbn∣n≥0}L =\{a^nb^n\mid n \geq0 \} and is not accepted by any finite automata

  2. B.

    L={an∣n≥0}∪{anbn∣n≥0}L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\} and is not accepted by any deterministic PDA

  3. C.

    LL is not accepted by any Turing machine that halts on every input

  4. D.

    L={an∣n≥0}∪{anbn∣n≥0}L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\} and is deterministic context-free

Attempted by 156 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…