# Can PDA have empty stack transition?

From a youtube video, this PDA can recognize any palindrom.

However, from wikipedia, here is one of the criteria of PDAs.

We clearly see that the transition function can't take an empty stack as input, as epsilon is not a part of Gamma. (but it can use it as output, and also epsilon input is allowed as we see in the union). But in the video, all transitions from q2 use empty stack as input stack character. What's wrong ?

• PDA is not a standardized model. There are several different variants. Perhaps the variant in the video is different from the variant on Wikipedia. Commented Jan 9, 2021 at 21:48
• The different variants are equal in power, and can be reduced to each other using simple reductions. Commented Jan 9, 2021 at 21:49
• So can we replace theses transitions "a, eps -> a" with "a, X -> X a" for all characters X in the stack Alphabet to conform with the definition of wikipedia ? Commented Jan 9, 2021 at 21:51
• The PDA in the image also pushes a "bottom of stack" symbol as the very first step, whereas the Wikipedia definition includes has the stack initialized with such a symbol. Commented Jan 9, 2021 at 21:59
• Also please never write that the transition function $\delta$ is of the form $\delta: Q \times (\Sigma\cup\{\varepsilon\})\times \Gamma \to \mathcal P(Q\times \Sigma^*)$ without extra restrictions. The reason is that $P(Q\times \Sigma^*)$ contains infinite sets. Commented Jan 10, 2021 at 2:06

1- The PDAs in the video seem to have a transition function of the form $$\delta: Q\times (\Sigma\cup\{\epsilon\}) \times (\Gamma \cup \{ \epsilon\}) \to 2^{Q\times (\Gamma \cup \{\epsilon\})}$$, so you are allowed to take a nondeterministic transition without reading any input letter and without popping a letter from the stack. Note however, that you are allowed to push a single letter (or none) to the stack in a transition that you take.
So you have two variants of PDAs that have slightly different syntax, however it is not hard to prove that a PDA from one variant can simulate a run of a PDA from the other variant, and thus both variants recognise the same class of languages, CFL. A high-level explanation of how both variants can simulate each other is given next. A PDA $$A$$ of the 1st variant simulates a run of a PDA B of the 2nd variant by first pushing a "buttom of stack letter", then $$A$$ mimics the transitions that $$B$$ takes: in the case where $$B$$ takes a transition that pushes a word of length $$\geq 2$$ into the stack, you can introduce new states that push that word, and then move to the state that $$B$$ moves to. Conversely, a PDA $$B$$ of the 2nd variant simulates a run of a PDA $$A$$ of the 1st variant by first popping the "buttom of stack letter", then $$B$$ mimics the transitions that $$A$$ takes: the non-trivial part here is to mimic popping $$\epsilon$$ from the stack. This is easy as $$B$$ is allowed to push an entire word into the stack: popping $$\epsilon$$, and then pushing a word $$w$$, is equivalent to popping a letter $$\sigma$$, and then pushing the word $$\sigma\cdot w$$.