Non Deterministic

Finite Automata
Non-  A Non-deterministic Finite Automaton (NFA)
deterministic  is “non-deterministic”

Finite  Implying that the machine can exist in more than one state at the same
time

Automata  Transitions could be non-deterministic

(NFA)
1 qj
qi … • Each transition function therefore
1 maps to a set of states
qk

2
  A Non-deterministic Finite Automaton (NFA)
consists of:
 Q ==> a finite set of states
 ∑ ==> a finite set of input symbols (alphabet)
Non-
 q0 ==> a start state
deterministic  F ==> set of accepting states
Finite  δ ==> a transition function, which is a mapping
Automata between Q x ∑ ==> subset of Q
(NFA)  An NFA is also defined by the 5-tuple:
 {Q, ∑ , q0,F, δ }

3
  Input: a word w in ∑*
 Question: Is w acceptable by the NFA?
 Steps:
How to use an  Start at the “start state” q0
 For every input symbol in the sequence w do
NFA?  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
 Why is this non-deterministic?

• Q = {q0,q1,q2}
0,1 0,1 •  = {0,1}

NFA for strings start

q0
0
q1
1
q2
• start state = q0
• F = {q2}
containing 01 Final • Transition table
state
symbols
0 1
q0 {q0,q1} {q0}

states
q1 Φ {q2}
What will happen if at state q1 *q2 {q2} {q2}
an input of 0 is received?

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

 A DFA for recognizing the key word “while”

w h i l e
What is an q0 q1 q2 q3 q4 q5

“error state”? 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 6

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

 Other examples
Example #2  Keyword recognizer (e.g., if, then, else, while, for, include, etc.)

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

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

8
  Theorem:
 A language L is accepted by a DFA if and only if it
is accepted by an NFA.
 Proof:
1. If part:
Equivalence of  Prove by showing every NFA can be converted to an
DFA & NFA equivalent DFA (subset construction)

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.

9
  L = {w | w ends in 01}
0,1 1 0

0 1 0 1
q0 q1 q2 [q0] [q0,q1] [q0,q2]
0
1

NFA to DFA NFA:

DFA:
construction: δN 0 1

Example
δ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]

0. Enumerate all possible subsets

1. Determine transitions
2. Retain only those states
reachable from {q0}
10
  L = {w | w ends in 01}

1 0

NFA to DFA:
0 1
[q0] [q0,q1] [q0,q2]
0

Repeating the 1

DFA:
example using δN 0 1

LAZY q0
q1
{q0,q1}
Ø
{q0}
{q2}
δD
[q0]
0
[q0,q1]
1
[q0]

CREATION *q2 Ø Ø

Main Idea:
Introduce states as you go
(on a need basis)
11
  Construct a minimal NFA accepting a set of strings over {a, b} in
which each string of the language starts with ‘ab’.
 Construct a minimal NFA accepting a set of strings over {a, b} in
which each string of the language contain ‘a’ as the substring.
 Design a NFA of all binary strings in which 2nd last bit is 1.

NFA Examples  Construct an NFA with ∑ = {0, 1} in which a substring “double ‘1’ is
followed by single ‘0’” must exist. (110)
 Construct an NFA in which all the string contains a substring 1101.
NFA TO DFA
conversion
 • We extend the class of NFAs by allowing (ε) transitions:
1. The automaton may be allowed to change its state without

NFA’s with reading the input symbol.

ε Transitions 2. In diagrams, such transitions are depicted by labeling the

appropriate arcs with ε.

3. Note that this does not mean that ε has become an input symbol.
On the contrary, we assume that the symbol ε does not
belong to any alphabet.
 • A ε-NFA is a 5-tuple A=(Q, , q0,F)
where

– Q is a set of states
Definition – is the alphabet of input symbols
– q0 is the initial state
– F is the set of final states
–  Q  ε  P(Q) is the transition
function
• Note ε is never a member of
• is defined to be (u ε)
 • ε -NFAs add a convenient feature but (in a sense) they bring us nothing
new: they do not extend the class of languages that can be
represented.

• Both NFAs and ε-NFAs recognize exactly the same languages.

ε-
NFA • ε-transitions are a convenient feature: try to design an NFA for the even
or divisible by 3 language that does not use them!
 • ε-closure of a state
• The ε-closure of the state q, denoted ECLOSE(q), is the set that
contains q, together with all states that can be reached starting at
q by following only ε-transitions.
ε-
Closure • In the example:

• ECLOSE(P) ={P,Q,R,S}
• ECLOSE(R)={R,S}
 Convert the following NFA with ε to NFA without ε.

ε-Elimination
Convert NFA-ɛ
to NFA
  Write the regular expression for the language accepting all the string which are
starting with 1 and ending with 0, over ∑ = {0, 1}.

 R = 1 (0+1)* 0

Cont…  Write the regular expression for the language starting and ending with ‘a’ and
having any combination of b's in between.

 R = a b* a

 Write the regular expression for the language starting with a but not having
consecutive b's.
 L = {a, aba, aab, aba, aaa, abab, .....}
 R = {a + ab}
Examples of regular expression and regular languages corresponding to them

( a + b )2 corresponds to the language {aa, ab, ba, bb}, that is the set of strings of length 2 over the
alphabet {a, b}.

In general ( a + b )k corresponds to the set of strings of length k over the alphabet {a, b}.

( a + b )* corresponds to the set of all strings over the alphabet {a, b}.

a*b* corresponds to the set of strings consisting of zero or more a's followed by zero or more b's.

a*b+a* corresponds to the set of strings consisting of zero or more a's followed by one or more b's
followed by zero or more a's.

( ab )+ corresponds to the language {ab, abab, ababab, ... }, that is, the set of strings of repeated ab's.
Examples
 This method involves the following steps in finding the regular expression
for any given DFA-

DFA to RE 1. If there exists any incoming edge to the initial state, then create a new
initial state having no incoming edge to it.
State 2. If there exists multiple final states in the DFA, then convert all the final
Elimination states into non-final states and create a new single final state.

Method 3. If there exists any outgoing edge from the final state, then create a
new final state having no outgoing edge from it.
4. a) Eliminate all the intermediate states one by one.
 These states may be eliminated in any order.
b) Only an initial state going to the final state will be left.
 DFA Step 1

Example 1
Step 3

•There is a path going from state qi to state B via state A.

•So, after eliminating state A, we put a direct path from state q i to state B having cost
∈.0 = 0
•There is a loop on state B using state A.
•So, after eliminating state A, we put a direct loop on state B having cost 1.0 = 10.
 Step 4 (a)

•There is a path going from state qi to state qf via state B.

Cont… •So, after eliminating state B, we put a direct path from state q i to state qf having cost
0.(10)*.∈ = 0(10)*

Step 4 (b)
Find RE for this
DFA