##### 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
8 Jun 2015 06:34 pm

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

rajashekar
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
28 Apr 2015 07:59 pm

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

Parimal Andhalkar
8 Jun 2015 01:46 pm

plz check it ...  ..

correct or Wrong..?

Arul
8 Jun 2015 06:57 pm

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

Parimal Andhalkar
8 Jun 2015 11:21 pm

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

i used acceptance by final state ..

Arul
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
14 Jun 2015 08:16 pm

u r right