CSI 3104 /Winter 2006: Introduction to Formal Languages

Chapter 7: Kleene’s Theorem

Chapter 7: Kleene’s Theorem

Regular expressions, Finite Automata, transition

graphs are all the same!!

Zaguia/Stojmenovic 1
 Chapter 7: Kleene’s Theorem

 Method of proof
Let A,B,C be sets such that AB, BC, CA.
Then A=B=C.

Remark: Regular expressions, finite

automata, and transition graphs each define a
set of languages.
Zaguia/Stojmenovic 2
 Chapter 7: Kleene’s Theorem

Kleene’s Theorem
Any language that can be defined by a regular
expression, or finite automaton, or transition
graph can be defined by all three methods.

Zaguia/Stojmenovic 3
 Chapter 7: Kleene’s Theorem

Proof of Kleen’s theorem: It is enough to prove each of the

lemmas below.
Lemma 1: Every language that can be defined by a finite
automaton can also be defined by a transition graph.

Lemma 2: Every language that can be defined by a

transition graph can also be defined by a regular
expression.

Lemma 3: Every language that can be defined by a regular

expression can also be defined by a finite automaton.
FA  TG  RE  FA

Zaguia/Stojmenovic 4
 Chapter 7: Kleene’s Theorem

Lemma 1: Every language that can be defined by a finite

automaton can also be defined by a transition graph.
Proof: By definition, every finite automaton is a transition
graph.

Lemma 2: Every language that can be defined by a transition

graph can also be defined by a regular expression.
Proof: By constructive algorithm, which works
1. for every transition graph
2. in a finite number of steps

Zaguia/Stojmenovic 5
 Chapter 7: Kleene’s Theorem

1st step: transform to a transition graph with a single start state.

ab
1
–
b 2 … 3–
5 aa 4 …
–

 1 b 2 …
–
 3
ab 4 …
 5 aa
Zaguia/Stojmenovic 6
 Chapter 7: Kleene’s Theorem

2nd step: and a single final state b

b 9

9+ … aa
… aa
+

b aba 1 
aba 12 2
+ b
Result is an equivalent transition graph, of the form:
 
–


…  +

Zaguia/Stojmenovic 7
 Chapter 7: Kleene’s Theorem

3a. Combine edges that have the same starting and ending state.

r1
r1+ r2+ r3
… x …
r3 r2
… x …
r1
… 3 7 … … 3
r1 + r2
7 …
r2
Zaguia/Stojmenovic 8
 Chapter 7: Kleene’s Theorem

3a. Combine edges

r1
r2
– … +
r35

–
r1+r2+ …+r 35
+

Zaguia/Stojmenovic 9
 Chapter 7: Kleene’s Theorem

3b. Eliminate states one by one:

bypass and state elimination operation

… 1
r1
2
r3
3 …… 1
r1r 3
3 …
r2

… 1
r1
2
r3
3 … … 1
r1r2*r3
3 …
Zaguia/Stojmenovic 10
 Chapter 7: Kleene’s Theorem

Bypass state 2 3 …
r2 r3
One incoming
… 1
r1
2
r4 4 … edge to state 2
r5
5 …
r1r2*r3 3 …
… 1
r1r2*r4
4 …
r1r2*r5 5 …
Zaguia/Stojmenovic 11
 Chapter 7: Kleene’s Theorem

1 ab a ba 4
 

– 2 +
bbb
 3 b 5 

bypass state 2,
paths through state 2: 1 24, 125, 324, 325

Zaguia/Stojmenovic 12
 Chapter 7: Kleene’s Theorem

1 ab a ba 4
 

– 2 +
bbb
 3 b 5 

aba*ba 4
1
 
aba*b
– +

 3
bbba*b 5 
bbba*ba
Zaguia/Stojmenovic 13
 Chapter 7: Kleene’s Theorem

r3 1
7 r1 r4 1

… 2
r5 4 …
r2 r6
Even with many paths
9 5
through state 2,
r1r3*r4 1 always an equivalent
7 GTG.
r1r3*r5 1
r1r3*r6
… r2r3*r4
4 …
r2r3*r5
9 5
r2r3*r6
Zaguia/Stojmenovic 14
 Chapter 7: Kleene’s Theorem

Special cases r2
r3
… 1 2
r4
3 …
r1
3  2 1, 121

r 1 r2* r 3

… 1
r4 r2* r3
3 …

