Non-Deterministic
Finite Automata
Fall 2006
Costas Busch - RPI
1
Nondeterministic Finite Automaton (NFA)
Alphabet = {a }
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
2
Alphabet = {a }
Two choices
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
3
Alphabet = {a }
Two choices
a
q0
q1
a
q 2 No transition
a
q 3 No transition
Fall 2006
Costas Busch - RPI
4
First Choice
a
a
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
5
First Choice
a
a
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
6
First Choice
a
a
All input is consumed
a
q0
q1
a
q2
“accept”
a
q3
Fall 2006
Costas Busch - RPI
7
Second Choice
a
a
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
8
Second Choice
a
a
Input cannot be consumed
a
q0
a
q1
a
q2
Automaton Halts
q 3 “reject”
Fall 2006
Costas Busch - RPI
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
Fall 2006
Costas Busch - RPI
10
aa is accepted by the NFA:
“accept”
a
q0
q1
a
q2
a
q0
a
q3
because this
computation
accepts aa
Fall 2006
q1
a
q3
a
q2
“reject”
this computation
is ignored
Costas Busch - RPI
11
Rejection example
a
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
12
First Choice
a
“reject”
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
13
Second Choice
a
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
14
Second Choice
a
a
q0
q1
q2
a
q3
Fall 2006
a
“reject”
Costas Busch - RPI
15
Another Rejection example
a
a
a
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
16
First Choice
a
a
a
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
17
First Choice
a
a
a
Input cannot be consumed
a
q0
q1
a
a
q2
“reject”
Automaton halts
q3
Fall 2006
Costas Busch - RPI
18
Second Choice
a
a
a
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
19
Second Choice
a
a
a
Input cannot be consumed
a
q0
q1
q2
Automaton halts
a
q3
Fall 2006
a
“reject”
Costas Busch - RPI
20
An NFA rejects a string:
if there is no computation of the NFA
that accepts the string.
For each computation:
• All the input is consumed and the
automaton is in a non final state
OR
• The input cannot be consumed
Fall 2006
Costas Busch - RPI
21
a is rejected by the NFA:
“reject”
a
q0
q1
a
q2
a
q0
a
q3
“reject”
q1
a
q2
a
q3
All possible computations lead to rejection
Fall 2006
Costas Busch - RPI
22
aaa is rejected by the NFA:
“reject”
a
q0
q1
a
q2
a
q0
a
q3
q1
a
q3
a
q2
“reject”
All possible computations lead to rejection
Fall 2006
Costas Busch - RPI
23
Language accepted: L  {aa }
a
q0
q1
a
q2
a
q3
Fall 2006
Costas Busch - RPI
24
Lambda Transitions
q0
Fall 2006
a
q1

q2
Costas Busch - RPI
a
q3
25
a
a
q0
Fall 2006
a
q1

q2
Costas Busch - RPI
a
q3
26
a
a
q0
Fall 2006
a
q1

q2
Costas Busch - RPI
a
q3
27
input tape head does not move
a
a
q0
Fall 2006
a
q1

q2
Costas Busch - RPI
a
q3
28
all input is consumed
a
a
“accept”
q0
a
q1

q2
a
q3
String aa is accepted
Fall 2006
Costas Busch - RPI
29
Rejection Example
a
a
a
q0
Fall 2006
a
q1

q2
Costas Busch - RPI
a
q3
30
a
a
a
q0
Fall 2006
a
q1

q2
Costas Busch - RPI
a
q3
31
(read head doesn’t move)
a
a
a
q0
Fall 2006
a
q1

q2
Costas Busch - RPI
a
q3
32
Input cannot be consumed
a
a
a
Automaton halts
“reject”
q0
a
String aaa
Fall 2006
q1

q2
a
q3
is rejected
Costas Busch - RPI
33
Language accepted: L  {aa }
q0
Fall 2006
a
q1

q2
Costas Busch - RPI
a
q3
34
Another NFA Example
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
35
a b
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
36
a b
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
37
a b
“accept”
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
38
Another String
a b a b
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
39
a b a b
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
40
a b a b
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
41
a b a b
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
42
a b a b
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
43
a b a b
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
44
a b a b
“accept”
q0
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
45
Language accepted
L  ab , abab , ababab , ... 
 ab 
