PDAs and context-free grammars

PDAs and context-free grammars#

Moving on from DFAs, NFAs and regular languages, we next consider more powerful models of computation, namely pushdown automata (PDAs) and context-free grammars (CFGs). These turn out to be analogous to finite-state automata and regular languages, but are more powerful. In particular, we will show that CFGs and PDAs are equivalent and that they are strict supersets of regular languages and NFAs.

Context-free grammars#

A CFG consists of variables and terminal symbols, as well as rules which expand these variables into strings of other variables and terminal symbols.

Definition 9 (Context-free grammar)

A context-free grammar (CGG) is a 4-tuple $(V, Σ, R, S)$ , where

$V$ is a finite set called the variables,
$Σ$ is a finite set that is disjoint from $V$ , called the terminals,
$R$ is a finite set of rules, with each rule being a pair consisting of a variable and a string of variables and terminals,
$S \in V$ is the start variable.

We now introduce some terminology on CFGs. We say that a string yields another if the latter can be obtained by applying a rule of a CFG onto the former. Similarly, we say that a string derives another if the latter can be obtained by applying a finite number of rules to it.

Definition 10 (Yields, derives)

If $A \to w$ is a rule of a CFG, we say that $u A v$ yields $u w v$ , written $u A v ⟹ u w v$ . We say that $u$ derives $v$ , written $u \overset{*}{⟹} v$ , if a sequence $u_{1}, u_{2}, \dots u_{k}$ exists for some $k \geq 0$ such that

u ⟹ u_{1} ⟹ \dots ⟹ u_{k} ⟹ v .

Similarly to DFAs and NFAs, we define the language of a CFG to be the set of strings it can represent, i.e. the set of strings that can be derived from it.

Definition 11 (Context-free language)

We define the language of a CFG $G$ with terminals $Σ$ and start variable $S$ , to be the set $L (G) \equiv {w \in Σ^{*} | S \overset{*}{⟹} w} .$

We can now look at a couple of examples of CFGs and strings that these generate. We can visualise the derivation of a string in a language using a parse tree, where each node is a variable or terminal symbol and each edge corresponds to part of a substitution rule. First is the following example of a CFG which generates all strings of the form $0^{k} 1^{k}$ for some $k \geq 0$ . We already know that this set of strings is not a regular language. Therefore, this example shows that the set of context-free languages (CFLs) is not equal to the set of regular languages.

Example 6 (Example CFG)

Consider the CFG $G_{1} = (V, Σ, R, S)$ where $V = {S, E}, Σ = {0, 1}$ and $R$ consists of the rules

\begin{array}{r} \begin{aligned} S & \to 0 S 1 \\ S & \to E \\ E & \to ϵ \end{aligned} \end{array}

Below is an example of a derivation of the string $0011$ using this language.

../../_images/76c9157b44e691f07d8916006b64f4cde0bbb70f0349771ff3407790852dd6e6.png

We also have the following example CFG which generates valid mathematical expressions involving sums and multiplications. CFGs similar to this can be used to define parsers for programming languages.

Example 7 (Example CFG for mathematical expressions)

Consider the CFG $G_{2} = (V, Σ, R, S)$ where $V = {E, T, F}, Σ = {a, (,)}, S = E$ and $R$ consists of the rules

\begin{array}{r} \begin{aligned} E & \to T | F + T \\ T & \to F | F * T \\ F & \to (E) | a \end{aligned} \end{array}

Below is an example of a derivation of the string $a*(a+a)$ using this language.

../../_images/abf2f1619c8e6b6b2c0f510113ddc30fb11c004dc6d93bda54d204345ab37935.png

Sometimes, a string in a CFL can be derived in more than one way (even if we account for applications of the same rules in different orders). In such cases, the language is ambiguous in the sense that there may be more than one parse tree that correspond to the same given string. The following definitions formalise this notion.

Definition 12 (Leftmost derivation)