Zaguia/Stojmenovic 15
 Chapter 7: Kleene’s Theorem

r8
r4 3 21,
r2 r5
r1
1 2 3 r7 323,
r3 r6 1
21,
r9
123
r8+r2 r4*r5

r1+r2 r4*r3 1 3 r7+r6 r4*r5

r9+r6 r4*r3
Zaguia/Stojmenovic 16
 Chapter 7: Kleene’s Theorem

Example 1
+
a,b aa

– aa,bb

bb
+

– +
(aa+bb)(a+b)*(aa+bb)

Zaguia/Stojmenovic 17
 Chapter 7: Kleene’s Theorem

EXAMPLE2: EVEN-EVEN
aa,bb aa,bb – aa+bb aa+bb
ab,ba  ab+ba
+ 1 2
ab,ba +  ab+ba
aa+bb
 1  +  1  +
– –

(ab+ba)(aa+bb)*(ab+ba) (aa+bb)+(ab+ba)(aa+bb)*(ab+ba)

– +
[(aa+bb)+(ab+ba)(aa+bb)*(ab+ba)]*
Zaguia/Stojmenovic 18
 Chapter 7: Kleene’s Theorem

Transition Graph  Regular Expression

 Algorithm (and proof)
1. Add (if necessary) a unique start state without incoming edges and a
unique final state without outgoing edges.
For each state that is not a start state or a final state, repeat steps 2 and 3.
2. Do a bypass and state elimination operation.
3. Combine edges that have the same starting and ending state.
4. Combine the edges between the start state and the final state. The
label on the only remaining edge is the regular expression result. If
there is none, the regular expression is .

Zaguia/Stojmenovic 19
 Chapter 7: Kleene’s Theorem

Lemma 3: Every language that can be defined

by a regular expression can also be defined by a
finite automaton.

Proof: By constructive algorithm starting from

the recursive definition of regular expressions,
we build FA.

Zaguia/Stojmenovic 20
 Chapter 7: Kleene’s Theorem

 Remember: Given an alphabet , the set of regular

expressions is defined by the following rules.
1. For every letter in , the letter written in bold is

a regular expression. Λ is a regular expression.

2. If r1 and r2 are regular expressions, so is r1+r2.

3. If r1 and r2 are regular expressions, so is r1 r2.

4. If r1 is a regular expression, so is r1*.
5. Nothing else is a regular expression.

Zaguia/Stojmenovic 21
 Chapter 7: Kleene’s Theorem

Lemma 3: Every language that can be defined by a regular

expression can also be defined by a finite automaton.
Proof: By constructive algorithm starting from the recursive definition of regular
expressions
1. There is an FA that accepts only the empty word (Λ) and an FA that accepts
only a single letter.
 If there is an FA that accepts the language defined by r1 and an FA that
accepts the language defined by r2, then there is an FA that accepts the
language r1+r2.
 If there is an FA that accepts the language defined by r1 and an FA that
accepts the language defined by r2, then there is an FA that accepts the
language defined by their concatenation r1r2.
 If there is an FA that accepts the language defined by r then there is an FA
that accepts the language defined by r*.
Thus for every regular expression, we can construct a FA.

Zaguia/Stojmenovic 22
 Chapter 7: Kleene’s Theorem

Build a finite automaton that accepts the language: (a+b)*(aa+bb)(a+b)*

Rule:
1. The letter a 1
2. The letter b 1
3. The word aa (using 1) 3
4. The word bb (using 2) 3
5. The expression aa+bb (using 3 and 4) 2
6. The expression a+b (using 1 and 2) 2
7. The expression (a+b)* (using 6) 4
8. The expression (a+b)*(aa+bb) (using 7 and 5) 3
9. The expression (a+b)*(aa+bb)(a+b)* (using 8 and 7) 3

Zaguia/Stojmenovic 23
 Chapter 7: Kleene’s Theorem

Rule 1 all 
all 
+ The language Λ

all  Only the letter x

all  except x –
x
+

all 
Zaguia/Stojmenovic 24
 Chapter 7: Kleene’s Theorem

Rule 2: r1+r2, Example 1 All word containing

b a,b
a b aa
– a a +x
x2 –x1 x2 x1
x1 3
b
b x2 x3 x1
+x3 x3 x3
+y1 y2
b a b
+y1 y3 y2
a a a a y2 y4 y1 EVEN-EVEN
b y3 y1 y4
y3 y4 y4 y2 y3
b Zaguia/Stojmenovic 25
 Combine two tables into one

