FIT2014 Theory of Computation Lecture 13 (A) Regular Grammars, (B) Pushdown Automata
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 13
(A) Regular Grammars,
(B) Pushdown Automata
slides by Graham Farr
based in part on previous slides by David Albrecht
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 {Regular Languages } ⊆ {CFLs }
I Pushdown Automaton (PDA)
I Constructing PDA to accept a Regular Grammar
2 / 23
Is every Regular Language
a Context-Free Language?
all languages
CFLs
regular
languages
?
?
3 / 23
NFA to CFG
Input: an NFA
1. Name all the states in the NFA by a symbol.
I Call the Start State S .
2. For each ordered pair of states X ,Y linked by an arc labelled z ,
create production rule X −→ zY
3. For each Final State X , create production rule X −→ ε.
Output: the CFG consisting of
I terminals: the alphabet of the NFA;
I non-terminals: the symbols representing the states of the NFA;
I all the production rules we have created.
4 / 23
NFA to CFG
X Y X X Y X
z
X −→ zY
z
X −→ z X
ε
X −→ Y X −→ ε
5 / 23
NFA to CFG: Example
S
X
Y
b
b
ba
a
S −→ aS
S −→ bX
S −→ bY
X −→ bY
Y −→ aY
X −→ ε
Y −→ ε
6 / 23
Regular Grammar
Definitions
Semiwords are of the form:
terminal terminal . . . terminal Nonterminal
A CFG is called a Regular Grammar if all its production rules are in one of the
following forms:
Nonterminal −→ semiword
or
Nonterminal −→ string of terminals
7 / 23
Theorem.
Every Regular Language can be generated
by a Regular Grammar.
Proof idea:
A regular language is recognised by
some NFA
Observe that our construction NFA−→ CFG
produces a regular grammar.
Theorem.
Every Regular Grammar generates
a Regular Language.
Proof: Exercise.
all languages
CFLs
regular
languages
?
8 / 23
Overview
Is there a state machine for Context Free Languages?
9 / 23
Pushdown Automaton (PDA)
I A Nondeterministic Finite Automaton (NFA) with a Stack.
I Can be used to represent Context Free Languages.
I Many parsers use a Pushdown Automaton
I . . . including the parsers generated by some compiler-compilers.
10 / 23
Pushdown Automaton (PDA)
ε, ε→ ε
ε, ε→ $
b, a→ ε
ε, $→ ε
a, ε→ a
b, a→ ε
11 / 23
Pushdown Automaton (PDA)
The Stack
I storage for letters
I serves as a memory
I two operations:
I Push: puts a letter on the top of the stack
I Pop: takes a letter off the top of the stack.
12 / 23
Pushdown Automaton (PDA)
Transitions
x , y −→ z
which means when the machine is reading x , if there is a y on top of the stack, it is
replaced by z .
I If x is ε then no letter is read from the tape.
I If y is ε then no letter is popped from the stack.
I If z is ε then no letter is pushed onto the stack.
13 / 23
Pushdown Automaton (PDA)
ε, ε→ ε
ε, ε→ $
b, a→ ε
ε, $→ ε
a, ε→ a
b, a→ ε
14 / 23
Pushdown Automaton (PDA)
A Pushdown Automaton consists of:
I an input alphabet: the set of possible input letters.
I a stack alphabet: the set of possible stack letters.
I a stack
I a finite set of states
I One called the Start State
I Some (maybe none) called Final States
I A set of transitions between states
x , y −→ z
which means when the machine is reading x , if there is a y on top of the stack, it
is replaced by z .
15 / 23
Pushdown Automaton (PDA)
Definitions
A string is accepted by a PDA if there exists at least one path through the PDA for
this string that ends in a Final State.
A string is rejected by a PDA if for all paths through the PDA for this string, the
PDA either crashes or ends in a non-Final State.
The set of strings accepted by the PDA is called the language accepted by the PDA.
16 / 23
HALF-AND-HALF
HALF-AND-HALF := {anbn : n ≥ 0}
= {ε, ab, aabb, aaabbb, . . .}
Using the Pumping Lemma we showed that this language was non-regular.
Consider:
S −→ aS b | ε
So it is a Context-Free Language.
17 / 23
PDA for HALF-AND-HALF
Input: aaabbb
Stack:
a
a
a
$
ε, ε→ ε
ε, ε→ $
b, a→ ε
ε, $→ ε
a, ε→ a
b, a→ ε
ε, ε→ $
a, ε→ a
b, a→ $
b, a→ ε
ε, $→ ε
18 / 23
PDA for PARENTHESES
1. S → ε
2. S → (S)
3.
ε, ε→ ε
ε, ε→ $
), (→ ε
ε, $→ ε
(, ε→ (
), (→ ε
19 / 23
PDA for PARENTHESES
1. S → ε
2. S → (S)
3. S → SS
ε, ε→ ε
ε, ε→ $
ε, $→ ε
(, ε→ (
), (→ ε
), (→ ε(, ε→ (
20 / 23
Regular Languages ⊆ languages accepted by PDAs
Exercise:
I What do you have to do to restrict a PDA so that it is just an NFA?
An NFA is a special case of a PDA.
So
{regular languages} ⊆ {languages recognised by a PDA}
21 / 23
Regular Languages ⊆ languages accepted by PDAs
S −→ aS | bY | bX
X −→ bY | ε
Y −→ aY | ε
ε, ε→ $ ε, ε→ S ε, $→ ε
a, S → S
b, S → Y
b, S → X
ε,X → ε
b,X → Y
ε,Y → ε
a,Y → Y
22 / 23
Revision
Things to think about:
I Which of the PDAs we’ve met are deterministic?
I Suppose we plot stack height against time for our PDA for the Dyck language.
What would it look like?
I How can we construct, from a given CFG, a PDA for the same language?
I How can we construct, from a given PDA, a CFG for the same language?
Reading: Sipser, Section 2.2, pp. 111–116.
23 / 23