Chapter-one continue

Nondeterministic Finite
Automata

1
 Nondeterminism
 A nondeterministic finite
automaton has the ability to be in
several states at once.
 Transitions from a state on an
input symbol can be to any set of
states.

2
 Nondeterminism – (2)
 Start in one start state.
 Accept if any sequence of choices
leads to a final state.
 Intuitively: the NFA always
“guesses right.”

3
 Example: Moves on a
Chessboard
 States = squares.
 Inputs = r (move to an adjacent
red square) and b (move to an
adjacent black square).
 Start state, final state are in
opposite corners.

4
 Example: Chessboard – (2)
r b
1 2 3
1 2,4 5
2 4,6 1,3,5
4 5 6 3 2,6 5
4 2,8 1,5,7
7 8 9 5 2,4,6,8 1,3,7,9
6 2,8 3,5,9
r b b 7 4,8 5
1 2 1 5 8 4,6 5,7,9
4 3 1 * 9 6,8 5
5 3
7 7
9 Accept, since final state reached
5
 Formal NFA
 A finite set of states, typically Q.
 An input alphabet, typically Σ.
 A transition function, typically δ.
 A start state in Q, typically q0.
 A set of final states F ⊆ Q.

6
 Transition Function of an
NFA
 δ(q, a) is a set of states.
 Extend to strings as follows:
 Basis: δ(q, ε) = {q}
 Induction: δ(q, wa) = the union
over all states p in δ(q, w) of δ(p,
a)

7
 Language of an NFA
 A string w is accepted by an NFA if
δ(q0, w) contains at least one final
state.
 The language of the NFA is the set
of strings it accepts.

8
 Example: 1 2 3
Language of an 4 5 6

NFA 7 8 9

 For our chessboard NFA we saw that

9
 Equivalence of DFA’s,
NFA’s
 A DFA can be turned into an NFA
that accepts the same language.
 If δD(q, a) = p, let the NFA have
δN(q, a) = {p}.
 Then the NFA is always in a set
containing exactly one state – the
state the DFA is in after reading
the same input.
10
 Equivalence – (2)
 Surprisingly, for any NFA there is a
DFA that accepts the same language.
 Proof is the subset construction.
 The number of states of the DFA can
be exponential in the number of
states of the NFA.
 Thus, NFA’s accept exactly the
regular languages.
11
 Subset Construction
 Given an NFA with states Q, inputs Σ,
transition function δN, state state q0,
and final states F, construct equivalent
DFA with:
 States 2Q (Set of subsets of Q).
 Inputs Σ.
 Start state {q0}.
 Final states = all those with a member of F.

12
 Critical Point
 The DFA states have names that
are sets of NFA states.
 But as a DFA state, an expression
like {p,q} must be read as a single
symbol, not as a set.
 Analogy: a class of objects whose
values are sets of objects of
another class.
13
 Subset Construction – (2)
 The transition function δD is
defined by:
δD({q1,…,qk}, a) is the union over all
i = 1,…,k of δN(qi, a).
 Example: We’ll construct the DFA
equivalent of our “chessboard”
NFA.
14
 Example: Subset
Construction
r b r b
1 2,4 5 {1} {2,4} {5}
2 4,6 1,3,5 {2,4}
3 2,6 5 {5}
4 2,8 1,5,7
5 2,4,6,8 1,3,7,9
6 2,8 3,5,9
7 4,8 5
8 4,6 5,7,9
* 9 6,8 5 Alert: What we’re doing here is
the lazy form of DFA construction,
where we only construct a state
if we are forced to. 15
 Example: Subset
Construction
r b r b
1 2,4 5 {1} {2,4} {5}
2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5}
4 2,8 1,5,7 {2,4,6,8}
5 2,4,6,8 1,3,7,9 {1,3,5,7}
6 2,8 3,5,9
7 4,8 5
8 4,6 5,7,9
* 9 6,8 5

16
 Example: Subset
Construction
r b r b
1 2,4 5 {1} {2,4} {5}
2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8}
5 2,4,6,8 1,3,7,9 {1,3,5,7}
6 2,8 3,5,9 * {1,3,7,9}
7 4,8 5
8 4,6 5,7,9
* 9 6,8 5