New state name a b

x1 or y1 -+ z1 z2= x2 or y3 z3= x1 or y2
x2 or y3 z2 z4 z5
x1 or y2 z3 z6 z1
x3 or y1 + z4 z7 z8
x1 or y4 z5 z9 z10
x2 or y4 z6 z8 z10
x3 or y3 + z7 z4 z11
x3 or y2 + z8 z11 z4
x2 or y2 z9 z11 z1
x1 or y3 z10 z12 z5
x3 or y4 + z11 z8 z7
x2 or y1 + z12Zaguia/Stojmenovicz7 z3 26
 Chapter 7: Kleene’s Theorem

11 a
+ 8+
a a a
b b a
9 1+ 3 6
b b a b b b b
Result: r1+r2
b
a
b
12 a 10 5
b
+ 2
a b a
a 4+
7+
a Zaguia/Stojmenovic 27
 Chapter 7: Kleene’s Theorem

Algorithm 1: r1+r2
Input:
FA 1: alphabet:  states: x1, x2, x3,… start state: x1
FA 2: alphabet:  states: y1, y2, y3,… start state: y1
plus final states and transitions
The new FA:
alphabet:  states: z1, z2, z3,… start state: x1 or y1
transitions: if zi= xj or yk and xj  xnew and yk  ynew
(for input p) then znew= (xnew or ynew) for input p.
If xnew or ynew is a final state, then znew is a final state.

Zaguia/Stojmenovic 28
 Chapter 7: Kleene’s Theorem

Example 2.
b a a b
x1 a
x2+ – x1 x2 x1
– b +x2 x2 x1
(words ending in a)
a b
y1 b a b
y2+
– –y1 y1 y2
a
+y2 y1 y2
(words ending in b)

Zaguia/Stojmenovic 29
 Chapter 7: Kleene’s Theorem

b a a b
a –x1 x2 x1 algorithm 1
x1
x2+ x1 or y1
– b +x2 x2 x1
–
(words ending in a)
a b
a b –y1 y1 y2 b a
y1 b +y2 y1 y2
y2+ b b a
– a
+ +
(words ending in b) a
x1 or y2 x2 or y1
Zaguia/Stojmenovic 30
 Chapter 7: Kleene’s Theorem

 Algorithm 2: Put all pairs (xi or yj) in the

a
transition table
x1 or y1 a x1 or y2
– +

x1 or y1 x1 or y2
b b
– + b a
a
x2 or y1 x2 or y2 x2 or y1 x2 or y2
+ + + b +

Zaguia/Stojmenovic 31
 Chapter 7: Kleene’s Theorem

Rule 3: r1r2, Example 1

a,b b a,b
– +

second letter is b
a

a,b b b
a
– + odd number of a’s
a
Zaguia/Stojmenovic 32
 Chapter 7: Kleene’s Theorem

b b
a,b b a,b a
– + – +
a

a
ab|abbaa Exercize for home study
a,b abab|baa

Zaguia/Stojmenovic 33
 Chapter 7: Kleene’s Theorem

b Example 2
a,b
x1 a a x3
x2 r1: all with aa
– +
b
a b
y1 b
y2+ r2: words ending in b
–
a
b a b
a a b
z1– z2 z3 z 4+
b r1r2 a
Zaguia/Stojmenovic 34
 Chapter 7: Kleene’s Theorem

b a b
a a b
z1– z2 z3 z4 +
b a
We start by creating the states z1=x1and z2=x2
(z2, a)= x3 “we continue on AF1” OR
y1 ”we move to AF2, since x3 is a final state in AF1”
(z2, a) = x3 or y1= z3 -running FA1
(z3, a) = x3 or y1= z3
-beginning FA2
(z3, b) = x3 or y1 or y2 = z4 +
(z4, a)= x3 or y1=z3 (y1 added to x3)
(z4, b)= x3 or y1 or y2 = z4 +
-running FA2
Zaguia/Stojmenovic 35
 Chapter 7: Kleene’s Theorem

Rule 3: Concatenation: Summary of the Algorithm

1. Add a state z for every state of the first automaton that is
possible to go through before arriving at a final state.
2. Rename each final state x of FA1 as z = (x or y1), where
y1 is the start state of the second automaton.
3. Starting from the states added at step 2, add states:
x (state such that execution continues on 1st automaton)
z= OR
y (state such that execution continues on 2nd automaton}

