FIT2014 Theory of Computation Lecture 9 Kleene’s Theorem. II. FA -3mu Regexp
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 9
Kleene’s Theorem. II.
FA −→ Regexp
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
Previous lecture:
I Convert Regular Expressions to NFA
I Convert NFA to FA
Today:
I Generalised Nondeterministic Finite Automata
I Convert FA to GNFA
I Convert GNFA to Regular Expression
2 / 23
Kleene’s Theorem
Regular Expression NFA
Finite AutomatonGNFA
3 / 23
Generalised Nondeterministic Finite Automaton (GNFA)
Definitions
A Generalised Nondeterministic Finite Automaton (GNFA) is defined as for an
NFA except that transitions may be labelled by regular expressions, not just by single
letters.
A string w is accepted by a given GNFA if it can be divided into substrings,
w = w1 · · ·wk , such that there is some sequence of transitions, starting at the Start
State, finishing at the Final State, and labelled by regular expressions R1, . . . ,Rk , such
that, for all i , wi matches Ri .
If a string w is not accepted by the GNFA, then it is rejected.
4 / 23
Standard GNFA
A standard GNFA is a GNFA in which:
I there is just one Final State, and it is not the Start State;
I the Start State has no incoming transitions and the Final State has no outgoing
transitions.
Notes:
I Sometimes (e.g., in Sipser), standard GNFAs are required to have arcs going
between every pair of states, subject to the prohibition on incoming arcs into the
Start State and outgoing arcs from the Final State. If a transition actually cannot
occur between two states, then the arc between them is labelled by the regular
expression ∅, which prevents the transition from being used.
I This is not really needed, for the algorithm we will describe. But it may make
proving properties of that algorithm easier.
I Standard GNFAs are sometimes called GNFAs of “special form” in Sipser.
5 / 23
From FA to Standard GNFA
Given a FA (or an NFA):
1. Ensure there is a single Final State, with incoming arcs only.
I If necessary: add new Final State, add new transitions labelled ε from the previous
Final States to this new one, and make those states no longer Final.
2. Ensure there is a single Start State, with outgoing arcs only.
I If necessary: add a new Start State, add new transitions labelled ε from this new
Start State to the previous Start States, and make those states no longer Start
states.
The letters on the arcs of the FA/NFA are already regular expressions in their own
right.
The GNFA constructed by this process accepts the same language as the original FA.
6 / 23
Kleene’s Theorem
Regular Expression NFA
Finite AutomatonGNFA
7 / 23
From Standard GNFA to Regular Expression
Starting with a Standard GNFA, we convert it to an equivalent GNFA with one fewer
state.
We keep doing this until we have a GNFA with just a Start State, a Final State, and
one transition:
R
The regular expression R on this transition defines the same language as the original
GNFA.
8 / 23
From GNFA to Regular Expression
Notation:
q some non-Start, non-Final state.
qin any non-Final state.
Rin the regular expression on the transition from qin to q.
qout any non-Start state.
Rout the regular expression on the transition from q to qout.
Rloop the regular expression on the transition from q to itself.
Rdirect the regular expression on the transition from qin to qout.
9 / 23
From GNFA to Regular Expression
qin qout
q
Rout
Rloop
qin qout
q
Rdirect ∪ (RinR∗loopRout)
Rloop
10 / 23
From GNFA to Regular Expression
Ensure this replacement is done for all qin, qout.
Then q is removed, and we have an equivalent GNFA to the one we started with.
Keep doing this whole procedure, removing one state at a time, until you are left with
just the Start State and the Final State, with a single transition between them.
The regular expression on this transition is the one you want.
It matches precisely those strings accepted by the original GNFA.
Examples: Sipser, pp. 75–76.
11 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b∪ (aa∗a)
a
a
a
b
ε
b
b
12 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b ∪ (aa∗a)
a
a
a
b
ε
b
b∪ (ba∗a)
13 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b ∪ (aa∗a)
a
a
a
b
ε∪ (ba∗b)
b
b ∪ (ba∗a)
14 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b ∪ (aa∗a)
a∪ (aa∗b)
a
a
b
ε ∪ (ba∗b)
b
b ∪ (ba∗a)
15 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b ∪ (aa∗a)
a ∪ (aa∗b)
a
a
b
ε ∪ (ba∗b)
b
b ∪ (ba∗a)
16 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b ∪ (aa∗a)
a ∪ (aa∗b)
a
a
b
ε ∪ (ba∗b)
b
b ∪ (ba∗a)
17 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b ∪ (aa∗a)
a
a
b
ε ∪ (ba∗b)
b
b ∪ (ba∗a)
a ∪ (aa∗b)
∪ ((b ∪ (aa∗a))(b ∪ (ba∗a))∗(ε ∪ (ba∗b)))
18 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b ∪ (aa∗a)
a
a
b
ε ∪ (ba∗b)
b
b ∪ (ba∗a)
a ∪ (aa∗b)
∪ ((b ∪ (aa∗a))(b ∪ (ba∗a))∗(ε ∪ (ba∗b)))
19 / 23
From GNFA to Regular Expression
1
2
3
4
a
b
a
a
a
b
ε
b
b
1
2
3
4
a
b ∪ (aa∗a)
a
a
b
ε ∪ (ba∗b)
b
b ∪ (ba∗a)
a ∪ (aa∗b)
∪ ((b ∪ (aa∗a))(b ∪ (ba∗a))∗(ε ∪ (ba∗b)))
20 / 23
From GNFA to Regular Expression
Complexity?
For FIT2004 students:
Compare this algorithm with the Floyd-Warshall algorithm for the All Pairs Shortest
Path problem.
21 / 23
Questions
I Can every language which is represented by a regular expression
be described by a finite automaton? YES
I Can every language which is described by a finite automaton
be represented by a regular expression? YES
I Can every language be represented by a regular expression or a finite automaton?
{ all languages } representable by
regexp
⇐⇒ recognised by
FA
?
22 / 23
Revision
Previous lecture:
I Understand Kleene’s Theorem
I Be able to convert Regular Expressions into NFA
I Be able to convert NFA into a Finite Automaton
Today:
I Be able to convert a FA into a Regular Expression
Reference
Sipser, Ch. 1, especially pp. 66, 69–76.
23 / 23