Context-Free Languages

Pushdown Automata

Pushdown automata resemble nondeterministic finite automata but have access to unlimited memory, modeled as a stack that operates on a first-in, last-out (FILO) principle.

Definition. A pushdown automaton is a six-tuple $\langle Q, \Sigma, \Gamma, \delta, S, F \rangle$, where

• $Q$ is a finite set of states,
• $\Sigma$ is a finite set of input symbols,
• $\Gamma$ is a finite set of stack symbols,
• $\delta : Q \times \Sigma_{\epsilon} \times \Gamma_{\epsilon} \to P(Q \times \Gamma_\epsilon)$ is the transition function, where $\Sigma_{\epsilon} = \Sigma \cup \{ \epsilon \}$, $\Gamma_\epsilon = \Gamma \cup \{ \epsilon \}$, and $P(Q \times \Gamma_\epsilon)$ is the power set of $Q \times \Gamma_\epsilon$,
• $S \in Q$ is the start state and
• $F \subseteq Q$ is a finite set of accept states.

At the core of a pushdown automaton's definition is its transition function. The next move is determined by three elements from the domain $Q \times \Sigma_{\epsilon} \times \Gamma_{\epsilon}$:

• The current state.
• The next input symbol $\sigma \in \Sigma_\epsilon$:
  • If $\sigma=\epsilon$, the machine moves without consuming input.
• The symbol $\gamma \in \Gamma_\epsilon$ at the top of the stack:
  • If $\gamma=\epsilon$, the machine moves without reading or popping the stack.
  • Otherwise, the machine pops $\gamma$ from the stack.

The machine transitions to a new state and updates the stack based on a pair from the domain $Q \times \Gamma_\epsilon$:

• It enters a (possibly new) state.
• It may push a symbol $\gamma \in \Gamma_\epsilon$ onto the stack:
  • If $\gamma=\epsilon$, no symbol is written.

Example Operations

If we want the automaton to move to state $q_1$ and push a symbol $\gamma \in \Gamma$ onto the stack when the machine is in state $q_0$ and reads input $\sigma$, we specify the transition function $\delta$ by including $(q_1, \gamma)$ in $\delta(q_0, \sigma, \epsilon)$.

Conversely, if we want the automaton to move to state $q_1$ and pop the symbol on top of the stack when

• the machine is in state $q_0$,
• reads input $\sigma$, and
• the symbol on top of the stack is $\gamma \in \Gamma$,

we specify the transition function $\delta$ by including $(q_1, \epsilon)$ in $\delta(q_0, \sigma, \gamma)$.

Computation

A pushdown automaton $M = \langle Q, \Sigma, \Gamma, \delta, S, F \rangle$ computes as follows. It accepts input $w$ if $w$ can be written as $w = w_1 w_2 \ldots w_m$, where each $w_i \in \Sigma_\epsilon$, and sequences of states $r_0, r_1, \ldots, r_m \in Q$ and strings $s_0, s_1, \ldots, s_m \in \Gamma^*$ exist that satisfy the following three conditions. The strings $s_i$ represent the sequence of stack contents that $M$ has on the accepting branch of the computation.

1. $r_0 = S$ and $s_0 = \epsilon$. This condition signifies that $M$ starts properly, in the start state with an empty stack.

2. For $i = 0, \ldots, m - 1$, we have $(r_{i + 1}, b) \in \delta(r_i, w_{i + 1}, a)$, where $s_i = at$ and $s_{i+1} = bt$ for some $a, b \in \Gamma_\epsilon$ and $t \in \Gamma^*$. This condition states that $M$ transitions correctly based on its state, stack, and input symbol.

3. $r_m \in F$. This condition ensures that $M$ reaches an accept state at the end of the input.

What can be computed by Pushdown Automata

Theorem. The class of context-free languages is closed under union, concatenation, and star operations.

What cann't be computed by Pushdown Automata

Pumping Lemma. For every context-free language $L$, there is a number $p$, such that for every $\omega \in L$, if the length of $\omega$ is greater than $p$, then $\omega$ can be devided into five pieces $\omega = axyzb$, satisfying the following three conditions:

1. $ax^iyz^ib \in L$, for all $i \ge 0$,
2. $|xyz| \le p$ and
3. $|x| \ge 0$ or $|z| \ge 0$.

Context-Free Grammar

Definition. A context-free grammar is a four-tuple $\langle N, \Sigma, S, R\rangle$, where

• $N$ is a finite set of symbols called the variables,
• $\Sigma$ is a finite set of symbols, disjoint from $N$, called the terminals,
• $S \in N$ is the start symbol, and
• $R$ is a finite set of rules, with each rule of the form $X \to \omega$, where $X \in N$ and $\omega \in (N \cup \Sigma)^+$.

Computation. Let $u, v, w \in (N \cup \Sigma)^*$.

• Say that $uAv$ yields $uwv$, written $uAv \Rightarrow uwv$, if there exists a rule $A \to w$ of the grammar,
• Say that $u$ derives $v$, written $u \stackrel{*}{\Rightarrow} v$, if $u = v$ or if a sequence $u_1, u_2, \ldots, u_k$ exists for $k \ge 0$ and