4. Label every state that contains a final state from the

second automaton as a final state.

Zaguia/Stojmenovic 36
 State transition rule

 State z= xi or yj1 or yj2 …

 xi on a to xi’
 yj1 on a to yj1’
 yj2 to a to yj2’
 Then z on a to z’= xi’ or yj1’ or yj2’ …
 Add y1 to z if xi’ + and not listed already
 Sort yj’s and eliminate duplications in z
 z is + if at least one of its own yj’s is + on FA2

Zaguia/Stojmenovic 37
 Chapter 7: Kleene’s Theorem

Example 3
b a,b
a a
x 1+ x2+ x3 r1: no double a
b

a,b
y1
y2+ r2: odd number of letters
–
a,b

Zaguia/Stojmenovic 38
 Chapter 7: Kleene’s Theorem

x1 or y1 x2 or y2 or y1
z1 –
a z2 +

a
b
b b
a,b
z4
z3 +
+
x1 or y2 or y1 x3 or y1 or y2

r1r2: all words except 

Zaguia/Stojmenovic 39
 Chapter 7: Kleene’s Theorem

Example 4 a,b

x1– b x3
+
a r1: words starting with b
a,b
x2

a b
y1 b
y2+ r2: words ending in b
–
a

Zaguia/Stojmenovic 40
 Chapter 7: Kleene’s Theorem

z1 a
z3
– b
r1r2 a b a
a,b b
z2 z4 +
b
z1 b z2 b z4+ a z6 + a
–

a a b a
a b
r2r1 z3 b
a z5 z7 +
b
Zaguia/Stojmenovic 41
 Chapter 7: Kleene’s Theorem

Rule 4: r*, Example 1 a

a x2 b
x1+ x3+
+

b a,b

x4
a,b
r: a* + aa*b
r*: words without double b, and that do not start with b.

Zaguia/Stojmenovic 42
 Chapter 7: Kleene’s Theorem

z1=x1 ± (z1, a) = x1 or x2= z2 + (z1,b) = x4= z4

(z2,a)= x1 or x2 =z2 (z2, b)= x1 or x3 or x4= z3 +
(z3, a)=z4 (z3,b) = z4
(z3,a)= x1 or x2 or x4= z5 + (z3, b)= x4 = z4
(z5,a)= x1 or x2 or x4= z5 (z5, b)= x1 or x3 or x4= z3
a

r* z2 + a
a b a
z1
a,b z3+ z5+
+
b b
b
z4
Zaguia/Stojmenovic 43
 Chapter 7: Kleene’s Theorem

Rule 4: Kleene Star: Algorithm: case +

Given: an FA whose states are {-x1, x2, x3, …}
 Rename every +xi state in FA as xi or x1
 Make the transition table where new states may be created
 some intended xi or x1 states may be ‘expanded’ by the time they are
reached, or could be split into few states, following transitions; e.g.
x3 or x4 became x3 or x4 or x1 =z3 when reached from z2
 Add a + state.
 + states are those that contain at least one + from the original FA.

Zaguia/Stojmenovic 44
 Chapter 7: Kleene’s Theorem

Example 2 z1=x1 _
b a
(z1, a) = x1 or x2= z2 +
x1 a x2 (z1,b) = z1
– + (z2,a)= x1 or x2 =z2
b (z2, b)= x1=z1 b
Words ending in a
x1
b a b
a b a

x1 x1 or x2
+ a
– +
b
a x1 or x2
Problem with Λ: add state + +
Zaguia/Stojmenovic 45
 Chapter 7: Kleene’s Theorem

Example 3
a b a
Words with an odd number of b’s.
x1 x2
– +
b

z1 + z2 a
a
b b
a,b Λ and words with at least one b.
z3 +

Zaguia/Stojmenovic 46
 Chapter 7: Kleene’s Theorem

b
Rule 2: r1+r2
x2 a a,b
a a
x1+ b x3 y1 b y2
b b – +
a b
a
x 4+ a
a a,b x2 a
a
b y2 b x1 b
y1 – x3
+
b b
a a a
b x4+
Zaguia/Stojmenovic 47
 Chapter 7: Kleene’s Theorem

b a a
Rule 3: r1r2 w2
w1 –
+
b

b a a,b
x1 – a x2 b x3
+

b a b a a,b
a
w 1–
w b x1 a x2 b x3+
2
b
a
Zaguia/Stojmenovic 48