CS 3186
Nondeterministic Finite Acceptors
Section 2.2
1
Nondeterministic Finite Accepter (NFA)
M = (Q, ,, q0,F)
Q: Set of states
: Input alphabet
: Transition function
q0: Initial state
F: Final states
2
Nondeterministic Finite Accepter - NFA
Where Q, , q0 and F are defined as for
deterministic finite accepters, but
: Q X ( ) 2Q
2Q is referred to as the power set of Q and is defined
as the set of all subsets of Q including the empty
set and Q itself.
For example, if Q = {q0,q1}, the power set of Q is
{}, {q0}, {q1}, {q0,q1}
3
Nondeterministic Finite Accepter - NFA vs DFA
Where Q, , q0 and F are defined as for
deterministic finite accepters, but
: Q X ( ) 2Q
NFA permits several possible “next states” specified in one of the
subsets of the power set.
i.e., for a given combination of current state and input symbol, the
next state is not uniquely defined as in a DFA.
The automaton, as it reads the input string, may choose at each step to
go into any one of these legal next states; the choice is not
determined by anything in our model, and is therefore said to be
nondeterministic.
4
Example (#1) of NFA
= {a}
Note: Two choices from q0 on input “a”
(q0,a) = {q1,q3}
Note: No transition defined on q2 and q3
5
NFA – Tracing First Choice
6
7
8
9
NFA – Tracing Second Choice
10
11
12
NFA Acceptance
An NFA accepts a string
when there is a computation
(on any one of the choices)
of the NFA that accepts the string
AND
all the input is consumed and the automaton
is in a final state
13
NFA Example #1
aa is accepted by the NFA because at least
one choice below leads to acceptance
because this
computation
accepts aa
14
NFA Example #2
a is rejected by the NFA
Because all possible computations lead to
rejection
15
NFA Rejection
An NFA rejects a string:
when there is no computation of the NFA
that accepts the string:
All the input is consumed and the
automaton is in a non final state
OR
The input cannot be consumed
16
NFA Language - Example (#1)
Language accepted = {aa}
17
Lambda Transitions in NFA
NFA allows transitions.
The transition takes place without consuming
an empty string.
Note does not occur on the input
18
NFA with transitions: Example #3
19
20
21
22
Example #3: Acceptance
all input is consumed
String aa is accepted
23
Example #3: Rejection
24
25
26
NFA Example #3: Rejection
No transition possible from q3
Input cannot be consumed and the automaton
hangs;
String aaa is rejected
27
NFA Example #3: Language
Language accepted: L ={aa}
28
Another NFA Example #4
29
30
31
32
33
NFA Example #4
34
35
36
37
38
39
40
41
NFA Example #4 - Language
Language accepted, L
L = {ab, abab, ababab, …}
= {ab}+
42
Another NFA Example #5
Language accepted by automata, M = L(M)
L(M) = {, 10, 1010, 101010, …}
= {10}*
43
NFA Remarks-1
• The symbol never appears on the
input tape
• Simple automata
44
NFA Remarks-2
The key differences between dfas and nfas are
1. dfa: yields a single state
nfa: yields a set of states
2. dfa: consumes input on each move
nfa: can move without input on
3. dfa: moves for all inputs in all states
nfa: some situations have no defined moves
45
NFA Remarks-3
NFAs are interesting because we can express
languages easier than DFAs
= {a}
46
Extended Transition Function *
As with dfas, the transition function can be extended so its
second argument is a string.
47
48
NFA – Extended transition function
Formally, qj *(qi,w)
There exists one possible walk from qi to qj
with label w.
49
The Language of an NFA
50
51
52
53
The language of an NFA, M
54
Language accepted by NFA
Formally, the language accepted by NFA, M,
is:
L(M) = {w1,w2,w3,…}
wmL(M) if
*(q0, wm) = {qi, qj,… qk,…}
where some qkF
55
Language accepted by NFA, M
i.e., L(M) is the set of all strings w for which there is a walk
labeled w from the initial vertex of the transition graph
to some final vertex.
56
Nondeterminism
1) an nfa can model a search or backtracking
algorithm
2) nfa solutions may be simpler than dfa solutions
(can convert from nfa to dfa)
3) Note that complementing a NFA is a non-trivial
task (unlike DFAs where all you needed to do was
to just flip the accepting/non-accepting states).
57
Homework 2.2
I) Do exercises : #5 to #14
II) Construct an NFA over the input
alphabet Σ = {a,b,c} that accepts all
strings aibjck where i,j,k are all greater
than or equal to 0.
58
