Deterministic PushDown Automaton transitions

Deterministic Context-Free Languages (DCFLs) are a subset of Context-Free Languages (CFLs) with some special properties. They are always unambiguous. They are also closed under complement. They can be parsed in linear time.

A PushDown Automaton (PDA) is a Deterministic PushDown Automaton (DPDA) if every transition in the PDA is deterministic. Given a combination of the symbol being read and the symbol on top of the stack, there is only one transition to follow from any state. This ensures determinism. Think of $\epsilon$ as negating all other possible choices.

For every $q \in Q$ , $a \in \Sigma$ , and $x \in \Gamma$ exactly one of

$\begin{equation*} \delta(q, \epsilon, \epsilon), \delta(q, a, \epsilon), \delta(q, \epsilon, x), \delta(q, a, x), \end{equation*}$

is non-empty and the non-empty one only contains a single transition.

Consider the following transitions from a state $q$

$\epsilon, \epsilon \rightarrow$

This is read as ignore the input symbol, ignore the top of the stack. In this case, there can be no other transitions from $q$ . Adding any other transition will allow a choice and create non-determinism.

$a, \epsilon \rightarrow$

This is read as read the input symbol $a$ , ignore the top of the stack. In this case, there can be no transitions that read the same input symbol ( $a, x \rightarrow$ ). However, there can be transitions that read a different input symbol ( $b, x \rightarrow$ )

$\epsilon, x \rightarrow$

This is read as read ignore the input symbol, pop $x$ from the top of the stack. In this case, there can be no transitions that pop the same input symbol ( $a, x \rightarrow$ ). However, there can be transitions that pop a different input symbol ( $a, y \rightarrow$ )

$a, x \rightarrow$

This is read as read the input symbol $a$ , pop $x$ from the top of the stack. In this case, there can no transitions that read the input symbol $a$ and pop $x$ from the top of the stack ( $a, x \rightarrow$ ). However, there can be transitions that differ at either place ( $a, y \rightarrow$ , $b, x \rightarrow$ , $b, y \rightarrow$ ).

The Beard Sage

Deterministic PushDown Automaton transitions

$\epsilon, \epsilon \rightarrow$

$a, \epsilon \rightarrow$

$\epsilon, x \rightarrow$

$a, x \rightarrow$

Leave a Reply Cancel reply