0
$\begingroup$

I have a problem where I'm asked to prove that if P is a pushdown automaton, then there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language as P. I've tried to codify the stack alphabet of P in binary, using the same ammount of symbols for each representation so I know where the codification of one symbol starts and ends, but I don't know how to simulate P with P'.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Please detail your attempts, and what you don't understand, and we'll help from there. This site does not accept homework dumps. $\endgroup$
    – Shaull
    Commented May 26, 2021 at 18:11

1 Answer 1

Reset to default
2
$\begingroup$

You're on a good path! Keep at it. Remember that a pushdown can have a finite-state control, and you can remember up to a finite amount of information in the finite-state control. Also, it can have $\epsilon$-transitions (so the read head doesn't consume any of the input). Those might be helpful.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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