FIT2014 Theory of Computation Lecture 14 Context-Free Languages and
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 14
Context-Free Languages and
slides by
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 23
Overview
I CFL −→ PDA
I PDA −→ CFL
2 / 23
CFL PDA
We will show . . .
{CFLs } = { languages recognised by a PDA }
. . . in two parts:
1. {CFLs } ⊆ { languages recognised by a PDA }
2. { languages recognised by a PDA } ⊆ {CFLs }
3 / 23
CFL PDA
Theorem.
{CFLs } ⊆ { languages recognised by a PDA }
Proof outline and main ideas:
Let L be a CFL.
Let G be a CFG for L.
We need to show that there is a PDA that recognises L.
If w ∈ L then w has a leftmost derivation.
Idea: leftmost derivation may be viewed as
I growing a prefix of w that we know to be correct, and
I managing the rest of w (including all nonterminals) with a stack.
4 / 23
Leftmost derivation: stack view
Grammar fragment:
. . . . . . . . .
S −→ peX
X −→ Y cZ
Y −→ ar
Z −→ ey
. . . . . . . . .
S pearcey
=⇒ peX pearcey X
=⇒ peY cZ pearcey Y cZ
=⇒ pearcZ pearcey cZ
pearcey Z
=⇒ pearcey pearcey
5 / 23
CFL PDA
We construct the required PDA as follows.
We start with four basic states, then add more states for each production rule . . .
We’ll need a new character (not currently a terminal or non-terminal),
to mark the end of our stack.
We’ll use $.
6 / 23
CFL PDA
ε, ε→ $ ε, ε→ S ε, $→ ε
ε,X → ε
For rule:
X −→ ε ε,X → Y
For rule:
X −→ Y
ε,X → Z
ε, ε→ Y
For rule:
X −→ YZ
7 / 23
CFL PDA
ε, ε→ $ ε, ε→ S ε, $→ ε
a,X → ε
For rule:
X −→ a a,X → Y
For rule:
X −→ aY
a,X → Z
ε, ε→ Y
For rule:
X −→ aYZ
8 / 23
CFL PDA
ε, ε→ $ ε, ε→ S ε, $→ ε
For rule:
X −→ abY cZ
a,X → ε
b, ε→ ε
ε, ε→ Z
ε, ε→ c
ε, ε→ Y
9 / 23
CFL PDA
ε, ε→ $ ε, ε→ S ε, $→ ε
For terminals
a, a→ ε
b, b→ ε
c, c→ ε
…
…
If a terminal is on top of stack:
everything before it in target string
must have been read in.
So we need loop transitions
to check such letters off . . .
10 / 23
CFL PDA
This construction gives a PDA that accepts precisely those strings with a leftmost
derivation by G ,
i.e., precisely those strings with a derivation by G ,
i.e., precisely those strings in L.
Full formal proof: see Sipser, Ch. 2, Section 2.2.
Now for the other way round . . .
11 / 23
PDA CFL
Theorem.
{ languages recognised by a PDA } ⊆ {CFLs }
Proof ideas:
Let L be a langauge recognised by some PDA M.
We need to show that ∃ a CFG G that generates L.
First, we make some simple modifications to M.
Then we give productions that describe certain ways of going through the PDA . . .
First, modifications to M:
Ensure it has just one Final State,
and that the stack is empty when it reaches the Final State.
12 / 23
PDA CFL
original
PDA
ε, ε→ $
ε, ε→ ε
ε, ε→ ε
ε, ε→ ε
ε, x → ε
∀x ∈ stack alphabet
ε, $→ ε
$: new symbol
13 / 23
PDA CFL
More modifications: ensure that each transition either pushes or pops, but not both.
These are ok: x ,Y → ε x , ε→ Y
These are not: x ,Y → Z x , ε→ ε
So we change them . . .
14 / 23
PDA CFL
x ,Y → Z x , ε→ ε
new new
x ,Y → ε ε, ε→ Z x , ε→W ε,W → ε
15 / 23
PDA CFL
A string is accepted by this (modified) M if one of its paths through M
I starts in the Start State s,
I finishes in the Final State t,
I with the stack empty at start and finish.
For every pair of states p, q, define a non-terminal symbol Apq:
I intended to generate all strings which, starting at p with an empty stack,
can take some path through M which ends at q with an empty stack.
Aim: a grammar such that, for every string,
it is accepted by M ⇐⇒ it can be derived from Ast .
16 / 23
PDA CFL
Consider how a computation in M, for a string w , moves from p to q,
with empty stack at start and finish.
We have two cases:
Case 1:
The computation also has an empty stack at some other state r on the path.
Then we can break the computation from p to q into two parts:
I the first part, going from p to r (starting and ending with empty stack),
I the second part, going from r to q (starting and ending with an empty stack).
We model this with the production
Apq −→ AprArq
17 / 23
PDA CFL
p r q
x , ε→ v y , z → ε
v
a
v v z
︸ ︷︷ ︸
Apr
︸ ︷︷ ︸
−→ AprArq
18 / 23
PDA CFL
Case 2:
The computation never has an empty stack, except at p and q.
Because it starts and finishes with an empty stack:
I the first transition must push a symbol onto the stack,
I the last transition must pop a symbol from the stack,
I the two symbols must be the same (call it z)
I . . . else the stack would have to have been emptied at some stage, to remove the
first symbol before the last symbol arrives.
I and this symbol stays at the bottom of the stack the whole time.
19 / 23
PDA CFL
p p′ q′ q
x , ε→ z y , z → ε
z
a
z z
b
z z
︸ ︷︷ ︸
x
︸ ︷︷ ︸
Ap′q′
︸ ︷︷ ︸
y
Apq −→ xAp′q′y
20 / 23
PDA CFL
In the computation from p′ to q′, the stack is not empty, but it always has z sitting at
the bottom.
The “substack” above z is empty at p′ and q′.
The computation path from p′ to q′ starts and ends with a stack containing just z ,
with z on the bottom of every stack along the way.
This is equivalent to starting and ending with an empty stack.
We model this with the production
Apq −→ xAp′q′y
21 / 23
PDA CFL
Also, for each state p, add the production
App −→ ε
Finally, add the production
S −→ Ast
where, as usual, the non-terminal S is the Start symbol.
This set of productions give a CFG for L.
For formal proof (making good use of induction), see Sipser.
22 / 23
Revision
Some things to think about:
I CFG −→ PDA:
I What conditions would the CFG have to satisfy, so that the PDA we construct is
deterministic?
I If the PDA produced by this construction only has the four states we started with —
so that the extra transitions we added are all loops —
what can we say about the language we started with?
I CFG −→ PDA −→ CFG:
I If you start with a CFG and then do the construction both ways to get another CFG,
will it ever be the same as the CFG you started with?
Reading: Sipser, pp. 117–125
23 / 23