HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

When does a PDA split?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
pdasplitdoeswhen

Problem

In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. In case of PDA where transitions are of the type $a,b \to c$, with $a$ being the input alphabet being read, $b$ being the stack element being read and popped and $c$ being the stack element being pushed. In NFA I understood the splitting upon $\epsilon$ as the ability to guess. So I assumed that a PDA in a state $r$ with stack being $S$ splits into two PDA only when the transition is $\epsilon,\epsilon \to \epsilon \\$ ( that is when $a=b=c=\epsilon$ in the figure below the PDA splits into two with one being in state $r$ and other in $s$ with same stack $S$ ). But now I am a bit doubtful, about when does a PDA split. I feel I am wrong and am misunderstanding something trivial. ( The figure below just shows the part of a larger PDA ). How would it affect the power of a PDA if it were only allowed to split on $\epsilon,\epsilon \to \epsilon$ transition?

Solution

A PDA (or an NFA) doesn't split. At any given point in time, it non-deterministically chooses a valid next step, if any. If there are several options, you can say that the PDA "splits" if you wish, trying all of them in parallel.

A PDA (or an NFA) could have more than one possible move even if it has no $\epsilon$ moves, and conversely, there might be situations in which an $\epsilon$ move is the only possible move of the automaton (can you think of such a situation?). So your identifying $\epsilon$ transitions with "splitting" is wrong.

Context

StackExchange Computer Science Q#48009, answer score: 2

Revisions (0)

No revisions yet.