Adding or Removing multiple symbols from stack in PDA

Adding or Removing multiple symbols from stack in PDA

by MATTEO ZANELLA -
Number of replies: 1

Is it possible to make a PDA that upon reading a symbol, adds or removes the two top-most symbols of the stack?

If so is the only way of doing this by using an epsilon transition in the PDA (to add/remove the second top-most symbol after having already added/removed the first one)?

In reply to MATTEO ZANELLA

Re: Adding or Removing multiple symbols from stack in PDA

by Giorgio Satta -

According to the definition of PDA, in a move you can only read the topmost symbol from the stack. Therefore you cannot remove the two top-most symbols of the stack in a single move.

To remove the two top-most symbols of the stack, you have to use a sequence of two moves, the second one being an epsilon move, and you need to use a special PDA state that forces you to apply the second move only after the first one.