q0
a

b
q1
q2

q3

Fall 2006
Costas Busch - RPI
46
Another NFA Example
0
q0
1
q1
0, 1
q2

Fall 2006
Costas Busch - RPI
47
Language accepted
L ( M ) = {λ , 10 , 1010 , 101010 , ... }
= {10 } *
0
q0
1
q1
0, 1

Fall 2006
Costas Busch - RPI
q2
(redundant
state)
48
Remarks:
•The  symbol never appears on the
input tape
•Simple automata:
Fall 2006
M1
M2
q0
q0
L ( M 1 ) = {}
L ( M 2 ) = {λ}
Costas Busch - RPI
49
•NFAs are interesting because we can
express languages easier than DFAs
NFA M 1
q0
a
DFA M 2
q2
q1
a
q0
L ( M 1 ) = {a}
Fall 2006
a
a
q1
L ( M 2 ) = {a}
Costas Busch - RPI
50
Formal Definition of NFAs
M  Q ,  ,  , q 0 , F 
Q : Set of states, i.e. q 0 , q1 , q 2 
:
Input aplhabet, i.e. a , b 
 
 : Transition function
q 0 : Initial state
F : Accepting states
Fall 2006
Costas Busch - RPI
51
Transition Function 
 q , x   q 1 , q 2 ,  , q k 
q1
x
q
x
q1
x
resulting states with
following one transition
with symbol x
qk
Fall 2006
Costas Busch - RPI
52
  q 0 , 1   q1 
0
q0
1
q1
0, 1
q2

Fall 2006
Costas Busch - RPI
53
 ( q1 , 0 )  { q 0 , q 2 }
0
q0
1
q1
0, 1
q2

Fall 2006
Costas Busch - RPI
54
 (q 0 ,  )  { q 2 }
0
q0
1
q1
0, 1
q2

Fall 2006
Costas Busch - RPI
55
 ( q 2 ,1)  
0
q0
1
q1
0, 1
q2

Fall 2006
Costas Busch - RPI
56
Extended Transition Function 
*
Same with  but applied on strings

*
q 0 , a   q 1 
q5
q4
a
q0
a
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
57

*
q 0 , aa   q 4 , q 5 
q5
q4
a
q0
a
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
58

*
q 0 , ab   q 2 , q 3 , q 0 
q5
q4
a
q0
a
a
b
q1
q2

q3

Fall 2006
Costas Busch - RPI
59
Special case:
for any state q
q 
Fall 2006
*
q ,  
Costas Busch - RPI
60
In general
qj  
*
q i , w  : there is a walk from q i to q j
with label w
w
qi
qj
w   1 2   k
qi
Fall 2006
1
k
2
Costas Busch - RPI
qj
61
The Language of an NFA M
The language accepted by
M
is:
L M   w 1 , w 2 ,... w n 
where
*
 (q 0 , w m )  { q i ,..., q k ,  , q j }
and there is some
Fall 2006
q k  F (accepting state)
Costas Busch - RPI
62
w m  L M

*
 (q 0 , w m )
qi
wm
q0
qk
wm
wm
Fall 2006
Costas Busch - RPI
qk  F
qj
63
F  q 0 , q 5 
q5
q4
a
q0
a
a
b
q1
q2

q3


*
q 0 , aa   q 4 , q 5 
aa  L ( M )
F
Fall 2006
Costas Busch - RPI
64
F  q 0 , q 5 
q5
q4
a
q0
a
a
b
q1
q2

q3


*
q 0 , ab   q 2 , q 3 , q 0 
ab  L  M 
F
Fall 2006
Costas Busch - RPI
65
F  q 0 , q 5 
q5
q4
a
q0
a
a
b
q1
q2

q3


*
q 0 , abaa   q 4 , q 5 
aaba  L ( M )
F
Fall 2006
Costas Busch - RPI
66
F  q 0 , q 5 
q5
q4
a
q0
a
a
b
q1
q2

q3


