NonDeterministic

Finite Automata
RIKIP GINANJAR
Non-deterministic Finite Automata (NFA)
A Non-deterministic Finite Automaton (NFA)
◦ is of course “non-deterministic”
◦ Implying that the machine can exist in more than one state at the same time
◦ Transitions could be non-deterministic

1 qj
qi … • Each transition function therefore
1 maps to a set of states
qk
2
Non-deterministic Finite Automata (NFA)
A Non-deterministic Finite Automaton (NFA) consists of:
◦ Q ==> a finite set of states
◦ ∑ ==> a finite set of input symbols (alphabet)
◦ q0 ==> a start state
◦ F ==> set of final states
◦ δ ==> a transition function, which is a mapping between Q x ∑ ==>
subset of Q
An NFA is also defined by the 5-tuple:
◦ {Q, ∑ , q0,F, δ }

3
How to use an NFA?
Input: a word w in ∑*
Question: Is w acceptable by the NFA?
Steps:
◦ Start at the “start state” q0
◦ For every input symbol in the sequence w do
◦ Determine all possible next states from all current states, given the current input symbol in
w and the transition function
◦ If after all symbols in w are consumed and if at least one of the current states is a
final state then accept w;
◦ Otherwise, reject w.

4
 Regular expression: (0+1)*01(0+1)*

NFA for strings containing 01

Why is this non-deterministic?

• Q = {q0,q1,q2}
0,1 0,1 •  = {0,1}
• start state = q0
start 0 1
q0 q1 q2 • F = {q2}
Final • Transition table
state symbols
0 1
What will happen if at state q1 q0 {q0,q1} {q0}

states
an input of 0 is received? q1 Φ {q2}
*q2 {q2} {q2}

5
 Note: Explicitly specifying dead states is just a matter of design convenience
(one that is generally followed in NFAs), and
this feature does not make a machine deterministic or non-deterministic.

What is a “dead state”?

A DFA for recognizing the key word “while”

w h i l e
q0 q1 q2 q3 q4 q5

Any other input symbol

qdead
An NFA for the same purpose: Any symbol

w h i l e
q0 q1 q2 q3 q4 q5

Transitions into a dead state are implicit 6

Example #2
Build an NFA for the following language:
L = { w | w ends in 01}

Other examples
◦ Keyword recognizer (e.g., if, then, else, while, for, include, etc.)
◦ Strings where the first symbol is present somewhere later on at least once

7
Extension of δ to NFA Paths
Basis:  (q,) = {q}

Induction:
◦ Let  (q0,w) = {p1,p2…,pk}
◦ δ (pi,a) = Si for i=1,2...,k

◦ Then,  (q0,wa) = S1 U S2 U … U Sk

8
Language of an NFA
An NFA accepts w if there exists at least one path from the start state to an accepting
(or final) state that is labeled by w

L(N) = { w | (q0,w) ∩ F ≠ Φ }

9
Advantages & Caveats for NFA
Great for modeling regular expressions
◦ String processing - e.g., grep, lexical analyzer

Could a non-deterministic state machine be implemented in

practice?
◦ A parallel computer could exist in multiple “states” at the same time
◦ Probabilistic models could be viewed as extensions of non-deterministic
state machines
(e.g., toss of a coin, a roll of dice)

10
 But, DFAs and NFAs are equivalent in their power to capture langauges !!

Differences: DFA vs. NFA

DFA NFA
1. Some transitions could be non-
1. All transitions are deterministic deterministic
◦ Each transition leads to exactly one ◦ A transition could lead to a subset of states
state
2. Not all symbol transitions need to be
defined explicitly (if undefined will go to a
2. For each state, transition on all dead state – this is just a design
possible symbols (alphabet) should be convenience, not to be confused with
defined “non-determinism”)
3. Accepts input if one of the last states is in
3. Accepts input if the last state is in F F
4. Sometimes harder to construct 4. Generally easier than a DFA to construct
because of the number of states 5. Practical implementation has to be
deterministic (convert to DFA) or in the
5. Practical implementation is feasible form of parallelism

11
Equivalence of DFA & NFA
Theorem:
◦ A language
Should be L is accepted by a DFA if and only if it is accepted by an NFA.
true for
Proof:
any L
1. If part:
◦ Prove by showing every NFA can be converted to an equivalent DFA (in the next
few slides…)

2. Only-if part is trivial:

◦ Every DFA is a special case of an NFA where each state has exactly one
transition for every input symbol. Therefore, if L is accepted by a DFA, it is
accepted by a corresponding NFA.

12
Proof for the if-part
If-part: A language L is accepted by a DFA if it is accepted by
an NFA
rephrasing…
Given any NFA N, we can construct a DFA D such that
L(N)=L(D)
How to convert an NFA into a DFA?
◦ Observation: In an NFA, each transition maps to a subset of states
◦ Idea: Represent:
each “subset of NFA_states”  a single “DFA_state”

Subset construction
13
NFA to DFA by subset construction

Let N = {QN,∑,δN,q0,FN}
Goal: Build D={QD,∑,δD,{q0},FD} s.t. L(D)=L(N)
Construction:
1. QD= all subsets of QN (i.e., power set)
2. FD=set of subsets S of QN s.t. S∩FN≠Φ
3. δD: for each subset S of QN and for each input symbol a in ∑:
◦ δD(S,a) = U δN(p,a)

p in s

14
 Idea: To avoid enumerating all of
power set, do
“lazy creation of states”

NFA to DFA construction: Example

L = {w | w ends in 01} 1 0
NFA: DFA: 0 1
0,1 {q0} {q0,q1} {q0,q2}
0
0 1 1
q0 q1 q2

δD 0 1 δD 0 1
δN 0 1
Ø Ø Ø {q0} {q0,q1} {q0}
q0 {q0,q1} {q0} {q0} {q0,q1} {q0} {q0,q1} {q0,q1} {q0,q2}
q1 Ø {q2} {q1} Ø {q2} *{q0,q2} {q0,q1} {q0}
*q2 Ø Ø *{q2} Ø Ø
{q0,q1} {q0,q1} {q0,q2}
*{q0,q2} {q0,q1} {q0} 0. Enumerate all possible subsets
*{q1,q2} Ø {q2} 1. Determine transitions
*{q0,q1,q2} {q0,q1} {q0,q2} 2. Retain only those states
reachable from {q0}
15
NFA to DFA: Repeating the example using LAZY
CREATION
L = {w | w ends in 01} 1 0
NFA: DFA: 0 1
0,1 {q0} {q0,q1} {q0,q2}
0
0 1 1
q0 q1 q2

δN 0 1 δD 0 1
q0 {q0,q1} {q0} {q0} {q0,q1} {q0}
q1 Ø {q2} {q0,q1} {q0,q1} {q0,q2}
*q2 Ø Ø *{q0,q2} {q0,q1} {q0}

Main Idea:
Introduce states as you go
(on a need basis)
16
Correctness of subset construction
Theorem: If D is the DFA constructed from NFA N by subset construction, then L(D)=L(N)
Proof:
◦ Show that D({q0},w) ≡ N(q0,w} , for all w
◦ Using induction on w’s length:
◦ Let w = xa
◦ D({q0},xa) ≡ D(N(q0,x}, a ) ≡ N(q0,w}

17
A bad case where
#states(DFA)>>#states(NFA)
L = {w | w is a binary string s.t., the kth symbol from its end is a 1}

◦ NFA has k+1 states

◦ But an equivalent DFA needs to have at least 2k states

(Pigeon hole principle)

◦ m holes and >m pigeons
◦ => at least one hole has to contain two or more pigeons

18