Prof.

Busch - LSU 1
Non-Deterministic
Finite Automata
Prof. Busch - LSU 2
1
q
2
q
3
q
a
a
a
0
q
} {a Alphabet =
Nondeterministic Finite Automaton (NFA)
Prof. Busch - LSU 3
No transition
1
q
2
q
3
q
a
a
a
0
q
Two choices
No transition
} {a Alphabet =
Prof. Busch - LSU 4
a a
0
q
1
q
2
q
3
q
a
a
First Choice
a
Prof. Busch - LSU 5
a a
0
q
1
q
2
q
3
q
a
a
a
First Choice
Prof. Busch - LSU 6
a a
0
q
1
q
2
q
3
q
a
a
a
accept
First Choice
All input is consumed
Prof. Busch - LSU 7
a a
0
q
1
q
2
q
3
q
a
a
Second Choice
a
Prof. Busch - LSU 8
a a
0
q
1
q
2
q
a
a
a
3
q
Second Choice
reject
Input cannot be consumed
Automaton Halts
Prof. Busch - LSU 9
An NFA accepts a string:
if there is a computation of the NFA
that accepts the string
i.e., all the input string is processed and the
automaton is in an accepting state
Prof. Busch - LSU 10
aa is accepted by the NFA:
0
q
1
q
2
q
3
q
a
a
a
accept
0
q
1
q
2
q
a
a
a
3
q
reject
because this
computation
accepts
aa
this computation
is ignored
Prof. Busch - LSU 11
a
0
q
1
q
2
q
3
q
a
a
Rejection example
a
Prof. Busch - LSU 12
a
0
q
1
q
2
q
3
q
a
a
a
First Choice
reject
Prof. Busch - LSU 13
Second Choice
a
0
q
1
q
2
q
3
q
a
a
a
Prof. Busch - LSU 14
Second Choice
a
0
q
1
q
2
q
a
a
a
3
q reject
Prof. Busch - LSU 15
Another Rejection example
a a
0
q
1
q
2
q
3
q
a
a
a
a
Prof. Busch - LSU 16
a a
0
q
1
q
2
q
3
q
a
a
a
First Choice
a
Prof. Busch - LSU 17
a a
0
q
1
q
2
q
3
q
a
a
a
reject
First Choice
a
Input cannot be consumed
Automaton halts
Prof. Busch - LSU 18
a a
0
q
1
q
2
q
3
q
a
a
Second Choice
a
a
Prof. Busch - LSU 19
a a
0
q
1
q
2
q
a
a
a
3
q
Second Choice
reject
a
Input cannot be consumed
Automaton halts
Prof. Busch - LSU 20
An NFA rejects a string:
if there is no computation of the NFA
that accepts the string.
All the input is consumed and the
automaton is in a non accepting state
The input cannot be consumed
OR
For each computation:
Prof. Busch - LSU 21
a is rejected by the NFA:
0
q
1
q
2
q
a
a
a
3
q
reject
0
q
1
q
2
q
a
a
a
3
q
reject
All possible computations lead to rejection
Prof. Busch - LSU 22
aaa is rejected by the NFA:
0
q
1
q
2
q
3
q
a
a
a
reject
0
q
1
q
2
q
a
a
a
3
q
reject
All possible computations lead to rejection
Prof. Busch - LSU 23
1
q
2
q
3
q
a
a
a
0
q
Language accepted:
} {aa L =
Prof. Busch - LSU 24
Lambda Transitions
1
q
3
q
a
0
q

2
q
a
Prof. Busch - LSU 25
a a
1
q
3
q
a
0
q

2
q
a
Prof. Busch - LSU 26
a a
1
q
3
q
a
0
q

2
q
a
Prof. Busch - LSU 27
a a
1
q
3
q
a
0
q

2
q
a
input tape head does not move
Automaton changes state
Prof. Busch - LSU 28
a a
1
q
3
q
a
0
q

2
q
a
accept
String is accepted
aa
all input is consumed
Prof. Busch - LSU 29
a a
1
q
3
q
a
0
q

2
q
a
Rejection Example
a
Prof. Busch - LSU 30
a a
1
q
3
q
a
0
q

2
q
a
a
Prof. Busch - LSU 31
a a
1
q
3
q
a
0
q

2
q
a
(read head doesnt move)
a
Prof. Busch - LSU 32
a a
1
q
3
q
a
0
q

2
q
a
reject
String is rejected
aaa
a
Input cannot be consumed
Automaton halts
Prof. Busch - LSU 33
Language accepted:
} {aa L =
1
q
3
q
a
0
q

2
q
a
Prof. Busch - LSU 34
Another NFA Example
0
q
1
q
2
q
a
b

3
q
Prof. Busch - LSU 35
a
b
0
q
1
q
2
q
a
b

3
q
Prof. Busch - LSU 36
0
q
2
q
a
b

3
q
a
b
1
q
Prof. Busch - LSU 37
a
b
0
q
1
q
a
b

3
q
2
q
accept
Prof. Busch - LSU 38
0
q
a
b

a
b
Another String
a
b
1
q
2
q
3
q
Prof. Busch - LSU 39
0
q
a
b

a
b
a
b
1
q
2
q
3
q
Prof. Busch - LSU 40
0
q
a
b

a
b
a
b
1
q
2
q
3
q
Prof. Busch - LSU 41
0
q
a
b

a
b
a
b
1
q
2
q
3
q
Prof. Busch - LSU 42
0
q
a
b

a
b
a
b
1
q
2
q
3
q
Prof. Busch - LSU 43
0
q
a
b

a
b
a
b
1
q
2
q
3
q
Prof. Busch - LSU 44
a
b
a
b
0
q
a
b

1
q
2
q
3
q
accept
Prof. Busch - LSU 45
{ }
{ }
+
=
=
ab
ababab abab ab L ... , , ,
Language accepted
0
q
1
q
2
q
a
b

3
q
Prof. Busch - LSU 46
Another NFA Example


0
q
1
q
2
q
0
1
1 , 0

Prof. Busch - LSU 47

Language accepted
(redundant
state)
Prof. Busch - LSU 48
Remarks:
The symbol never appears on the
input tape

0
q
2
M
0
q
1
M
{} = ) M ( L
1
} { = ) M ( L
2
Simple automata:
Prof. Busch - LSU 49
0
q
2
q
1
q
a
a
a
0
q
1
q
a
} { = ) (
1
a M L
2
M
1
M
} { = ) (
2
a M L
NFA DFA
NFAs are interesting because we can
express languages easier than DFAs
Prof. Busch - LSU 50
Formal Definition of NFAs

( ) F q Q M , , , ,
0
o E =
: Q
: o
:
0
q
: F
Set of states, i.e.
{ }
2 1 0
, , q q q
: E
Input aplhabet, i.e. { } b a,
Transition function
Initial state
Accepting states
E e
Prof. Busch - LSU 51
( ) { }
k
q q q x q , , , ,
2 1
= o
Transition Function
o
q
1
q
1
q
k
q
x
x
x
resulting states with
following one transition
with symbol
x
Prof. Busch - LSU 52
( ) { }
1 0
1 , q q = o
0
1
1 , 0

0
q
1
q
2
q
Prof. Busch - LSU 53
0
q
0
1
1 , 0

} , { ) 0 , (
2 0 1
q q q = o
1
q
2
q
Prof. Busch - LSU 54
0
q
0
1
1 , 0

1
q
2
q
} { ) , (
2 0
q q = o
Prof. Busch - LSU 55
0
q
0
1
1 , 0

1
q
2
q
C = ) 1 , (
2
q o
Prof. Busch - LSU 56
Extended Transition Function

*
o
0
q

5
q
4
q
3
q
2
q
1
q
a
a a
b
( ) { }
1 0
*
, q a q = o
Same with but applied on strings o
Prof. Busch - LSU 57
( ) { }
5 4 0
*
, , q q aa q = o
0
q

5
q
4
q
3
q
2
q
1
q
a
a a
b
Prof. Busch - LSU 58
( ) { }
0 3 2 0
*
, , , q q q ab q = o
0
q

5
q
4
q
3
q
2
q
1
q
a
a a
b
Prof. Busch - LSU 59
Special case:
( ) o ,
*
q q e
for any state
q
Prof. Busch - LSU 60


( ) w q q
i j
,
*
o e
: there is a walk from to
with label
i
q
j
q
w
i
q
j
q
w
k
w o o o
2 1
=
1
o
2
o
k
o
i
q
j
q
In general
Prof. Busch - LSU 61
The Language of an NFA
M
The language accepted by is:




where


and there is some
M
( ) { }
n
w w w M L ,... ,
2 1
=
} , , ,..., { ) , (
0
*
j k i m
q q q w q = o
F q
k
e (accepting state)
Prof. Busch - LSU 62


0
q
k
q
m
w
) , (
0
*
m
w q o
( ) M L w
m
e
F q
k
e
i
q
j
q
m
w
m
w
Prof. Busch - LSU 63

0
q

5
q
4
q
3
q
2
q
1
q
a
a a
b
( ) { }
5 4 0
*
, , q q aa q = o
) (M L aae
{ }
5 0
, q q F =
F e
Prof. Busch - LSU 64

0
q

5
q
4
q
3
q
2
q
1
q
a
a a
b
( ) { }
0 3 2 0
*
, , , q q q ab q = o
( ) M L abe
{ }
5 0
, q q F =
F e
Prof. Busch - LSU 65

0
q

5
q
4
q
3
q
2
q
1
q
a
a a
b
{ }
5 0
, q q F =
( ) { }
5 4 0
*
, , q q abaa q = o ) (M L aabae
F e
Prof. Busch - LSU 66

0
q

5
q
4
q
3
q
2
q
1
q
a
a a
b
{ }
5 0
, q q F =
( ) { }
1 0
*
, q aba q = o
( ) M L abae
F e
Prof. Busch - LSU 67

0
q

5
q
4
q
3
q
2
q
1
q
a
a a
b
( ) { } { } } { * * aa ab ab M L =
Prof. Busch - LSU 68
NFAs accept the Regular
Languages

Prof. Busch - LSU 69
Equivalence of Machines

Definition:

Machine is equivalent to machine

if



1
M
2
M
( ) ( )
2 1
M L M L =
Prof. Busch - LSU 70


0
q
1
q
0
1
0
q
1
q
2
q
0
1
1
0
1 , 0
NFA
DFA
( ) * } 10 {
1
= M L
( ) * } 10 {
2
= M L
1
M
2
M
Example of equivalent machines
Prof. Busch - LSU 71
Theorem:
Languages
accepted
by NFAs
Regular
Languages
=
NFAs and DFAs have the same computation power,
accept the same set of languages
Languages
accepted
by DFAs
Prof. Busch - LSU 72
Languages
accepted
by NFAs
Regular
Languages
_
Languages
accepted
by NFAs
Regular
Languages
_
we only need to show Proof:
AND
Prof. Busch - LSU 73
Languages
accepted
by NFAs
Regular
Languages
_
Proof-Step 1
Every DFA is trivially an NFA
Any language accepted by a DFA
is also accepted by an NFA
L
Prof. Busch - LSU 74
Languages
accepted
by NFAs
Regular
Languages
_
Proof-Step 2
Any NFA can be converted to an
equivalent DFA
Any language accepted by an NFA
is also accepted by a DFA
L
Prof. Busch - LSU 75
Conversion NFA to DFA

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
M
M
'
Prof. Busch - LSU 76

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
M
M
'
} , { ) , (
2 1 0
*
q q a q = o
Prof. Busch - LSU 77

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
M
M
'
C = ) , (
0
*
b q o empty set
trap state
Prof. Busch - LSU 78

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
M
M
'
} , { ) , (
2 1 1
*
q q a q = o
C = ) , (
2
*
a q o
{ }
2 1
, q q
union
Prof. Busch - LSU 79

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
M
M
'
} { ) , (
0 1
*
q b q = o
} { ) , (
0 2
*
q b q = o
{ }
0
q
union
Prof. Busch - LSU 80

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
b a,
M
M
'
trap state
Prof. Busch - LSU 81

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
b a,
M
M
'
END OF CONSTRUCTION
F q e
1
{ } F q q
'
e
2 1
,
Prof. Busch - LSU 82
General Conversion Procedure

Input: an NFA

Output: an equivalent DFA
with

M
M
'
( ) ) (M L M L
'
=
Prof. Busch - LSU 83
The NFA has states



The DFA has states from the power set


,... , ,
2 1 0
q q q
{ } { } { } { } .... , , , , , , , ,
3 2 1 1 0 1 0
q q q q q q q C
Prof. Busch - LSU 84


1. Initial state of NFA:



Initial state of DFA:
0
q
( ) { } , ,
0 0
*
q q = o
Conversion Procedure Steps
step
{ } ,
0
q
Prof. Busch - LSU 85

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
M
M
'
Example
( ) { }
0 0
*
, q q = o
Prof. Busch - LSU 86
2. For every DFAs state

compute in the NFA





add transition to DFA

} ,..., , {
m j i
q q q
( )
( )
( ) a q
a q
a q
m
j
i
, *
...
, *
, *
o
o
o

} ,..., , {
n
l k
q q q
' ' '
( ) } ,..., , { }, ,..., , {
n
l k
m j i
q q q a q q q
' ' '
= o
=
Union
step
Prof. Busch - LSU 87

a
b
a

0
q
1
q
2
q
NFA
{ }
0
q
{ }
2 1
, q q
a
DFA
} , { ) , ( *
2 1 0
q q a q = o
{ } ( ) { }
2 1 0
, , q q a q = o
M
M
'
Example
Prof. Busch - LSU 88


3. Repeat Step 2 for every state in DFA and
symbols in alphabet until no more states
can be added in the DFA
step
Prof. Busch - LSU 89

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
b a,
M
M
'
Example
Prof. Busch - LSU 90
4. For any DFA state


if some is accepting state in NFA


Then,
is accepting state in DFA

} ,..., , {
m j i
q q q
j
q
} ,..., , {
m j i
q q q
step
Prof. Busch - LSU 91

a
b
a

0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
b a,
F q e
1
{ } F q q
'
e
2 1
,
M
M
'
Example
Prof. Busch - LSU 92

If we convert NFA to DFA
then the two automata are equivalent:
M
( ) ( ) M L M L
'
=
M
'
Lemma:
Proof:
( ) ( ) M L M L
'
_
( ) ( ) M L M L
'
_
AND
We only need to show:
Prof. Busch - LSU 93
( ) ( ) M L M L
'
_
First we show:
) (M L we
We only need to prove:
) (M L w
'
e
Prof. Busch - LSU 94
) (M L we
w
k
w o o o
2 1
=
0
q
f
q
0
q
f
q
1
o
2
o
k
o
symbols
Consider
NFA
Prof. Busch - LSU 95
i
o
i
o

denotes a possible sub-path like

i
q
j
q
i
q
j
q
symbol
symbol
Prof. Busch - LSU 96
0
q
f
q
k
w o o o
2 1
=
1
o
2
o
k
o
: M
} , {
0
q
1
o
2
o
k
o
: M
'
} , {
f
q
) (M L we
) (M L w
'
e
We will show that if
then
NFA
DFA
state
label
state
label
Prof. Busch - LSU 97
0
q
m
q
n
a a a v
2 1
=
1
a
2
a
n
a
: M
1
a
2
a
n
a
: M
'
} , {
i
q
i
q
j
q
l
q
} , {
j
q
} , {
l
q
} , {
m
q
More generally, we will show that if in : M
(arbitrary string)
then
NFA
DFA
} , {
0
q
Prof. Busch - LSU 98
0
q
1
a
: M
1
a
: M
'
} , {
i
q
i
q
Proof by induction on
Induction Basis:
1
a v =
| | v
is true by construction of M
'
NFA
DFA
1 | | = v
} , {
0
q
Prof. Busch - LSU 99
Induction hypothesis:
k v s s | | 1
0
q
d
q
1
a
2
a
k
a
: M
i
q
j
q
c
q
1
a
2
a
k
a
: M
'
} , {
i
q
} , {
j
q
} , {
c
q } , {
d
q
k
a a a v
2 1
=
NFA
DFA
Suppose that the following hold
} , {
0
q
Prof. Busch - LSU 100
Induction Step:
1 | | + = k v
0
q
d
q
1
a
2
a
k
a
: M
i
q
j
q
c
q
1
a
2
a
k
a
: M
'
} , {
i
q
} , {
j
q
} , {
c
q } , {
d
q
1 1 2 1 + +
'
'
= =
k k
v
k
a v a a a a v


v
'
v
'
e
q
1 + k
a
1 + k
a
} , {
e
q
NFA
DFA
Then this is true by construction of
M
'
} , {
0
q
Prof. Busch - LSU 101
0
q
f
q
k
w o o o
2 1
=
1
o
2
o
k
o
: M
1
o
2
o
k
o
: M
'
} , {
f
q
) (M L we
) (M L w
'
e
Therefore if
NFA
DFA
then
} , {
0
q
Prof. Busch - LSU 102
We have shown: ( ) ( ) M L M L
'
_
With a similar proof
we can show: ( ) ( ) M L M L
'
_
END OF LEMMA PROOF
( ) ( ) M L M L
'
=
Therefore: