0
$\begingroup$

i saw in a book how to construct a PDA for a case with m is equal to n . It's pretty simple, just push a symbol for every a and pop this symbol for every b that the PDA reads. But, i don't found a way to construct a PDA for this particular case. Every help is welcome.

$\endgroup$
2
$\begingroup$

You can think about the scheme you proposed (push a symbol for every a, pop for every b) as using the stack as a counter. When you see an a, you increment the counter (push a symbol onto the stack) and when you see a b, you decrement the counter (pop from the stack). In the case where $m=n$, the stack should be empty after processing the whole string, or in other words the value of the counter should be 0. Following the same scheme, how would we know from the count that $m > n$? What would the stack have to look like in that case?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.