Context-Free Language

Overview

A (nondeterministic) pushdown automaton (PDA) 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 \mathcal{P}(Q\times {\mathrm{\Gamma }}_{ϵ})$ is the transition function,
5. $q_0\in Q$ is the start state, and
6. $F\subseteq Q$ is the set of accept states.

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

PDAs are often described with two different acceptance modes: by final state and by empty stack. We assume acceptance by final state. The two are shown to be equivalent.

Context-Free Grammar

A context-free grammar (CFG) is a $4$-tuple $⟨V,\mathrm{\Sigma },R,S⟩$ where

1. $V$ is a finite set called the variables (or nonterminals).
2. $\mathrm{\Sigma }$ is a finite set, disjoint from $V$, called the terminals.
3. $R$ is a finite set of rules, with each rule being a variable to a string of variables/terminals.
4. $S\in V$ is the start variable.

They are equivalent to PDAs in their descriptive power.

If $u$, $v$, and $w$ are strings of variables and terminals, and $A\to w$, we say that $uAv$ yields $uwv$ (denoted $uAv\Rightarrow uwv$). We say $u$ derives $v$ (denoted $u\stackrel{\ast }{\Rightarrow }v$), if $u=v$ or if a sequence $u_1,u_2,\dots ,u_k$ exists for $k\ge 0$ and

A derivation of $w$ is a sequence of substitution steps, beginning with the start variable, that produces $w$. A derivation of a string $w$ in a grammar $G$ is a leftmost derivation if at every step the leftmost remaining variable is the one replaced.

Ambiguity

A string $w$ is derived ambiguously in context-free grammar $G$ if it has two or more different leftmost derivations. Grammar $G$ is ambiguous if it generates some string ambiguously.

A context-free language that can be generated only from an ambiguous grammar is called inherently ambiguous.

Reductions

A reduce step is a reversed substitution, whereby the string of terminals and variables on the RHS of a rule is replaced by the variable on the corresponding LHS. If $u$ and $v$ be strings of variables and terminals, write $u\rightarrowtail v$ to mean that $v$ can be obtained from $u$ by a reduce step. A reduction from $u$ to $v$ is a sequence

We say that $u$ is reducible to $v$, written $u\stackrel{\ast }{\rightarrowtail }v$, whenever $v\stackrel{\ast }{\Rightarrow }u$. The string being replaced is called the reducing string.

A reduction from $w$ is a reduction from $w$ to the start variable. A leftmost reduction is a reduction in which each reducing string is reduced only after all other reducing strings to its left.

Valid Strings

Let $G$ be a CFG with terminals $\mathrm{\Sigma }$. A string that appears in a leftmost reduction of some string in $L(G)$ is called a valid string.

Let $u_i$ be a valid string. In the reduce step $u_i\rightarrowtail u_{i+1}$, suppose rule $T\to h$ was applied in reverse. That is, $u_i=xhy$ and $u_{i+1}=xTy$ for some strings $x$ and $y$. Then $h$, along with reducing rule $T\to h$, is called a handle of $u_i$.

We say that a handle $h$ of a valid string $v=xhy$ is a forced handle if $h$ is the unique handle in every valid string $xh\hat{y}$ where $\hat{y}\in {\mathrm{\Sigma }}^{\ast }$. We say $h$ is forced by lookahead $k$ if $h$ is the unique handle of every valid string $xh\hat{y}$ where $\hat{y}\in {\mathrm{\Sigma }}^{\ast }$ agrees with $y$ on their first $k$ symbols. (If either $y$ or $\hat{y}$ is shorter than $k$, the strings must agree up to the length of the shorter one).

Chomsky Normal Form

A context-free grammar is in Chomsky normal form if every rule is of the form

where $a$ is any terminal, and $A$, $B$, and $C$ are variables distinct from start variable $S$. This is typically done in stages:

1. Introduce a new start variable $S_0$ with rule $S_0\to S$.
   1. This ensures the start state is never on the RHS.
2. Eliminate all $ϵ$-rules (except for that of the start variable).
   1. These are the rules that map a variable to $ϵ$.
3. Eliminate all unit rules.
   1. These are the rules that map a variable to another variable.
4. Introduce new rules to match forms above.

Closure Operations

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

• Union: $A\cup B=\{x\mid x\in A\vee x\in B\}$
• Reversal: $A^R=\{x^R\mid x\in A\}$
• Concatenation: $A\circ B=\{xy\mid x\in A\wedge y\in B\}$
• Kleene star: $A^{\ast }=\{x_1{x}_2\cdots x_k\mid k\ge 0\wedge x_i\in A\}$

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

Pumping Lemma

Let $L$ be a context-free language. Then there exists a pumping constant $p$ where, if $s$ is any string in $L$ of at least length $p$, then $s$ can be written as $s=uvxyz$ such that

1. $u{v}^{i}x{y}^{i}z\in L$ for any integer $i\ge 0$,
2. $|vy|>0$, and
3. $|vxy|\le p$.

The stronger variant of this lemma allows one to strengthen condition 2 as follows:

2. $v\ne ϵ$ and $y\ne ϵ$.