Fall 2006
*
q 0 , aba   q 1 
aba  L  M 
F
Costas Busch - RPI
67
q5
q4
a
q0
a
a
b
q1
q2

q3

L M   ab  *  ab  * { aa }
Fall 2006
Costas Busch - RPI
68
NFAs accept the Regular
Languages
Fall 2006
Costas Busch - RPI
69
Equivalence of Machines
Definition:
Machine M 1
is equivalent to machine M 2
if L  M 1   L  M 2 
Fall 2006
Costas Busch - RPI
70
Example of equivalent machines
NFA M 1
L  M 1   {10 } *
0
q0
q1
1
DFA M 2
L  M 2   {10 } *
0 ,1
0
q0
1
q1
1
q2
0
Fall 2006
Costas Busch - RPI
71
Theorem:
Languages
accepted
by NFAs

Regular
Languages
Languages
accepted
by DFAs
NFAs and DFAs have the same computation power,
accept the same set of languages
Fall 2006
Costas Busch - RPI
72
Proof:
we only need to show
Languages
accepted
by NFAs

Regular
Languages
AND
Languages
accepted
by NFAs
Fall 2006

Costas Busch - RPI
Regular
Languages
73
Proof-Step 1
Languages
accepted
by NFAs

Regular
Languages
Every DFA is trivially an NFA
Any language L accepted by a DFA
is also accepted by an NFA
Fall 2006
Costas Busch - RPI
74
Proof-Step 2
Languages
accepted
by NFAs

Regular
Languages
Any NFA can be converted to an
equivalent DFA
Any language L accepted by an NFA
is also accepted by a DFA
Fall 2006
Costas Busch - RPI
75
Conversion NFA to DFA
a
NFA M
q0
a

q1
q2
b
DFA M 
q 0 
Fall 2006
Costas Busch - RPI
76
*
 (q 0 , a )  { q 1 , q 2 }
a
NFA M
q0
a

q1
q2
b
DFA M 
q 0 
Fall 2006
a
q1 , q 2 
Costas Busch - RPI
77
empty set
*
 (q 0 , b )  
a
NFA M
q0
a

q1
q2
b
DFA M 
q 0 
a
q1 , q 2 

trap state
b
Fall 2006
Costas Busch - RPI
78
*
 (q 1 , a )  { q 1 , q 2 }
*
 (q 2 , a )  
a
NFA M
q0
a

q1
union
q2
q1 , q 2 
b
a
DFA M 
a
q 0 
q1 , q 2 
b

Fall 2006
Costas Busch - RPI
79
*
 (q 1 , b )  { q 0 }
*
 (q 2 , b )  { q 0 }
a
NFA M
q0
a

q1
union
q2
q 0 
b
DFA M 
a
b
a
q 0 
q1 , q 2 
b

Fall 2006
Costas Busch - RPI
80
a
NFA M
q0
a

q1
q2
b
DFA M 
a
b
a
q 0 
q1 , q 2 
b

Fall 2006
Costas Busch - RPI
a,b
trap state
81
END OF CONSTRUCTION
a
NFA M
q0
a

q1
q1  F
q2
b
a
DFA M 
b
a
q 0 
q1 , q 2 
b

Fall 2006
Costas Busch - RPI
q1 , q 2   F 
a,b
82
General Conversion Procedure
Input: an NFA M
Output: an equivalent DFA M
with L  M   L ( M )
Fall 2006
Costas Busch - RPI

83
The NFA has states
q 0 , q1 , q 2 ,...
The DFA has states from the power set
 , q 0 , q 1 , q 0 , q 1 , q 1 , q 2 , q 3 , ....
Fall 2006
Costas Busch - RPI
84
Conversion Procedure Steps
step
1.
Initial state of NFA: q 0
Initial state of DFA:
Fall 2006
q 0 
Costas Busch - RPI
85
Example
a
NFA M
q0
a

q1
q2
b
DFA M 
q 0 
Fall 2006
Costas Busch - RPI
86
step
2. For every DFA’s state { q i , q j ,..., q m }
compute in the NFA
 * q i , a 

  * qj ,a