17
 Example: Subset
Construction
r b r b
1 2,4 5 {1} {2,4} {5}
2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8}{2,4,6,8} {1,3,5,7,9}
5 2,4,6,8 1,3,7,9 {1,3,5,7}
6 2,8 3,5,9 * {1,3,7,9}
7 4,8 5 * {1,3,5,7,9}
8 4,6 5,7,9
* 9 6,8 5

18
 Example: Subset
Construction
r b r b
1 2,4 5 {1} {2,4} {5}
2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8}{2,4,6,8} {1,3,5,7,9}
5 2,4,6,8 1,3,7,9 {1,3,5,7}{2,4,6,8} {1,3,5,7,9}
6 2,8 3,5,9 * {1,3,7,9}
7 4,8 5 * {1,3,5,7,9}
8 4,6 5,7,9
* 9 6,8 5

19
 Example: Subset
Construction
r b r b
1 2,4 5 {1} {2,4} {5}
2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8}{2,4,6,8} {1,3,5,7,9}
5 2,4,6,8 1,3,7,9 {1,3,5,7}{2,4,6,8} {1,3,5,7,9}
6 2,8 3,5,9 * {1,3,7,9}{2,4,6,8} {5}
7 4,8 5 * {1,3,5,7,9}
8 4,6 5,7,9
* 9 6,8 5

20
 Example: Subset
Construction
r b r b
1 2,4 5 {1} {2,4} {5}
2 4,6 1,3,5 {2,4} {2,4,6,8} {1,3,5,7}
3 2,6 5 {5} {2,4,6,8} {1,3,7,9}
4 2,8 1,5,7 {2,4,6,8}{2,4,6,8} {1,3,5,7,9}
5 2,4,6,8 1,3,7,9 {1,3,5,7}{2,4,6,8} {1,3,5,7,9}
6 2,8 3,5,9 * {1,3,7,9}{2,4,6,8} {5}
7 4,8 5 * {1,3,5,7,9}
{2,4,6,8} {1,3,5,7,9}
8 4,6 5,7,9
* 9 6,8 5

21
 NFA’s With ε-Transitions
 We can allow state-to-state
transitions on ε input.
 These transitions are done
spontaneously, without looking at
the input string.
 A convenience at times, but still
only regular languages are
accepted.
22
 Example: ε-NFA
ε 0 1 ε
A {E} {B} ∅
1 1 B ∅ {C} {D}
1 B C D
C ∅ {D} ∅
A ε ε 0
*D ∅ ∅ ∅
E {F} ∅ {B, C}
0 E F
0 F {D} ∅ ∅

23
 Summary
 DFA’s, NFA’s, and ε–NFA’s all
accept exactly the same set of
languages: the regular languages.
 The NFA types are easier to design
and may have exponentially fewer
states than a DFA.
 But only a DFA can be
implemented!
24
 QUESTION
1. Design DFA for the language strings over{0,1} with even length that end
with 0.
First Analysis language
Even length:-total number of character is even.
Ends with 0:-last character must be0
Alphabet:{0,1}.
DFA Strategy:
We need to track TWO pieces of information simultaneously:
[Link] of length (even/odd)
2. Last character (0/1)
States:
- q₀: Even length, last char 0 (ACCEPT)
- q₁: Even length, last char 1
- q₂: Odd length, last char 0
- q₃: Odd length, last char 1

25
How it works:
- q₀: Accept state (even length AND ends with
0)
- Each transition flips length parity (even↔odd)
- Track last character to know if we end with 0
Testing:
- "00": q₀→q₂(0)→q₀(0) ✓ ACCEPTED
- "10": q₀→q₃(1)→q₀(0) ✓ ACCEPTED
- "0": q₀→q₂(0) ❌ REJECTED (odd length)
- "11": q₀→q₃(1)→q₁(1) ❌ REJECTED (ends with 1)
Questin2:-Design DFA for the language strings
over{0,1} with even length that end with 0. 26