$$u \Rightarrow u_1 \Rightarrow u_2 \Rightarrow \ldots \Rightarrow u_k \Rightarrow v.$$

The language of the grammar is $\{ w \in \Sigma^* | S \stackrel{*}{\Rightarrow} w \}$.

Chomsky Normal Form. A context-free grammar $\langle N, \Sigma, S, R\rangle$ is in chomsky normal form if each rule is of one of the two forms

• $X \to YZ$, where $X \in N$, and $Y, Z \in N \setminus \{ S \}$,
• $X \to a$, where $X \in N, a \in \Sigma$.

In addition, we permit $S \to \epsilon$, where $S$ is the start variable.

Equivalence between Context-Free Grammar and Pushdown Automata

1. For every context-free grammar $G$, there is an automaton $M$, such that $M$ recognizes the language generated by $G$.

2. If a pushdown automaton recognizes some language, then it is context-free.

Proof: For the convenience of proof, we modify a pushdown automaton $M = \langle Q, \Sigma, \Gamma, \delta, S, F \rangle$ to give it three features:

• $M$ accepts by entering empty stack.

• These is only one accept state $q_{accpet}$ in $F$.
• Each transition either pushes a symbol onto the stack or pops one off the stack, but it does not do both at the same time.

The way to construct a context-free grammar $G$ from the push-down automaton $M$ is given by follow:

(1) $\forall p \in Q$, we put the rule $N_{pp} \to \epsilon$ in G.
(2) $\forall p,q,r \in Q$, we add to $G$ a new rule $N_{pq} \to N_{pr} N_{rq}$,
(3) $\forall p, q, r, s \in Q$, if $\exists a, b\in \Sigma_\epsilon$, $t \in \Gamma$, s.t. $(r,t) \in \delta(p,a,\epsilon)$ and $(q,\epsilon) \in \delta(s,b,t)$, then we put the rule $N_{pq} \to a N_{rs}b$ in $G$.

It is easy to see that (1) and (2) may give rise to many meaningless grammar rules, i.e., grammar rules that will never be used to derive terminal strings. (3) seems to be the only exception at the first glance. However, it indeed does the same. Consider the following example,

Some of the grammar productions constructed according to (1), (2), (3) are:

Heading down this way, we can get the grammar for pushdown automaton $M1$.
But following (3), we also get productions like:

$N_{dn} \to N_{em}$
$N_{ek} \to N_{fj}$

These rules are useless. They can not derive any string of terminals. To understand the real cause of the problem, take $N_{dn} \to N_{em}$ for example. When the push down automaton goes from state $q_d$ to state $q_e$, it pushes a $Y$ into the stack. And a $Y$ is poped during the transition from state $q_m$ to $q_n$. But the $Y$ poped is not the same $Y$ pushed during the transition from state $q_d$ to $q_e$. At state $q_n$, the stack does not recover to its initial state before the automaton entering state $q_d$. Some additional non-terminal symbols are still in the stack.

Now let's look at another automaton M2 that recognizes the same language as M1.

Interestingly, such unnecessary rules disappear in $M2$. See the following rules:

When the push down automaton goes from state $q_d$ to state $q_e$, it pushes a $Y$ into the stack. And a $Y$ is poped during the transition from state $q_j$ to $q_c$. When entering state $q_j$, the stack may not be what it is before going to state $q_d$. But the rule $N_{dj} \to N_{ec}$ is valid. It can indeed derive terminal strings.

Actually, $M2$ will enter $q_j$ twice, with $XY\$$ and $\$$ in the stack respectively. In the former case, the automaton will loop on $q_c$. It enters the accept state until $\$$ is left on the stack.

The grammar corresponding to $M2$:

$N_{ak} \to N_{bc}$
$N_{bc} \to N_{bd}N_{dc}$
$N_{bd} \to N_{cc}$
$N_{dc} \to N_{dj}N_{jc}$
$N_{dj} \to N_{ec}$
$N_{ec} \to N_{ei}N_{ic}$
$N_{ei} \to N_{fc}$
$N_{fc} \to N_{fj}N_{jc}$
$N_{fj} \to N_{gc}$
$N_{gc} \to N_{gi}N_{ic}$
$N_{gi} \to N_{hc}$
$N_{hc} \to N_{cc}a$
$N_{jc} \to N_{cc}y$
$N_{ic} \to N_{cc}x$
$N_{cc} \to \epsilon$

In the book Introduction To Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman give another way of converting a pushdown automaton into context-free grammar. In that way, we can avoid construct meaningless rules even for pushdown automaton $M1$. The key idea is, rule like $N_{pq} \to a N_{rs}b$ is constructed if and only if in state $q$ the stack is the same as what it is before the automaton entering state $p$.

One more thing to mention about rule(3)

(3) $\forall p, q, r, s \in Q$, if $\exists a, b\in \Sigma_\epsilon, t \in \Gamma$, s.t. $(r,t) \in \delta(p,a,\epsilon)$ and $(q,\epsilon) \in \delta(s,b,t)$, then we put the rule $N_{pq} \to a N_{rs}b$ in G.

is that $t$ need not to be $b$. We will give an example, though it is kind of weird.

Reference

[1] Introduction To The Theory Of Computation, 2nd Edition, by Michael Sipser