GATE CSE 2016 Set 1 | Question: 43

Question

Consider the transition diagram of a PDA given below with input alphabet $\Sigma=\{a,b\}$ and stack alphabet $\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 =\{a^nb^n\mid n \geq0 \}$ and is not accepted by any finite automata 
• B. $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 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 =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic context-free

Comments

same concept based

https://gateoverflow.in/2765/gate1996-13

 

---

@once_2019 when we say that a language is closed under some property, we guarantee that it will be closed in any case. But when we say that it is not closed, we say that it may not be closed. So the union of two DCFL is not closed means it may or may not be DFCL depending upon the language.

---

@once_2019 If you see first part of union then it is regular language &  union of DCFL with regular is DCFL.

Answer 1

Ans is d because a^n b^n can't be accepted by finite automata

Answer 2

Answer should be D.