1
$\begingroup$

The formal definition of the pushdown automata according to Mike Sisper's book on theory of computation is as follows: formal definition. The transition function however only takes in one symbol from the stack (after popping it) and returns sets where each set only has a single letter from the stack alphabet.

But later in the book, it says this:

The PDA P begins by writing the start variable on its stack. It goes through a series of intermediate strings, making one substitution after another. Eventually it may arrive at a string that contains only terminal symbols, meaning that it has used the grammar to derive a string. Then P accepts if this string is identical to the string it has received as input.

It seems to say that the PDA is going to write more than one symbols in one reading of the input tape but how is this possible if the PDA can only write one symbol?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Based on the given definition, you cannot have a single transition that pushes multiple symbols from a single state. But you can simulate it. The idea here is to add auxiliary states and take advantage of $\varepsilon$ in the transition. Say you want to push $abc$ ($c$ will be the topmost symbol after) when reading $1$ from state $q_i$ going to $q_j$. Then modify your PDA so it will have the following transitions:

  • $\delta(q_i,1, \varepsilon) = \{(q_{i,0}, a)\} $
  • $\delta(q_{i, 0}, \varepsilon , \varepsilon) = \{(q_{i,1}, b)\} $
  • $\delta(q_{i, 1}, \varepsilon , \varepsilon) = \{(q_{j}, c) \} $

The states $q_{i,0}$ and $q_{i,1}$ are auxiliary states. You can add more depending on how many stack symbols you want to push when reading a single input symbol.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But there's another part that confuses me. In the book and his lecture videos, Michael compares the symbols at the top after making all substitutions that are required to get a terminal at the top (by substituting any non-terminals with new non-terminals until a terminal appears). But how could one do this? You need to read some symbols first before making a new substitution but if you do that you lose the compare read symbols with the terminal that might appear after a terminal appears. $\endgroup$
    – Sbeve
    May 11 at 16:57
  • 1
    $\begingroup$ You can simulate this peeking of the top symbol using the same idea as in my answer, read the input and pop the stack in one transition, enter an auxiliary state, transition out of this auxiliary state without reading an input but push the same stack symbol popped earlier. $\endgroup$
    – Russel
    May 11 at 23:58

Your Answer

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

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