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'.

$\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 May 26 at 18:11
1
$\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.

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