no. of states in pda

the minimum number of states in the PDA accepting the language

L={a^n b^m |n>m;m,n>0}

a) 2

b) 3

c) 4

d) 5

Pritam Prasun @pritam
8 Jun 2015 06:34 pm

Answer:  b) 3


Given L= {an bm | n > m; m, n > 0}

rajashekar @rajsh3kar
27 Apr 2015 07:51 pm

if,for example n=1 and m=0 ,  n>m satiesfies n>0 also , single 'a'  cant accepted by this automaton but it shud accept na and  suggest it   with transition ?

Pritam Prasun @pritam
28 Apr 2015 07:59 pm

Thank You @rajashekar, I have improved the PDA accordingly.

Parimal Andhalkar @parimal_andhalkar
8 Jun 2015 01:46 pm

plz check it ...  ..

correct or Wrong..?


Arul @innovwelt
8 Jun 2015 06:57 pm

@Parimal: It seems to be correct, except that the state q3 looks unnecessary.

Instead the state q2 can be made as final state (refer Pritam's answer).

Parimal Andhalkar @parimal_andhalkar
8 Jun 2015 11:21 pm

@Arul :   i think ...pritam used acceptance by empty stack...

i used acceptance by final state ..



Arul @innovwelt
9 Jun 2015 02:47 am

@parimal: We need the minimum number of states. In your diagram, what if we add the transition {ε, Z0} -> {Z0} to the state q2 itself & make the state q2 as Final State?

Will there be any issue with that?

by the way, I think, your solution is using "acceptance by Empty stack" & pritam's solution is "acceptance by Final state". not vice versa.

Parimal Andhalkar @parimal_andhalkar
14 Jun 2015 08:16 pm

 u r right