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 as negating all other possible choices.

For every , , and exactly one of

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

Consider the following transitions from a state

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

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

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

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