Deterministic Pushdown Automata and DCFLs

Deterministic Pushdown Automata §

• DPDAs are weaker than PDAs.
• Formally, a deterministic pushdown automata is a -tuple where and are all finite sets. We denote and
  • is the set of all states
  • is the input alphabet.
  • is the stack alphabet.
  • is the transition function.
  • is the start state.
  • is the set of accept states.
• The transition function must satisfy the following. For every exactly one of the following is not
• If the output is we perform no action. Otherwise, we have a single move of the form . In a DPDA, there is no ambiguity.
• Strings are accepted by the DPDA if the whole string is read and the machine is on an accept state.
• Strings are rejected if we fail to read the whole string (i.e., because of being unable to pop the stack) or if we never land on the accept state.

Properties §

• Sipser 2.42: The class of DCFLs is closed under complementation. ¹

• An endmarked input is one where we have a special endmarker that is appended to the input string and acts as a way to know when the string ends. An endmarked language is one where all strings are endmarked, and it is denoted .
• Sipser 2.43: is a DCFL if and only if is a DCFL.

Links §

• Sipser 2.4
• Pushdown Automata and Context Free Languages - more on PDAs

Footnotes §

1. The idea is, first, make the DPDA amenable to complementation by only having accept states in states that read symbol. Then, just make all accept states reject states and vice versa among reading states. ↩