...
  * q m , a
Union
 { q k , q l,..., q n }

add transition to DFA
 { q i , q j ,..., q m }, a   { q k , q l,..., q n }
Fall 2006
Costas Busch - RPI
87
Example
 * ( q 0 , a )  { q1 , q 2 }
a
NFA M
a
q0

q1
q2
b
DFA M 
 q 0 , a   q1 , q 2 
q 0 
Fall 2006
a
q1 , q 2 
Costas Busch - RPI
88
step
3. Repeat Step 2 for every state in DFA and
symbols in alphabet until no more states
can be added in the DFA
Fall 2006
Costas Busch - RPI
89
Example
a
NFA M
q0
a

q1
q2
b
DFA M 
a
b
a
q 0 
q1 , q 2 
b

Fall 2006
Costas Busch - RPI
a,b
90
step
4. For any DFA state
{ q i , q j ,..., q m }
if some q j is accepting state in NFA
Then, { q i , q j ,..., q m }
is accepting state in DFA
Fall 2006
Costas Busch - RPI
91
Example
a
NFA M
q0
a

q1
q1  F
q2
b
a
DFA M 
b
a
q 0 
q1 , q 2 
b

Fall 2006
Costas Busch - RPI
q1 , q 2   F 
a,b
92
Lemma:
If we convert NFA M to DFA M 
then the two automata are equivalent:
L  M   L  M 
Proof:
We only need to show: L  M
  L  M 
AND
L  M   L  M 
Fall 2006
Costas Busch - RPI
93
First we show:
L  M   L  M 
We only need to prove:
w  L(M )
Fall 2006
w  L ( M )
Costas Busch - RPI
94
NFA
Consider
w  L(M )
w
q0
qf
symbols
w   1 2   k
q0
Fall 2006
1
2
Costas Busch - RPI
k
qf
95
symbol
qi
i
qj
denotes a possible sub-path like
qi
Fall 2006


symbol
i
Costas Busch - RPI

qj
96
We will show that if w  L ( M )
w   1 2   k
NFA M :
q0
1
k
2
qf
then
1
DFA M  :
{q 0 }
Fall 2006
state
label
2
w  L ( M )
Costas Busch - RPI
k
{ q f , }
state
label
97
More generally, we will show that if in M :
(arbitrary string)
NFA M :
q0
v  a1 a 2  a n
a1
qi
a2
qj
ql
an
qm
then
a1
DFA M  :
{q 0 }
Fall 2006
a2
{ q i , } { q j , }
Costas Busch - RPI
an
{ q l ,  } { q m , }
98
Proof by induction on | v |
Induction Basis: | v | 1
NFA M :
q0
v  a1
a1
qi
a1
DFA M  :
{q 0 }
{ q i , }
is true by construction of M 
Fall 2006
Costas Busch - RPI
99
Induction hypothesis: 1  | v | k
v  a1 a 2  a k
Suppose that the following hold
NFA M :
q0
a1
DFA M  :
{q 0 }
Fall 2006
a1
qi
a2
qj
qd
ak
a2
{ q i , }
qc
ak
{ q j , }
Costas Busch - RPI
{ q c , }
{ q d , }
100
Induction Step: | v | k  1
v  a1 a 2  a k a k 1  v a k 1
 

v
Then this is true by construction of M 
NFA M :
q0
a1
a2
qi
qj
qc
ak
qd
a k 1
qe
v
DFA M  :
a1
{q 0 }
Fall 2006
ak
a2
{ q i , }
{ q j , }
v
Costas Busch - RPI
{ q c , }
a k 1
{ q d , }
{ q e , }
101
Therefore if w  L ( M )
w   1 2   k
NFA M :
1
q0
k
2
qf
then
DFA M  :
1
{q 0 }
Fall 2006
2
w  L ( M )
Costas Busch - RPI
k
{ q f , }
102
We have shown:
L  M   L  M 
With a similar proof
we can show: L  M
Therefore: L M
  L  M 
  L M  
END OF LEMMA PROOF
Fall 2006
Costas Busch - RPI
103
Descargar

Languages and Finite Automata