1
$\begingroup$

I'm studying computer science and I want to show that a language which is accepted by a pushdown automaton with a bounded stack height is regular, but I'm totally lost... Can someone try to explain how we can prove it ?

Thank you in advance!

$\endgroup$
3
$\begingroup$

If the stack has bounded height then there are only finitely many possibilities for its contents. Therefore a regular automaton can “remember” the entire contents of the stack. In other words, you can convert the PDA into an equivalent regular automaton in which each state stores both the state of the PDA and the contents of its stack.

$\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.