push down automata

Question

How many states will the pda for a^n b^n c^m d^m have??

I know it can be drawn using 5 states as given everywhere. But i think it can be drawn using 4 states also.

can anyone tell??

Comments

it depends on value of m,n i.e m,n>=0 or m,n >=1

---

n,m>=0

(q0,ε,z) = (q2,z)...................// if both n = 0 . m= 0

(q0,a,z) = (q0, az)

(q0,a,z) = (q0, aa)

(q0,b,a) = (q1, ε)

(q1,b,a) = (q1, ε)

(q1, ε,z) = (qf, z)....... if m = 0

(q0,c,z) = (q0, cz)  ....if n = 0

(q0,c,c) = (q0, cc)

(q1,c,z) = (q1, cz)

(q1,c,c) = (q1, cc)

(q1,d,c) = (q2,ε)

(q2,d,c) = (q2,ε)

(q2,ε,z) = (qf,z)

---

But your diagram does not make sure that all b's come before all c's.

So, if a C comes it loops 2nd state and then if B comes, it again loops the 2nd state.

---

I guess DPDA = 6 states and NPDA = 5 states.

---

sushmita u tried well but there is little bit problem i will rectify it..

---

Kapil sir I know how to draw it correctly. But I just wanted to know why this diagram is wrong. Because after all bs are exhausted only then can c come because cs are allowed only when stack top is z that is empty stack. So how can b come after c because I haven't make any transition for accepting b when stack top is c??

---

Tauhin sir can u tell the exact problem with this diagram?

---

sushmita check it...now i have udated ur answer....ask ARJUN SIR,,,,to verify it

---

how can transition for 'c' b made from state q0?? after a, b has to come..???

---

1)that is for....if n = 0... 

the string will be generated as....c^md^m.......as. a⁰b⁰ =1

2)and that transition cannot be after a & b...comes...it only when n= 0

---

Oh yeah. But if n>0 always then wat will be the problem in my diagram?

---

then your answer was accurate...i think

---

thanx @ tauhin.

---

I too exactly have the same doubt. But couldn’t get the reason for n=0. Can you please explain me a bit?

---

after 4 years u r asking..i am even not able to recognize my comments..what i have written...but wait i will see and tell.

---

this pda made by you is totally wrong ..

---

sir, i didn’t have made this pda. I think confusion arises since the me and person who has originally posted the questioni having same name!!

I was wondering why the pda with 4 states will not work for n=0?