```Single Final State for NFAs
Courtesy Costas Busch - RPI
1
Any NFA can be converted
to an equivalent NFA
with a single final state
Courtesy Costas Busch - RPI
2
a
Example
NFA
b
a
b
Equivalent NFA
a
a
b
b


Courtesy Costas Busch - RPI
3
NFA
In General
Equivalent NFA



Courtesy Costas Busch - RPI
Single
final state
4
Extreme Case
NFA without final state
Without transitions
Courtesy Costas Busch - RPI
5
Properties of
Regular Languages
Courtesy Costas Busch - RPI
6
For regular languages
we will prove that:
Union:
Concatenation:
L1
and
L2
L1  L2
L1L2
Star:
L1 *
Reversal:
R
L1
Complement:
L1
Intersection:
L1  L2
Courtesy Costas Busch - RPI
Are regular
Languages
7
We say: Regular languages are closed under
Union:
Concatenation:
L1  L2
L1L2
Star:
L1 *
Reversal:
R
L1
Complement:
L1
Intersection:
L1  L2
Courtesy Costas Busch - RPI
8
Regular language
L1
LM1   L1
NFA
Regular language
L2
LM 2   L2
NFA
M1
Single final state
M2
Single final state
Courtesy Costas Busch - RPI
9
Example
n0
L1  {a b}
n
M1
a
b
M2
L2  ba
b
Courtesy Costas Busch - RPI
a
10
NFA for
L1  L2
Union
M1



M2
Courtesy Costas Busch - RPI

11
Example
NFA for
L1  L2  {a b}  {ba}
n
L1  {a b}
n
a


b

L2  {ba}
b

a
Courtesy Costas Busch - RPI
12
Concatenation
NFA for
L1L2
M1
M2

Courtesy Costas Busch - RPI

13
Example
NFA for
L1L2  {a b}{ba}  {a bba}
n
L1  {a b}
n
n
L2  {ba}
a
b

b
Courtesy Costas Busch - RPI
a

14
Star Operation
NFA for L1 *

  L1 *
M1



Courtesy Costas Busch - RPI
15
Example
NFA for
w  w1w2  wk
L1*  {a b} *
n
wi  L1

L1  {a b}
n
a


b

Courtesy Costas Busch - RPI
16
Reverse
R
NFA for L1
L1

M1
M1
1. Reverse all transitions
2. Make initial state final state
and vice versa
Courtesy Costas Busch - RPI
17
Example
M1
a
L1  {a b}
n
b
a
R
L1
 {ba }
n

M1
b
Courtesy Costas Busch - RPI
18
Complement
L1
M1
L1

M1
1. Take the DFA that accepts L1
2. Make final states non-final,
and vice-versa
Courtesy Costas Busch - RPI
19
Example
M1
a, b
a
L1  {a b}
n
b
L1  {a, b} * {a b}
n
a, b

M1
a, b
a
b
Courtesy Costas Busch - RPI
a, b
20
Intersection
DeMorgan’s Law:
L1  L2  L1  L2
L1 , L2
regular
L1 , L2
regular
L1  L2
regular
L1  L2
regular
L1  L2
regular
Courtesy Costas Busch - RPI
21
Example
L1  {a b} regular
n
L2  {ab, ba} regular
Courtesy Costas Busch - RPI
L1  L2  {ab}
regular
22
Regular Expressions
Courtesy Costas Busch - RPI
23
Regular Expressions
Regular expressions
describe regular languages
Example:
( a  b  c) *
describes the language
a, bc*   , a, bc, aa, abc, bca,...
Courtesy Costas Busch - RPI
24
Recursive Definition
Primitive regular expressions:
Given regular expressions
r1
,  , 
and r2
r1  r2
r1  r2
r1 *
Are regular expressions
r1 
Courtesy Costas Busch - RPI
25
Examples
A regular expression:
a  b  c  * (c  )
Not a regular expression:
Courtesy Costas Busch - RPI
a  b  
26
Languages of Regular Expressions
L r  :
language of regular expression
r
Example
L(a  b  c) *   , a, bc, aa, abc, bca,...
Courtesy Costas Busch - RPI
27
Definition
For primitive regular expressions:
L   
L    
La   a
Courtesy Costas Busch - RPI
28
Definition (continued)
For regular expressions r1 and r2
Lr1  r2   Lr1   Lr2 
Lr1  r2   Lr1  Lr2 
Lr1 *  Lr1  *
Lr1   Lr1 
Courtesy Costas Busch - RPI
29
Example
Regular expression: a  b   a *
La  b   a *  La  b La *
 La  b La *
 La   Lb La  *
 a b a *
 a, b , a, aa, aaa,...
 a, aa, aaa,..., b, ba, baa,...
Courtesy Costas Busch - RPI
30
Example
Regular expression
r  a  b  * a  bb
Lr   a, bb, aa, abb, ba, bbb,...
Courtesy Costas Busch - RPI
31
Example
Regular expression
Lr   {a b
r  aa  * bb * b
2n 2m
b : n, m  0}
Courtesy Costas Busch - RPI
32
Example
Regular expression
r  (0  1) * 00 (0  1) *
L(r ) = { all strings with at least
two consecutive 0 }
Courtesy Costas Busch - RPI
33
Example
Regular expression
r  (1  01) * (0   )
L(r ) = { all strings without
two consecutive 0 }
Courtesy Costas Busch - RPI
34
Equivalent Regular Expressions
Definition:
Regular expressions
are equivalent if
r1
and
r2
L(r1)  L(r2 )
Courtesy Costas Busch - RPI
35
Example
L = { all strings without
two consecutive 0 }
r1  (1  01) * (0   )
r2  (1* 011*) * (0   )  1* (0   )
L(r1)  L(r2 )  L
and r2
are equivalent
regular expr.
r1
Courtesy Costas Busch - RPI
36
Regular Expressions
and
Regular Languages
Courtesy Costas Busch - RPI
37
Theorem
Languages
Generated by
Regular Expressions

Courtesy Costas Busch - RPI
Regular
Languages
38
Theorem - Part 1
Languages
Generated by
Regular Expressions

Regular
Languages
1. For any regular expression r
the language L(r ) is regular
Courtesy Costas Busch - RPI
39
Theorem - Part 2
Languages
Generated by
Regular Expressions

Regular
Languages
2. For any regular language L there is
a regular expression r with L(r )  L
Courtesy Costas Busch - RPI
40
Proof - Part 1
1. For any regular expression r
the language L(r ) is regular
Proof by induction on the size of
Courtesy Costas Busch - RPI
r
41
Induction Basis
Primitive Regular Expressions:
,  , 
NFAs
L( M1 )    L()
L( M 2 )  {}  L( )
a
regular
languages
L( M 3 )  {a}  L(a)
Courtesy Costas Busch - RPI
42
Inductive Hypothesis
Assume
for regular expressions r1 and r2
that
L(r1) and L(r2 ) are regular languages
Courtesy Costas Busch - RPI
43
Inductive Step
We will prove:
Lr1  r2 
Lr1  r2 
Lr1 *
Are regular
Languages
Lr1 
Courtesy Costas Busch - RPI
44
By definition of regular expressions:
Lr1  r2   Lr1   Lr2 
Lr1  r2   Lr1  Lr2 
Lr1 *   Lr1  *
Lr1   Lr1 
Courtesy Costas Busch - RPI
45
By inductive hypothesis we know:
L(r1) and L(r2 ) are regular languages
We also know:
Regular languages are closed under:
Union
Lr1   Lr2 
Concatenation Lr1  Lr2 
Star
 Lr1  *
Courtesy Costas Busch - RPI
46
Therefore:
Lr1  r2   Lr1   Lr2 
Lr1  r2   Lr1  Lr2 
Are regular
languages
Lr1 *   Lr1  *
Courtesy Costas Busch - RPI
47
And trivially:
L((r1))
is a regular language
Courtesy Costas Busch - RPI
48
Proof – Part 2
2. For any regular language L there is
a regular expression r with L(r )  L
Proof by construction of regular expression
Courtesy Costas Busch - RPI
49
Since L is regular take the
NFA M that accepts it
L( M )  L
Single final state
Courtesy Costas Busch - RPI
50
From M construct the equivalent
Generalized Transition Graph
in which transition labels are regular expressions
Example:
M
a
c
a
c
ab
a, b
Courtesy Costas Busch - RPI
51
Another Example:
a
q0
b
b
q1 a, b
q2
b
b
b
a
q0
q1 a  b q2
b
Courtesy Costas Busch - RPI
52
Reducing the states:
b
a
q0
b
q1 a  b q2
b
bb * a
q0
b
bb * (a  b)
Courtesy Costas Busch - RPI
q2
53
Resulting Regular Expression:
bb * a
q0
b
bb * (a  b)
q2
r  (bb * a) * bb * (a  b)b *
L( r )  L( M )  L
Courtesy Costas Busch - RPI
54
In General
e
g
d
Removing states:
qi
c
qj
q
a
b
f
ae * d
ce * b
* d* d
g ce
 ce
qi
f
aeae
* b* b
Courtesy Costas Busch - RPI
qj
55
The final transition
graph:
r4
r1
r3
q0
r2
qf
The resulting regular expression:
r  (r1  r2 r4 * r3 ) * r2 r4 *
r  r1 * r2 (r4  r3r1 * r2 ) *
L( r )  L( M )  L
Courtesy Costas Busch - RPI
56
Theorem
If L  L(A) for some DFA A
Then there is a regular expression R such that
L  L(R)
Proof: (by induction on the size of R)
Let A’s states be {1, 2, …, n} for some integer n
Construct a collection of regular expressions
that describe progressively broader sets of
paths in DFA A
57
Let Rij(k ) be the regex that represent the set
of strings w such that w is the label of a path
from state i to j in A, and that path has no
intermediate state who’s label is greater than
k.
Note: beginning & end points, i.e. i & j are not
intermediate so they can be greater than k
Courtesy Costas Busch - RPI
58
Inductive Definition
Basis: k = 0
Since all states are >= 1, restriction on the
paths is that the path must have no
intermediate states at all.
• If i ≠ j
An arc from i to j
( 0)
•Depending of the DFA A Rij may be φ, a or
( 0)
ij
R
 a1  a2   am
(If there are m symbols that label arcs from
i to j)
59
Inductive Definition
•If i = j
all loops from i to itself
legal paths of length 0
( 0)
ij
R
   a1  a2   am
(If there are m symbols that label arcs from
i to i)
60
Inductive Definition
Induction:
Suppose that there is a path from i to j that
goes through no state with label higher than
k. Consider two cases
•path does not go thru state k at all.
j
i
(k )
ij
R
( k 1)
ij
R
61
•path goes thru state k at least once
- once
More than once
i
k
k
( k 1)
ik
(k )
ij
R
( k 1)
kj
( k 1) *
kk
R
(R
( k 1)
ij
R
( k 1)
ik
R
j
k
R
)
( k 1) *
kk
(R
( k 1)
kj
)R
62
```