CMP3008

Formal Languages
and Automata Theory
Lecture Notes 3
Nondeterminism
Sources
https://eecs.wsu.edu/~ananth/CptS317/Lectures/index.htm
"Introduction to automata theory, languages and
computation" by JE Hopcroft, R Motwani and JD Ullman.
" An Introduction to Formal Languages and Automata Theory" by
Peter Linz
1
 Content
• Nondeterminism
• Nondeterministic Finite Accepters (NFAs)
• Formal Definition of Computation
• Equivalence of DFA and NFA
• Closure Under Regular Operations

2
Nondeterminism
• When a machine is in a given state and reads the next input symbol, if
we know what the next state will be (it is determined) we call this
deterministic computation.
• In a nondeterministic machine, several choices may exist for the next
state at any point.
• Deterministic finite automaton is abbreviated DFA.
• Nondeterministic finite automaton is abbreviated NFA.

3
Nondeterminism Is this a DFA?

4
Nondeterminism

• Every state of a DFA always has exactly one exiting transition arrow for
each symbol in the alphabet. The NFA shown above violates that rule. In an
NFA, a state may have zero, one, or many exiting arrows for each alphabet
symbol.
• In a DFA, labels on the transition arrows are symbols from the alphabet.
This NFA has an arrow with the label ε. In general, an NFA may have arrows
labeled with members of the alphabet or ε. Zero, one, or many arrows may
exit from each state with the label ε.
5
 Nondeterministic Finite Accepters
• An automaton is nondeterministic if it has a choice of
actions for given conditions
• Basic differences between deterministic and
nondeterministic finite automata:
• In an nfa, a (state, symbol) combination may lead to several
states simultaneously
• If a transition is labeled with the empty string as its input symbol,
the nfa may change states without consuming input
• An nfa may have undefined transitions

6
Nondeterministic FA
Example 1

• Example shows a NFA in

which there are two
transitions labeled a out of
state q0
• More precisely,
δ(q0, a) = { q1, q4 }

7
Nondeterministic FA Example 2
• Example shows a NFA which contains both a -transition as
well as undefined transitions
• More precisely, δ(q0, ) = { q2 } and δ(q2, 0) = 

8
The Language Accepted by a Nondeterministic FA
• For a given nfa, the value of the extended transition function δ*(qi, w) is
the set of all possible states for the control unit after processing w,
having started in qi
• Sample values of δ* for the nfa given below:
δ*(q0, 10) = { q0, q2 } δ*(q0, 101) = { q1 }
• A string w is accepted if δ*(q0, w) contains a final state.
• In the example above, 10 would be accepted but 101 would be rejected.

9
The Language Accepted by a Nondeterministic FA
• As is the case with dfa, the language accepted by a
nondeterministic fa M is the set of all accepted strings.
• What is the language accepted by the machine given below?
• L = { (10)n: n ≥ 0 }

10
11
The computation of the above NFA on
input 010110 is depicted on the figure
right.

12
Formal Definition of
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 accepting 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, δ }

13
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.

14
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
Regular expression: (0+1)*01(0+1)* 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}
15
 Note: Omitting to explicitly show error states is just a matter of design convenience
(one that is generally followed for NFAs), and
i.e., this feature should not be confused with the notion of non-determinism.

What is an “error state”?

• A DFA for recognizing the key word “while”

w h i l e
q0 q1 q2 q3 q4 q5

Any other input symbol

qerr
Any symbol

• An NFA for the same purpose:

w h i l e
q0 q1 q2 q3 q4 q5

Transitions into a dead state are implicit 16

Example NFAs
L = {w | w contains a 1 in the third position from the end}, Σ = {0, 1}
Let us first try to build a DFA:
How many states are needed? How many of them are accept states?
Keep a state for each combination of last three digits
Total number of states: 2^3 = 8

17
Example NFAs What is the related regular expression?

(0+1)*1(0+1)(0+1)
Here is the NFA:

No matter what is occurs in the first part of the input, the

words with the following last three symbols are accepted:
……………100 -> one state for the inital part
……………101 -> one state for the first 1
……………110 -> one state for any further 0 or 1
……………111 -> one state for any further 0 or 1

