GATE Papers >> CSE >> 2016 >> Question No 53

Consider the transition diagram of a PDA given below with input alphabet $\Sigma = \{a,b\}$ and stack alphabet $\mathrm{\Gamma } =\{X,Z\}$ .Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

• (A)  $L =\left\{a^n{b}^n\right|n\ge 0\}$ and is not accepted by any finite automata    
• (B)  $L =\left\{a^n\right|n\ge 0\}\cup \{a^n{b}^n|n\ge 0\}$ and is not accepted by any deterministic PDA   
• (C)  $L$ is not accepted by any Turing machine that halts on every input   
• (D)  $L =\left\{a^n\right|n\ge 0\}\cup \{a^n{b}^n|n\ge 0\}$ and is deterministic context-free