patternMinor
Can PDA have empty stack transition?
Viewed 0 times
canstackemptypdatransitionhave
Problem
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 ?
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 ?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#134156, answer score: 2
Revisions (0)
No revisions yet.