Finite Automata
This ppt is the work by Dr. Costas Busch, used with permission, and available from http://csc.lsu.edu/~busch/courses/theorycomp/fall2008/ 1
Nondeterministic Finite Automaton (NFA)
Alphabet ={a}
a
q0
q1
a
q2
a
q3
2
Alphabet ={a}
Two choices a q0
q1
a
q2
a
q3
3
Alphabet ={a}
Two choices a q0
q1
a
q2
No transition
a
q3
No transition
4
First Choice a a
a
q0
q1
a
q2
a
q3
5
First Choice a a
a
q0
q1
a
q2
a
q3
6
First Choice a a
All input is consumed a q0
q1
a
q2
“accept”
a
q3
7
Second Choice a a
a
q0
q1
a
q2
a
q3
8
Second Choice a a
Input cannot be consumed a q0
a
q1
a
q2
Automaton Halts
q3
“reject”
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
10
aa
is accepted by the NFA:
“accept”
a
q0
q1
a
q2
a
q0
a
q3
because this computation accepts aa
q1
a
q2
a
q3
“reject”
this computation is ignored
11
Rejection example a a
q0
q1
a
q2
a
q3
12
First Choice a “reject” a q0
q1
a
q2
a
q3
13
Second Choice a a
q0
q1
a
q2
a
q3
14
Second Choice a a
q0
q1
a
q3
“reject”
q2
a
15
Another Rejection example a a a
a
q0
q1
a
q2
a
q3
16
First Choice a a a
a
q0
q1
a
q2
a
q3
17
First Choice a a a
Input cannot be consumed a q0
q1
a
q3
a
q2
“reject”
Automaton halts
18
Second Choice a a a
a
q0
q1
a
q2
a
q3
19
Second Choice a a a
Input cannot be consumed a q0
q1
a
q2
Automaton halts
a
q3
“reject”
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
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
22
aaa is rejected by the NFA:
“reject”
a
q0
q1
a
q2
a
q0
a
q3
q1
a
q2
a
q3
“reject”
All possible computations lead to rejection
23
Language accepted:L {aa}
a
q0
q1
a
q2
a
q3
24
Epsilon Transitions
q0
a
q1
q2
a
q3
25
a a
q0
a
q1
q2
a
q3
26
a a
q0
a
q1
q2
a
q3
27
input tape head does not move a a
q0
a
q1
q2
a
q3
28
all input is consumed a a
“accept”
q0
String
aa
a
q1
q2
a
q3
is accepted
29
Rejection Example a a a
q0
a
q1
q2
a
q3
30
a a a
q0
a
q1
q2
a
q3
31
(read head doesn’t move) a a a
q0
a
q1
q2
a
q3
32
Input cannot be consumed a a a
Automaton halts
“reject”
q0
String
a
aaa
q1
q2
a
q3
is rejected
33
Language accepted:L {aa}
q0
a
q1
q2
a
q3
34
Another NFA Example
q0
a
b
q1
q2
q3
35
a b
q0
a
b
q1
q2
q3
36
a b
q0
a
q1
b
q2
q3
37
a b
“accept”
q0
a
q1
b
q2
q3
38
Another String
a b a b
q0
a
q1
b
q2
q3
39
a b a b
q0
a
q1
b
q2
q3
40
a b a b
q0
a
q1
b
q2
q3
41
a b a b
q0
a
q1
b
q2
q3
42
a b a b
q0
a
q1
b
q2
q3
43
a b a b
q0
a
q1
b
q2
q3
44
a b a b
“accept”
q0
a
q1
b
q2
q3
45
Language accepted
L ab, abab, ababab, ...
ab q0 a
q1
b
q2
q3
46
Another NFA Example
0 q0 1
q1
0, 1 q2
47
Language accepted
L( M ) , 10, 1010, 101010, ...
10 *
0
q0
1
q1
0, 1 q2
(redundant state) 48
Remarks:
•The symbol never appears on the input tape
•Simple automata:
M1 q0 M2
L(M1 ) = {}
L( M 2 ) { }
q0
49
•NFAs are interesting because we can express languages easier than DFAs
NFA
q0
a
M1
DFA
q2
q1
a q0 L( M1 ) = {a}
a
M2
a
q1
L( M 2 ) = {a}
50
Formal Definition of NFAs
M Q, , , q0 , F
q0 , q1, q2
Q:
Set of states, i.e.
:
Input aplhabet, i.e. a, b
:
Transition function
q0 : Initial state
F:
Accepting