18
Example NFAs
L = {0k | k is a multiple of 2 or 3}, Σ = {0}

19
 Example NFAs

L = {0k | k is a multiple of 2 or 3}, Σ = {0}

DFA?
What is the least common multiple of 2 and 3?

20
Example NFAs
L = {w | w starts with a 0}, Σ = {0,1 }

21
22
Formal Definition of Computation

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

Differences: DFA vs. NFA

DFA NFA
1. All transitions are deterministic 1. Some transitions could be non-deterministic
• Each transition leads to exactly one state • A transition could lead to a subset of states
2. For each state, transition on all possible 2. Not all symbol transitions need to be defined
symbols (alphabet) should be defined explicitly (if undefined will go to an error state –
this is just a design convenience, not to be
confused with “non-determinism”)
3. Accepts input if the last state visited is in F 3. Accepts input if one of the last states is in F
4. Sometimes harder to construct because of the 4. Generally easier than a DFA to construct
number of states
5. Practical implementation is feasible 5. Practical implementations limited but emerging
(e.g., Micron automata processor)

24
 Equivalence of DFA & NFA
• Theorem:
• A language L is accepted by a DFA if and only if it is accepted by an NFA.
•
Should be Proof:
true for any 1. If part: A language L is accepted by a DFA if it is accepted by an NFA.
L
(If a language L is accepted by an NFA, we can also design a DFA that accepts L).
• Prove by showing every NFA can be converted to an equivalent DFA (in the next few
slides…)
2. Only-if part is trivial: A language L is accepted by a NFA if it is accepted by
an DFA.
• 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.

25
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

26
Equivalence of NFAs and DFAs
• Proof by construction:
• To construct a DFA that is equivalent
to an NFA, we first determine DFA’s
states.
• The NFA on the right has three states,
{1, 2, 3}, so we construct DFA with
eight states, one for each subset of
NFA’s states.
• We label each of DFA’s states with the
corresponding subset.
• That’s because we can move to an
empty set, one of the states, two of the
states, ….., or all of the states (i.e. Any
subset of set of states) from a given
state after reading an input
27
Equivalence of NFAs and DFAs
Then determine the start and accept states and the transitions

Start state?

28
Equivalence of NFAs and DFAs
• We may simply the machine by removing unreachable states.

29
Procedure: nfa-to-dfa Conversion
1. Beginning with the start state, define input transitions for
the dfa as follows:
• If the nfa input transition leads to a single state, replicate for the dfa
• If the nfa input transition leads to more than one state, create a new
state in the dfa labeled { qi, ..., qj }, where qi, ..., qj are all the states
the nfa transition can lead to.
• If the nfa input transition is not defined, the corresponding dfa
transition should lead to a trap state.
2. Repeat step 1 for all newly created dfa states, until no new
states are created.
3. Any dfa state containing an nfa final state in its label should
be labeled as final.
4. If the nfa accepts the empty string, label the start dfa state a
final state.

30
NFA to DFA: Example 1

• 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)
31
NFA to DFA: Example 2

• L = {w | w starts with 0}

NFA:
0, 1
Trap state
0
q1
DFA:
q0

δN 0 1
δN 0 1
q0 [q1] [q2]
q0 {q1} Ø
*q1 [q1] [q1]
*q1 {q1} {q1}
q2 [q2] [q2]

Main Idea:
Introduce states as you go
(on a need basis)
32
NFA to DFA: Example 3

• What is modeled by the following NFA?

• L = {w | w ends with 1}
NFA:
0, 1

1
q0 q1

δN 0 1

q0

*q1

33
NFA to DFA: Example 4

• L = {w | w whose second symbol from the end is ‘1’}

34
NFA to DFA: Example 5

35
 nfa-to-dfa Conversion Example (cont.)
• Since there are no dfa states with undefined
transitions, the process stops. All states containing q1
in their label are designated as final states.

36
Closure under regular operations

37
Closure under regular operations
• Proof by construction

38
Closure under regular operations

39
Closure under regular operations
• Proof by construction

40
Closure under regular operations

41
Closure under regular operations
• Proof by construction

42