in Theory of Computation
282 views
0 votes
0 votes
Draw PDA for ((a^m)(b^n)(a^n)(b^m))  ?
in Theory of Computation
282 views

1 Answer

2 votes
2 votes

Initially, m a's will be pushed on to the stack, then n b's will be pushed on to the stack. Now, for the next n a's, we will pop out the n b's which was already on the stack. Now the stack only has m a's, so for the next m b's we will pop m a's. Here is the PDA state diagram 

2 Comments

For the language L = ${\{a^mb^na^nb^m/ m \geq1, n\geq0 \}}$ DPDA is not possible we have to go for PDA.
0
0
edited by
Yes, looks like it can't be solved by a DPDA when $n\geq 0$ and $m\geq1$.
0
0

Related questions