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

https://www.tutorialspoint.com/automata_theory/pushdown_automata_acceptance.htm

---

Many people considering this as not DPDA since we need non determinism for every a either to push X(a symbol) or don't push..

But this quest don't work like that.. even the string is a* just push X for every a  if there is b's then they should be equal  i.e; #a's = #b's..

so for a's we push X and for b's we pop X and push state and the last state we make final..

so it is clearly a DPDA

....

For suppose if we have L2 = {a^n b^n } U {a^n b^2n}

in this we either want to push one X for a  OR 2X for a

if we push 2X for each and every a.. we may not get valid strings only..

so here non determinism should be used

so this L2 is NOT DPDA but PDA

but L1 push X no matter what .. and decide if b exist.. so this is DPDA

---

Option D is correct answer

Answer 1

Strings accepted at $I^{st}$ final state are $a^n\; ,\;n\geq0$ and strings accepted at $II^{nd}$ final state are $a^nb^n\;,\;n\geq 0$ (actually $n\geq 1$ at this state, $n=0$ already included at first state).

$L=\{a^n\;|\;n\geq 0\} \cup \{a^nb^n\;|\;n\geq0\}$
Language is deterministic context-free  accepted by DPDA (dpda is already given) and so by TM too, and not regular (as we need stack to implement it), and so cannot accepted by FA

Correct Answer: $D$

Comments

@sharadkurdekar6 Epsilon move won't make it non determinism, the epsilon,Z  move is not conflicting with any other outgoing move from q1, the other move is b,X clearly here  both moves epsilon,Z and b,X won't conflict since for one of them TOS = Z and for other TOS = X .. so there is no non det here, this is determinism only

 

---

What if initial state was not final/accepting state then we would've L as a^nb^n where n>0 right ?

---

@Rohit Pol yes,

Answer 2

Ya it should be D option. As 1st state is also the final state

Comments

it accpepts aⁿbⁿ also.. and is deterministic too as can be seen from the diagram

Answer 3

As we know Acceptence of given string by PDA in two ways Either by

1. Acceptance by final state: ( If you are scanning the input, and at the end of string machine enters to one of the final state then string is accepted.)

2. Acceptance by Empty Stack: In this case we don't bother, machine enter into final state or not, if at end of string stack is empty then we can say string is accepted.

Option D is correct:  

Bcz in option D, if u take L= a^n, a is pushed into the stack  and it remains in first state only, which is marked as Final state so this string is accepted by PDA (Acceptence by final state)

  L= a^n b^n, as we know this string is accepted by given PDA as shown in given figure, this is also acceptence by final state). This language is not accepted by FA.

Regarding deterministic, in both the case we are deterministic to push a in to stack. So this is accepted by DPDA. so option D

Answer 4

the first state is accepting all strings of type aⁿ for n>0

and if a b comes it will make a transition to second state and it will reach empty stack only when all the a's are popped out of stack so it is accepting a^n.bⁿ   and  the given pda is dpda.

option d

Answer 5

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

Answer 6

Answer should be D.