We call a derivation of a string in a CFG a leftmost derivation if at every step of the derivation the leftmost variable is the one that is replaced.

This idea allows us to succinctly define ambiguous languages.

Definition 13 (Ambiguity)

We say that a string $w$ is derived ambiguously from a CFG $G$ , if there is more than one leftmost derivation of $w$ in $G$ . If a CFG $G$ contains a string that can be derived ambiguously, we say that $G$ is ambiguous. If a CFL can only be generated by an ambiguous CFG, we say it is inherently ambiguous.

Some CFLs are inherently ambiguous, which means that they can be generated only by ambiguous grammars.

Chomsky normal form#

Definition 14 (Chomsky normal form)

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

\begin{aligned} A & \to B C A & \to a \end{aligned}

where $a$ is any terminal and $A,$ $B,$ and $C$ are any variables, except that $B$ and $C$ may not be the start variable. In addition, we permit the rule $S \to ϵ$ where $S$ is the start variable.

Lemma 4 (CFLs generated by CFG in Chomsky normal form)

Any context-free language is generated by a context-free grammar in Chomsky normal form.

Pushdown Automata#

Now we move to pushdown automata (PDA), which are another kind of computational model. PDAs are similar to NFAs in that they have a finite number of states and allow for nondeterminism. We will show that PDAs have the same expressive power as CFGs, in a somewhat analogous way that NFAs have the same power as regular expressions. It will turn out that PDAs are very useful in this sense because they provide another way to prove things about CFLs, in addition to CFGs. PDAs extend NFAs by introducing a stack of symbols, from which they can read symbols as well as add new ones or remove existing symbols. The stack itself can be of infinite length, which is what makes PDAs more powerful than NFAs.

Definition 15 (Pushdown automaton (PDA))

A pushdown automaton is a $6$ -tuple $(Q, Σ, Γ, δ, q_{0}, F),$ where $Q, Σ, Γ$ and $F$ are all finite sets, and

$Q$ is a finite set, the set of states,
$Σ$ is a finite set, the input alphabet,
$Γ$ is a finite set, the stack alphabet,
$δ : Q \times Σ_{ϵ} \times Γ_{ϵ} \to P (Q \times Γ_{ϵ})$ is a function, the transition funciton,
$q_{0} \in Q$ is the start state,
$F \subseteq Q$ is the set of accept states.

Crucially a PDA can only read, write or remove symbols at the top of the stack. Now we define what it means for a PDA to accept a string, which is analogous to an NFA accepting a string.

Definition 16 (PDA accepts)

A pushdown automaton $M = (Q, Σ, Γ, δ, q_{0}, F)$ acccepts an input $w$ if it can be written in the form $w = w_{1} w_{2} \dots w_{m}, w_{i} \in Σ_{ϵ},$ and there exist sequences of states $r_{0}, r_{1}, \dots, r_{m} \in Q$ and strings $s_{0}, s_{1}, \dots, s_{m} \in Γ^{*}$ that satisfy

$r_{0} = q_{0}$ and $s_{0} = ϵ .$
For $i = 0, \dots, m - 1,$ we have $(r_{i + 1}, b) \in δ (r_{i}, w_{i + 1}, a),$ where $s_{i} = a t, s_{i + 1} = b t$ with $a, b \in Γ_{ϵ}$ and $t \in Γ^{*} .$
$r_{m} \in F .$

Context Free Pumping Lemma#

Theorem 6 (Pumping Lemma for CFLs)

For every CFL $A$ , there exists an integer $p$ such that if $s \in A$ and $| s | \geq p$ , then $s = u v x y z$ where

$u v^{i} x y^{i} z \in A$ for all $i \geq 0$ ,
$v y \neq ϵ$ ,
$| v x y | \leq p$ .

Example 8 (A non-context-free language)

The language $A = {0^{k} 1^{k} 2^{k} | k \geq 0}$ is not a CFL.

Lemma 5 (CFL not closed under intersection)

The class of context-free languages are not closed under intersection.