FIT2014 Theory of Computation Lecture 8 Kleene’s Theorem. I. Regexp -3mu NFA -3mu FA
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 8
Kleene’s Theorem. I.
Regexp −→ NFA −→ FA
slides by Graham Farr
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 / 28
Overview
I Questions
I Kleene’s Theorem
I Convert Regular Expressions to NFA
I Convert NFA to FA
I Next lecture:
Convert FA to Regular Expression
Stephen Cole Kleene (1909–1994)
https://mathshistory.st-andrews.
ac.uk/Biographies/Kleene/
2 / 28
https://mathshistory.st-andrews.ac.uk/Biographies/Kleene/
https://mathshistory.st-andrews.ac.uk/Biographies/Kleene/
Questions
I Can every language which is represented by a regular expression
be described by a finite automaton?
I Can every language which is described by a finite automaton
be represented by a regular expression?
I Can every language be represented by a regular expression or a finite automaton?
{ all languages } representable by
regexp
?
recognised by
FA
?
?
3 / 28
Kleene’s Theorem
Theorem.
Any language which can be defined by
I Regular Expressions
I Finite Automata
I Nondeterministic Finite Automata (NFA)
I Generalized Nondeterministic Finite Automata (GNFA)
can be defined by any of the other methods.
4 / 28
Kleene’s Theorem
Regular Expression NFA
Finite AutomatonGNFA
5 / 28
Converting Regular Expression to NFA
Start with:
Regular Expression
Apply the following rules until all edges are labelled with a letter or ε:
6 / 28
Converting Regular Expression to NFA
∅ (R)
R
7 / 28
Converting Regular Expression to NFA
RS
R S
R ∪ S
R
S
8 / 28
Converting Regular Expression to NFA
R∗
ε ε
R
9 / 28
Converting Regular Expression to NFA
The two ε transitions
are necessary,
in general.
Here, you can’t
match PR∗Q
or SR∗T ,
in general.
So the R loop
cannot be at
left node or
right node.
P
Q
S
T
P
Q
S
T
R∗
ε ε
R
10 / 28
Converting Regular Expression to NFA. Example: a((ab)∗ ∪ (ba))b∗
a((ab)∗ ∪ (ba))b∗
a (ab)
∗ ∪ (ba) b∗
a
(ab)∗
ba
b∗
11 / 28
a
(ab)∗
b a
b∗
a
ε ε
ab
b a
b∗
12 / 28
a
ε ε
ab
b a
ε ε
b
a
ε ε
b a
ε ε
ba b
13 / 28
Converting a NFA to a FA
Complexity?
How reversible is this construction?
14 / 28
Kleene’s Theorem
Regular Expression NFA
Finite AutomatonGNFA
15 / 28
Converting a NFA to a FA
In a FA:
I Any string w traces a unique path, starting from the Start State and ending at
some unique state, which we’ll call endState(w).
I The string w is accepted if endState(w) is a Final State, otherwise it is rejected.
I endState(ε) = Start State.
In a NFA:
I Any string w traces a set of paths, starting from the Start State and ending at
some set of states, which we’ll call endStates(w).
I The set might have zero, one or more members.
I The string w is accepted if endStates(w) contains a Final State, otherwise it is
rejected.
I endStates(ε) = { Start State } if there are no ε transitions.
16 / 28
Converting a NFA to a FA
1 2 3
a,b
b a,b
endStates(ab) = {1, 2}
endStates(aba) = {1, 3}
In general, if w is a string and x is a single letter, then
endStates(wx) = {q : for some state p ∈ endStates(w), there is a transition p x−→ q}
. . . provided there are no empty transitions.
This suggests part of a method for constructing endStates(w) for all strings w .
17 / 28
Converting a NFA to a FA
Idea:
sets of states in the NFA −→ states in the FA.
Informally (and assuming no empty transitions, for the time being):
Start with the one-element set { Start State }.
I This is endStates(ε).
I It’s the set of NFA-states we can possibly be in at the very start.
Construct endStates(a), the set of all states we could then get to by reading a single a.
Construct endStates(b), the set of all states we could then get to by reading a single b.
For each set of states, X , that we construct:
I find the set of states we can get to from X , by reading a single a.
I find the set of states we can get to from X , by reading a single b.
Keep doing this, until we no longer get any new sets of states.
18 / 28
Converting a NFA to a FA
1 2 3
a,b
b a,b
state a b
Start {1}
state a b
Start {1} {1} {1,2}
{1,2}
state a b
Start {1} {1} {1,2}
{1,2} {1,3} {1,2,3}
{1,3}
{1,2,3}
· · ·
state a b
Start {1} {1} {1,2}
{1,2} {1,3} {1,2,3}
{1,3} {1} {1,2}
{1,2,3}
· · · · · ·
19 / 28
Converting a NFA to a FA
1 2 3
a,b
b a,b
· · ·
state a b
Start {1} {1} {1,2}
{1,2} {1,3} {1,2,3}
{1,3} {1} {1,2}
{1,2,3} {1,3} {1,2,3}
state a b
Start {1} {1} {1,2}
{1,2} {1,3} {1,2,3}
Final {1,3} {1} {1,2}
Final {1,2,3} {1,3} {1,2,3}
20 / 28
Converting a NFA to a FA
1 2 3
a,b
b a,b
state a b
Start {1} {1} {1,2}
{1,2} {1,3} {1,2,3}
Final {1,3} {1} {1,2}
Final {1,2,3} {1,3} {1,2,3}
{1}
{1,2}
{1,3}
{1,2,3}
a
b
a
b
a
b
a
b
21 / 28
Algorithm: Conversion of NFA without empty transitions to FA
Input: a NFA
NextSetOfStatesOfNFA := { Start State of NFA }.
Create new incomplete row in FA table, for Start State called NextSetOfStatesOfNFA.
while the FA table still has at least one incomplete row do
CurrentStateInFA := the state for the first incomplete row of the FA.
for each letter x in the alphabet do
NextSetOfStatesOfNFA :=
{q : for some NFA-state p in CurrentStateInFA, ∃ transition p x−→ q}
Write NextSetOfStatesOfNFA in table entry for row CurrentStateInFA, column x .
if NextSetOfStatesOfNFA is new then
Create new incomplete row in table, using set NextSetOfStatesOfNFA as state.
Any FA state which (as a set) contains an NFA Final State is labelled Final.
Output: the FA 22 / 28
Converting a NFA to a FA
Now suppose that the NFA might have empty transitions, q1
ε−→ q2.
These allow change of state without reading any letter of the input string.
Every time we include a new state q in NextSetOfStatesOfNFA, we also need to
include any state we can reach from it along empty transitions.
Look at all paths from q that just use ε transitions . . .
q
ε−→ q1
ε−→ q2
ε−→ · · · · · · ε−→ qi
. . . and include all states on such paths.
Modify earlier algorithm, for constructing the sets of NFA states, to take account of
empty transitions.
23 / 28
Algorithm: Conversion of NFA to FA
Input: a NFA
NextSetOfStatesOfNFA := { Start State of NFA }.
for each q ∈ NextSetOfStatesOfNFA do
Add, to NextSetOfStatesOfNFA, all states reachable from q along ε-transitions.
Create new incomplete row in FA table, for Start State called NextSetOfStatesOfNFA.
while the FA table still has at least one incomplete row do
CurrentStateInFA := the state for the first incomplete row of the FA.
for each letter x in the alphabet do
NextSetOfStatesOfNFA :=
{q : for some NFA-state p in CurrentStateInFA, ∃ transition p x−→ q}
for each q ∈ NextSetOfStatesOfNFA do
Add, to NextSetOfStatesOfNFA, all states reachable from q along ε-transitions.
Write NextSetOfStatesOfNFA in table entry for row CurrentStateInFA, column x .
if NextSetOfStatesOfNFA is new then
Create new incomplete row in table, using set NextSetOfStatesOfNFA as state.
Any FA state which (as a set) contains an NFA Final State is labelled Final.
Output: the FA 24 / 28
Converting a NFA to a FA
1 2 3
a
ε
b
ε
state a b
Start {1,2,3}
state a b
Start {1,2,3} {1,2,3} {2,3}
{2,3}
state a b
Start {1,2,3} {1,2,3} {2,3}
{2,3} ∅ {2,3}
∅
state a b
Start {1,2,3} {1,2,3} {2,3}
{2,3} ∅ {2,3}
∅ ∅ ∅
25 / 28
Converting a NFA to a FA
1 2 3
a
ε
b
ε
state a b
Start {1,2,3} {1,2,3} {2,3}
{2,3} ∅ {2,3}
∅ ∅ ∅ {1,2,3} {2,3} ∅
a
b
b
a
a,b
26 / 28
Converting a NFA to a FA
Complexity?
I Think about how many states the FA may have,
as a function of the number of states in the NFA.
27 / 28
Revision
Today:
I Understand Kleene’s Theorem
I Be able to convert Regular Expression −→ NFA
I Be able to convert NFA −→ Finite Automaton
Next lecture:
I Be able to convert FA −→ Regular Expression
Reading:
Sipser, Ch 1, especially pp. 54–58, 66–69.
28 / 28