COMP30026 Models of Computation – Nondeterministic Finite Automata
COMP30026 Models of Computation
Nondeterministic Finite Automata
Bach Le / Anna Kalenkova
Lecture Week 7 Part 2
Semester 2, 2021
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 1 / 12
This Lecture is Being Recorded
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 2 / 12
Nondeterminism
The type of machine we have seen so far is called a deterministic
finite automaton, or DFA.
We now turn to non-deterministic finite automata, or NFAs.
Here is an NFA that recognises the language
{
w
∣
∣
∣
∣
w ∈ {0, 1}∗ has length 3 or more,
and the third last symbol in w is 1
}
q1 q2 q3 q4
0, 1
1 0, 1 0, 1
Note: No transitions from q4, and two possible transitions when we
meet a 1 in state q1.
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 3 / 12
Nondeterminism
The NFA is more intelligible than a DFA for the same language:
000 100 010 101 110
001 011 111
0
0 0
1
0
1
0
1 1 0
1 1
1
1 0 0
This is the simplest DFA that will do the job!
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 4 / 12
Epsilon Transitions
NFAs may also be allowed to move from one state to another without
consuming input.
Such a transition is an ǫ transition.
Among other things, this gives us an easy way to construct a
machine to recognise the union of two languages:
0 1
32
S
0
0
1
1
1 1
00
ǫ
ǫ
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 5 / 12
Multiple Possible Start States
Epsilon transitions are often useful, but in the previous example we
actually did not need them, because an NFA is also allowed to have
multiple start states.
This NFA is equivalent to the previous one, but it has only four states:
0 1
32
0
0
1
1
1 1
00
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 6 / 12
Formal Definition of NFA
For any alphabet Σ let Σ
ǫ
denote Σ ∪ {ǫ}.
An NFA is a 5-tuple (Q,Σ, δ, I , F ), where
Q is a finite set of states,
Σ is a finite alphabet,
δ : Q × Σ
ǫ
→ P(Q) is the transition function,
I ⊆ Q are the start states, and
F ⊆ Q are the accept states.
Note that, unlike a DFA, an NFA can have several “start” states—it
can start executing from any one of those.
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 7 / 12
NFA Acceptance and Recognition, Formally
The definition of what it means for an NFA N to accept a string says
that it has to be possible to make the necessary transitions.
Let N = (Q,Σ, δ, I , F ) be an NFA and let w = v1v2 · · · vn where each
vi is a member of Σǫ.
N accepts w iff there is a sequence of states r0, r1, . . . , rn, with each
ri ∈ Q, such that
1. r0 ∈ I
2. ri+1 ∈ δ(ri , vi+1) for i = 0, . . . , n − 1
3. rn ∈ F
N recognises language A iff A = {w | N accepts w}.
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 8 / 12
DFAs vs NFAs
The class of languages recognised by NFAs is exactly the class of
regular languages.
Theorem: Every NFA has an equivalent DFA.
The proof rests on the so-called subset construction.
Given NFA N, we construct DFA M , each of whose states
corresponds to a set of N-states.
If N has k states then M may have up to 2k states (but it will often
have far fewer than that).
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 9 / 12
DFAs vs NFAs
Consider the NFA on the right. We can
systematically construct an equivalent
DFA from the NFA.
The DFA’s start state is {1, 3}.
From {1, 3} a takes us to {1, 2, 3}.
From {1, 2, 3}, a takes us back to
{1, 2, 3}, b takes us to {2, 3}.
Any state S which contains an accept
state from the NFA will be an accept
state for the DFA. Here we mark accept
states with a star.
1
2 3
a
ǫ
a, b
b
a
a b
A={1,3} B∗ –
B∗={1,2,3} B∗ C∗
C∗={2,3} B∗ C∗
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 10 / 12
DFAs vs NFAs
Here is the equivalent DFA that we
derive.
Any state S which contains an accept
state from the NFA (in this case the NFA
has just one, namely state 2) becomes an
accept state for the DFA.
We add (dead) state D that corresponds
to the empty set.
A
B∗ C ∗
D
a
a
b
b
a
a, b
b
a b
A={1,3} B∗ D
B∗={1,2,3} B∗ C∗
C∗={2,3} B∗ C∗
D=∅ D D
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 11 / 12
More Formally . . .
Let N = (Q,Σ, δ, I , F ). Let
∗
→
ǫ
be the reflexive transitive closure of
→
ǫ
, which in turn is defined by s →
ǫ
s ′ iff s ′ ∈ δ(s, ǫ).
Let E (S) be the “ǫ closure” of S ⊆ Q, that is, S together with all
states reachable from states in S , using only ǫ steps:
E (S) =
⋃
s∈S
{s ′ ∈ Q | s
∗
→
ǫ
s
′}
We construct M = (P(Q),Σ, δ′, q0, F
′) as follows:
q0 = E (I )
δ′(S , v ) =
⋃
s∈S
E (δ(s, v ))
F ′ = {S ⊆ Q | S ∩ F 6= ∅}
Note: This construction may include unreachable states.
Models of Computation (Sem 2, 2021) Nondeterministic Finite Automata © University of Melbourne 12 / 12