youtube DPA

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

enter image description here

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 ?

  • $\begingroup$ PDA is not a standardized model. There are several different variants. Perhaps the variant in the video is different from the variant on Wikipedia. $\endgroup$ – Yuval Filmus Jan 9 at 21:48
  • $\begingroup$ The different variants are equal in power, and can be reduced to each other using simple reductions. $\endgroup$ – Yuval Filmus Jan 9 at 21:49
  • $\begingroup$ 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 ? $\endgroup$ – rafoo Jan 9 at 21:51
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 9 at 21:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Hendrik Jan Jan 10 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.

2- The PDAs from Wikipedia do not allow you to take a transition without popping a letter from the stack (note that as Yuval said: the stack is initialized with a "bottom of stack" symbol), however note that, unlike the PDAs in item 1, you can push an entire word in 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$.

  • $\begingroup$ Is also a modified version of v.1, with allowing to push multiple letters once, equivalent to v.1 and v.2 ? $\endgroup$ – rafoo Jan 10 at 2:08
  • $\begingroup$ Yes, for similar reasons. $\endgroup$ – Bader Abu Radi Jan 10 at 8:56

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.