Context Free Languages and Pushdown Automata
Context Free Languages and
Pushdown Automata
Dr. John McDonough
Spoken Language Systems
Saarland University
June 29, 2009
Context Free Languages and Pushdown Automata
Introduction
During the lecture of June 8, we learned that some
languages are not regular.
We then consider a richer class of languages known as
context free grammars.
We demonstrated that context free grammars subsume
regular languages, but that the converse is not true.
In this lecture, we discuss the “natural” automata for
context free grammars, namely, pushdown automata
(PDA).
We will discuss both deterministic and nondeterministic
versions of PDAs.
We will also discuss acceptance criteria for PDAs.
Coverage: Hopcroft and Ullman (1979) Chapter 5.
Context Free Languages and Pushdown Automata
Context Free Grammars
There are four components of a context free grammar
G = (V , T , P, S):
1 There is a set T of terminals and all strings w in L can be
expressed as w ∈ T ∗ . Σ is the set of terminals.
2 There is a set V of variables or non-terminals. Each
variable represents a set of possible strings.
3 There is a start symbol S.
4 There is a set P of productions that represent the recursive
nature of the language.
Context Free Languages and Pushdown Automata
Productions
Every production consists of:
1 A variable A ∈ V , the head of the production, which is
partly defined through the production.
2 The production symbol →.
3 the tail of the production, a string α ∈ (T ∪ V )∗ of one or
more terminals and non-terminals.
Context Free Languages and Pushdown Automata
Derivations and Languages
Let us formally define the language generated by
G = (V , T , P, S).
If A → β is a production of P and α and γ are any strings in
(V ∪ T )∗ , then αAγ ⇒ αβγ.
G
Two strings are related by ⇒ exactly when the second is
G
obtained from the first by a single application of some
production.
Context Free Languages and Pushdown Automata
Chains of Derivations
Suppose that α1 , α2 , . . . , αm ∈ (V ∪ T )∗ , m ≥ 1, and
α1 ⇒ α2 , α2 ⇒ α3 , . . . , αm−1 ⇒ αm .
G G G
∗
Then α1 ⇒ αm or α1 derives αm in grammar G.
G
∗
In other words, ⇒ is the reflexive, transitive closure of ⇒.
G G
∗
Alternatively, α ⇒ β if β follows from α by applications of
G
zero or more more productions of P.
i
If α derives β in exactly i steps, then we write α ⇒ β.
Context Free Languages and Pushdown Automata
Language Generated by G
The language generated by G, denoted as L(G), is
∗
{w|w ∈ T ∗ and S ⇒ w}.
G
In other words, a string w is in L(G) if:
1 w contains only terminals.
2 w can be derived from S in one or more steps.
L is a context free language (CFL) if it is L(G) for some
CFG G.
∗
A string α ∈ (T ∪ V )∗ is a sentential form if S ⇒ α.
G
Two grammars G1 and G2 are equivalent if L(G1 ) = L(G2 ).
Context Free Languages and Pushdown Automata
Simple Example of a CFL
Consider a grammar G = (V , T , P, S), where V = {S},
T = {a, b}, and P = {S → aSb, S → ab}.
In other words, S is the only variable, a and b are the only
terminals, and there are two productions: S → aSb and S → ab.
Let us apply the first production n − 1 times, followed by the
second production:
S ⇒ aSb ⇒ aaSbb ⇒ a3 Sb3 ⇒ · · · ⇒ an−1 Sbn−1 ⇒ an bn .
Clearly, the only strings w ∈ L(G) are of the form w = an bn for
some n ≥ 1.
As soon as the second production is applied, no further
productions are possible.
Context Free Languages and Pushdown Automata
Another Simple Example
The set L = {wcw R |w in (0 + 1)∗ } is a CFL generated by
the grammar
S → 0S0|1S1|c.
As shown previously, it can be demonstrated that L is not
regular through the pumping lemma.
To construct an automaton for accepting L, we need a finite
control with two states, q1 and q2 , and a stack on which we
place blue, green, and red plates.
Next we describe the operation of the device.
Context Free Languages and Pushdown Automata
Operation of the Automaton
1 The machine starts in state q1 with one red plate on the
stack.
2 In state q1 : input 0 → place blue plate on stack;
input 1 → place green plate on stack.
3 For input c: move from state q1 to state q2 .
4 In state q2 : input 0 → remove blue plate from stack;
input 1 → remove green plate from stack.
5 If the device is in state q2 and a red plate appears on the
top of the stack, it is removed and the machine halts.
6 In all other cases, the device makes no move.
Context Free Languages and Pushdown Automata
Table of Instructions
Top Plate State Input
0 1 2
Blue q1 Add blue plate. Add green plate. Go to state q2
q2 Remove top plate. — —
Green q1 Add blue plate. Add green plate. Go to state q2
q2 — Remove top plate. —
Red q1 Add blue plate. Add green plate. Go to state q2
q2 Without waiting for next input, remove top plate.
Context Free Languages and Pushdown Automata
Definition: Pushdown Automaton
A pushdown automaton M is a system (Q, Σ, Γ, δ, q0 , Z0 , F ),
where
1 Q is a finite set of states;
2 Σ is an alphabet called the input alphabet;
3 Γ is an alphabet called the stack alphabet;
4 q0 ∈ Q is the initial state;
5 Z0 ∈ Γ is a particular stack symbol called the start symbol;
6 F ⊆ Q is the set of final states;
7 δ is a mapping from Q × (Σ ∪ {}) × Γ to finite subsets of
Q × Γ∗ .
Context Free Languages and Pushdown Automata
Moves
Let us denote:
q and pi for all 1 ≤ i ≤ m as states;
a ∈ Σ is an input symbol;
Z ∈ Γ is a stack symbol;
γi ∈ Γ∗ for 1 ≤ i ≤ m are sequences of stack symbols;
Then δ(q, a, Z ) = {(p1 , γ1 ), (p2 , γ2 ), . . . , (pm , γm )} denotes that:
the PDA is in state q;
the input symbol is a;
the top symbol on the stack is Z ; and that
the automaton can enter state qi for all 1 ≤ i ≤ m;
replace symbol Z by γi ;
advance the input head one symbol.
The leftmost (rightmost) symbol of γi is placed highest
(lowest) on the stack.
Context Free Languages and Pushdown Automata
Moves (cont’d.)
The interpretation of
δ(q, , Z ) = {(p1 , γ1 ), (p2 , γ2 ), . . . , (pm , γm )}
is that:
the PDA is in state q;
Z is the top symbol on the stack;
inpependent of the symbol being scanned, the PDA can
replace Z by γi for all 1 ≤ i ≤ m; and
enter state pi .
Context Free Languages and Pushdown Automata
CFG for L = {wcw R |w in (0 + 1)∗ }
M = ({q1 , q2 }, {0, 1, c}, {R, G, B}, δ, q1 , R, ∅)
δ(q1 , 0, R) = {(q1 , BR)} δ(q1 , 1, R) = {(q1 , GR)}
δ(q1 , 0, B) = {(q1 , BB)} δ(q1 , 1, B) = {(q1 , GB)}
δ(q1 , 0, G) = {(q1 , BG)} δ(q1 , 1, G) = {(q1 , GG)}
δ(q1 , c, R) = {(q2 , R)}
δ(q1 , c, B) = {(q2 , B)}
δ(q1 , c, G) = {(q2 , G)}
δ(q2 , 0, B) = {(q2 , )} δ(q2 , 1, G) = {(q2 , )}
δ(q2 , , R) = {(q2 , )}
Figure: Formal pushdown automaton accepting
L = {wcw R |w in (0 + 1)∗ } by empty stack.
Context Free Languages and Pushdown Automata
Instantaneous Descriptions
The instantaneous description (ID) records the state and
stack contents of a PDA.
It also records the unexpended input.
Formally define the ID as the triple (q, w, γ) where
q is a state;
w is a string if input symbols;
γ is a string of stack symbols.
For automaton M, we write (q, aw, Z α) ` (p, w, βα) if
M
δ(q, a, Z ) contains (p, β).
That (q1 , BG) is in δ(q1 , 0, G) tells us that
(q1 , 011, GGR) ` (q1 , 11, BGGR).
Context Free Languages and Pushdown Automata
Accepted Languages
For a PDA M = (Q, Σ, Γ, δ, q0 , Z0 , F ) we define the
language L(M) accepted by final state as
∗
{w|(q0 , w, Z0 ) ` (p, , γ) for some p ∈ F and γ ∈ Γ∗ }.
We define the language N(M) accepted by empty stack as
∗
{w|(q0 , w, Z0 ) ` (p, , ) for some p ∈ Q}.
Context Free Languages and Pushdown Automata
CFG for L = {ww R |w ∈ (0 + 1)∗ }
M = ({q1 , q2 }, {0, 1}, {R, G, B}, δ, q1 , R, ∅)
δ(q1 , 0, R) = {(q1 , BR)} δ(q1 , 1, G) = {(q1 , GG)}
δ(q1 , 1, R) = {(q1 , GR)} δ(q2 , 0, B) = {(q2 , )}
δ(q1 , 0, B) = {(q1 , BB), (q2 , )} δ(q2 , 1, G) = {(q2 , )}
δ(q1 , 0, G) = {(q1 , BG)} δ(q1 , , R) = {(q2 , )}
δ(q1 , 1, B) = {(q1 , GB)} δ(q2 , , R) = {(q2 , )}
Figure: A nondeterministic PDA that accepts {ww R |w ∈ (0 + 1)∗ } by
empty stack.
Context Free Languages and Pushdown Automata
Definition: Deterministic PDA
We will say that a PDA M = {Q, Σ, Γ, δ, q0 , Z0 , F )} is
deterministic iff
1 for each q ∈ Q and Z ∈ Γ, whenever δ(q, , Z ) 6∈ ∅, then
δ(q, a, Z ) = ∅ for all a ∈ Σ;
2 for no q ∈ Q, Z ∈ Γ, and a ∈ Σ ∪ {} does δ(q, a, Z )
contain more than a single element.
Context Free Languages and Pushdown Automata
Summary
In this lecture, we examined the natural automata for
context free grammars, namely, pushdown automata.
We defined two criteria of acceptance for PDAs:
1 Acceptance by final state;
2 Acceptance by empty stack.
We constructed a deterministic pushdown automata for the
language {wcw R |w ∈ (0 + 1)∗ }.
We constructed a nondeterministic pushdown automata for
the language {ww R |w ∈ (0 + 1)∗ }.
Next lecture, we will see how PDAs can be used to parse
context free grammars.
