edited by
16,707 views
48 votes
48 votes

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

  1. $L =\{a^nb^n\mid n \geq0 \}$ and is not accepted by any finite automata 
  2. $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 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 =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic context-free
edited by

6 Answers

Best answer
84 votes
84 votes
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$
edited by
20 votes
20 votes
Ya it should be D option. As 1st state is also the final state
13 votes
13 votes

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

5 votes
5 votes

the first state is accepting all strings of type an 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 an.bn   and  the given pda is dpda.

option d

Answer:

Related questions