plz answer

Question

the minimum number of states in the PDA accepting the language

$L=\left\{a^n b^m \mid n>m;m,n>0 \right\}$

a) 2

b) 3

c) 4

d) 5

Answer 1

if  we  use stack symbols as {z0,A} where initial stack symbol is {z0}  and final state is {q2} than if the  transition functions are-

(q0, a, z0) --> (q0, Az0)

(q0, a, A) --> (q0, AA)

(q0, b, A) --> (q1, ϵ)

(q1, b, A) --> (q1, ϵ)

(q1, ϵ, A) --> (q2, ϵ)

q2 is final state..

Minimum no. of states = 3, with NPDA.

Comments

If the combination is unique then a DPDA allows ∈-move without making it NPDA??

---

@Arjun Sir 

 (q1,^,A) and (q1,b,A)  I think it will still be DPDA even if include them in q1.

But the fact that including them in q1 will reject the  the string aaaaabbb.

After accepting aaaaab we go to state q1 then .we can delete any number of a's in q1 with the transition (q1, ϵ, A) --> (q1, ϵ).  and then when we get (q1,b,Z0) we have no transitions and it would halt in a non-final state.Thus a valid string for the Language will not be accepted.

Sir I am not getting why otherwise both ((q^,A) and (q1,b,A) ) cannot be valid.

---

NOTE : Much Beyond GATE level. Should be skipped by GATE aspirants. 

Answer will be 1. We can accept every CFL using only single state PDA.

Given a CFG you can construct a single state PDA, accepting by empty stack.

If L is a CFL and ϵ does not belong to L, then there is a PDA M accepting L by final state such that M has at most 2 states and makes no ϵ-moves.

https://cs.stackexchange.com/questions/11321/designing-a-pda-w-o-epsilon-moves-and-leq-2-states-to-accept-an-epsilon

P.S. : A GATE aspirant should not spend time on this. Once you go to IISc, take Automata theory course, you will be taught similar question and you will be able to solve it(or similar question) in your homework.

 

Answer 2

NOTE : Much Beyond GATE level. Should be skipped by GATE aspirants. 

Answer will be 1. We can accept every CFL using only single state PDA.

Given a CFG you can construct a single state PDA, accepting by empty stack.

If L is a CFL and ϵ does not belong to L, then there is a PDA M accepting L by final state such that M has at most 2 states and makes no ϵ-moves.

https://cs.stackexchange.com/questions/11321/designing-a-pda-w-o-epsilon-moves-and-leq-2-states-to-accept-an-epsilon

P.S. : A GATE aspirant should not spend time on this. Once you go to IISc, take Automata theory course, you will be taught similar question and you will be able to solve it(or similar question) in your homework.

Answer 3

Assuming only DPDA:

We cannot accept this language using empty stack. Because aaab is in L and aaabb also in L, thus violating prefix property. So, this language must be accepted using final state as long as PDA is deterministic.   

State 1- counting A using stack

State 2- counting B using stack

State 3 - accept

State 4 - reject

Comments

If we use End of String marker ,Then Can we accept the following language using 4 state DPDA with empty stack ??

as we can do so:

(q1 , $ , A )   ---->  (q2, ∈)

(q2, ∈ , A )   ---->  ( q2 , ∈)

Here I took $ as end marker.

---

@Arjun Sir, I have a doubt that, any deterministic turing machine should have minimum 2 states ?

Please tell if I a understanding it right. If there is only 1 state, which is both final and initial state and it has not defined a transition on some input symbol, then the strings containing this input symbol will halt into the same state as a dead configuration, and hence be accepted, which is wrong as they should not be accepted. Thus, we have minimum 2 states.

---

@Arjun sir, please show the Dpda diagram.... I'm failing to draw Dpda diagram... because (q1,b,a) and (q1,€,a) make it Npda....I have been trying on this type of problem like n'a>n'b...but everytime I'm failing...most of the people violating the Dpda definition...if(q,€,x) != Phi then (q,a,x) must be phi ....