Deterministic Context-Free Language

Overview

A deterministic pushdown automaton (DPDA) is a $6$-tuple $⟨Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F⟩$, where $Q$, $\mathrm{\Sigma }$, $\mathrm{\Gamma }$, and $F$ are all finite sets, and

1. $Q$ is the set of states,
2. $\mathrm{\Sigma }$ is the input alphabet,
3. $\mathrm{\Gamma }$ is the stack alphabet,
4. $\delta :Q\times {\mathrm{\Sigma }}_{ϵ}\times {\mathrm{\Gamma }}_{ϵ}\to (Q\times {\mathrm{\Gamma }}_{ϵ})\cup \{\varnothing \}$ is the transition function,
5. $q_0\in Q$ is the start state, and
6. $F\subseteq Q$ is the set of accept states.

For every $q\in Q$, $a\in \mathrm{\Sigma }$, and $x\in \mathrm{\Gamma }$, exactly one of the values is not $\varnothing$:

• $\delta (q,a,x)$;
• $\delta (q,a,ϵ)$, an $ϵ$-stack move;
• $\delta (q,ϵ,x)$, an $ϵ$-input move;
• $\delta (q,ϵ,ϵ)$, an $ϵ$-stack and $ϵ$-input move.

A language is called deterministic context-free if a DPDA recognizes it.

DPDAs are often described with two different acceptance modes: by final state and by empty stack. We assume acceptance by final state. Acceptance by empty stack is strictly less powerful, only recognizing prefix-free DCFLs.

Deterministic CFG

A deterministic context-free grammar (DCFG) is a CFG such that every valid string has a forced handle.

If we restrict our attention to prefix-free languages, they are equivalent to DPDAs in their descriptive power. By adding an endmarker to a language, we ensure the resulting language is prefix-free.

Dotted Rules

A dotted rule is a rule in a CFG augmented with a dot ($\bullet$) between two of the symbols found on its RHS. For example, rule $B\to u_1{u}_2\cdots u_k$ containing $k$ symbols has $k+1$ dotted rules:

DK-Test

Every CFG $G$ has a corresponding NFA and DFA, typically denoted $K$ and $DK$ respectively, that can identify handles. That is, $K$ and $DK$ accept input $w$ if and only if $w$ is the prefix of some valid string $v=wy$ and $w$ ends with a handle of $v$. $DK$ is constructed from $K$ using the standard power set construction.

$K$'s states correspond to the dotted rules of $G$. It has a special start state with an $ϵ$-move to $\boxed{{\displaystyle S_0\to \bullet u}}$ for every rule involving start variable $S_0$. Subsequent transitions are of one of two forms:

• A shift-move appears for every terminal/variable $a$ and every rule $B\to uav$:$$\boxed{{\displaystyle B\to u\bullet av}}\stackrel{a}{⟶}\boxed{{\displaystyle B\to ua\bullet v}}$$
• An $ϵ$-move appears for all rules $B\to uCv$ and $C\to r$:$$\boxed{{\displaystyle B\to u\bullet Cv}}\stackrel{ϵ}{⟶}\boxed{{\displaystyle C\to \bullet r}}$$

The accept states are all $\boxed{{\displaystyle \boxed{{\displaystyle B\to u\bullet }}}}$ corresponding to a completed rule. They have no outgoing transitions.

Generalizations of the $DK$-test can be used to determine if a grammar is an $LR(k)$ grammar or not. This is known as a $DK$-test with lookahead $k$ or just $D{K}_k$-test.

LR Grammar

An LR($k$) grammar is a context-free grammar such that the handle of every valid string is forced by lookahead $k$.

LR($1$) grammars are equivalent to DPDAs in power. For every $k>1$, an LR($k$) grammar can be converted to a DPDA and hence is also equivalent to LR($1$). For this reason, If $k$ is omitted, it is assumed $k=1$.

Closure Operations

Let $A$ and $B$ be deterministic context free languages over alphabet $\mathrm{\Sigma }$. Such languages are closed under the following:

• Complementation: $\bar{A}=\{w\in {\mathrm{\Sigma }}^{\ast }\mid w\notin A\}$
• Endmark: $A⊣=\{w⊣\mid w\in A\}$
  • In fact, $A$ is a DCFL if and only if $A⊣$ is a DCFL.

Furthermore, the intersection of a DCFL with a regular language is deterministic context-free.