Formal Languages and Theory of Automata

Chapter 2 – Finite Automata

Outline
● Finite Automata
● Deterministic Finite Automata (DFA)
● Nondeterministic Finite Automata (NFA)
● Equivalence Between DFA and NFA
● Minimization of DFA

2
Finite Automata
● A finite automata has a finite set of states and a
control unit.
● The control unit moves from state to state in response to
external inputs.
● Depending on the state transition there are two types of
finite automata:
1. Deterministic Finite Automata (DFA) – if the automaton
cannot be in more than one state at any time.
2. Nondeterministic Finite Automata (NFA) – if the
automaton can be in several states at once.
● Let us first discuss about DFA, then NFA.
3
Deterministic Finite Automata (DFA)
● A deterministic finite automaton is the one that is
in a single state after reading any sequence of
inputs.
● The term ‘deterministic’ refers to the fact that
on each input there is one and only one state to
which the automaton can transition from its
current state.

4
Deterministic Finite Automata (DFA)
 A Deterministic Finite Automata (DFA) is a 5-tuple
(Q, S, d, q0, F) where
 Q is a finite set of states
 S (sigma) is an alphabet
 d: Q × S → Q is a transition function
 q0 Î Q is the initial state
 F Í Q is a set of accepting states (or final states).

5
The Transition Function
 It takes two arguments: a state and an input
symbol.
 δ(q, a) = the state that the DFA goes to when it
is in state q and input a is received.
 DFA do not allow non-deterministic state
transitions. There can not be multiple state
transition from state q with the same input a.

6
Graph Representation of DFA’s
 Nodes = states.
 Edges represent transition function.
 Edge from state p to state q labeled by all those
input symbols that have transitions from p to q.
 Edge labeled “Start” to the start state.
 Final states indicated by double circles.
 DFA do not allow non-deterministic edges. i.e.,
there can not be more that one edge leaving
any state with the same label.
7
 Example: Graph of a DFA

Accepts all strings without two consecutive 1’s.

0 0,1
1 1
A B C

Start 0
Previous Previous Consecutive
string OK, String OK, 1’s have
does not ends in a been seen.
end in 1. single 1.
8
 Alternative Representation:
Transition Table
Final states
Starred or circled Columns =
0 1 input symbols
* A A B
Arrow for * B A C
start state C C C

Rows = states

9
 Language of a DFA

 Automata of all kinds define languages.

 If A is an automaton, L(A) is its language.
 For a DFA A, L(A) is the set of strings labeling
paths from the start state to a final state.
 Formally: L(A) = the set of strings w such that
δ(q0, w) is in F.

10
 Example: String in a Language

String 101 is in the language of the DFA below.

Start at A.
0 0,1
1 1
A B C

Start 0

11
 Example: String in a Language

String 101 is in the language of the DFA below.

Follow arc labeled 1.
0 0,1
1 1
A B C

Start 0

12
 Example: String in a Language

String 101 is in the language of the DFA below.

Then arc labeled 0 from current state B.

0 0,1
1 1
A B C

Start 0

13
 Example: String in a Language

String 101 is in the language of the DFA below.

Finally arc labeled 1 from current state A. Result
is an accepting state, so 101 is in the language.
0 0,1
1 1
A B C

Start 0

14
 Example – Concluded
 The language of our example DFA is:
{w | w is in {0,1}* and w does not have
two consecutive 1’s}

Such that…
These conditions
about w are true.
Read a set former as
“The set of strings w…

15
 More Examples on DFA
1. Given a DFA, M such that:
L(M) = {x | x is a string of 0’s and 1’s and |x| >= 2}

0/1

0/1 0/1
q0 q1 q2

16
 More Examples on DFA
2. Given a DFA, M such that:
L(M) = {x | x is in {a,b,c}* and x contains the
substring aba}

b/c a a/b/c
a a
b
q0 q1 q2 q3
c

b/c

17
 More Examples on DFA
3. Let M be a DFA given by:
M = ({q0,q1},{a,b}, δ,q0,{q0}) and δ is given as:
δ(q0,a)=q0
δ(q0,b)=q1
δ(q1,a)=q1
δ(q1,b)=q0

Construct transition diagram and table for the

given DFA and determine the language L(M)18
 More Examples on DFA
4. Given a DFA, M such that:
L(M) = {x | x is in {a,b}* and x contains aa or bb}
a|b
a
q1 q2
a

q0 a b
a|b
b
b
q3 q4

19
 More Examples on DFA
5. Given a DFA, M such that:
L(M) = {x | x is in {a,b}* and x contains both aa
and bb} a
b
a
q1 q2 q3
b a/b
a a

q0 a b q7
b
b a
b a
q4 q5 q6
b
20
 More Examples on DFA
6. Given a DFA, M such that:
L(M) = {x | x is in {0,1}* and x has neither 11
nor 00 as a substring}

q1
0 0/1
0

q0 0 1 q3

1
1
q2

21
 More Examples on DFA
7. Given a DFA, M such that:
L(M) = {x | x is in {0,1}* and x contains 0001 as
a substring}

1 0 0/1
0 1
0 0
q0 q1 q2 q3 q4
1

22
 More Examples on DFA
8. Given a DFA, M such that:
L(M) = {x | x is in {a,b}* and a is immediately
followed by b}
b a/b
a
a
q0 q1 q2
b

23
 More Examples on DFA
9. Given a DFA, M such that:
L(M) = {x | x is in {0,1}* and x contains strings
ending in 00}

1 0
0
0
q0 q1 q2
1

24
 Exercise on DFA
10. For S = {a,b}, construct DFA's that accept
the sets consisting of:
(a) all strings with exactly one a
(b) all strings with at least one a,
(c) all strings with no more than three a's
(d) all strings with at least one a and exactly
two b's.
(e) all the strings with exactly two a's and
more than two b's
25
 Exercise on DFA
11. Given a DFA, M such that:
a) L(M) = {x | x is in {0,1}* and x has a substring
011}

b) L(M) = {x | x is in {0,1}* and the second

symbol from the right is a 1}

c) L(M) = {x | x is in {0,1}* and Either begin or

end (or both) with 01 }
26
Nondeterministic Finite Automata
(NFA)

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

 Start in one start state.

 Accept if any sequence of choices leads to a
final state.
 Intuitively: the NFA always “guesses right.”
28
 Example: Chessboard – (2)
1 2 3
red r b
1 2,4 5
4 5 6 2 4,6 1,3,5
red red
3 2,6 5
7 8 9 4 2,8 1,5,7
red
5 2,4,6,8 1,3,7,9
Check rbb
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 29
Example: Accepted Moves
1 2 3
4 5 6
7 8 9

 For our chessboard NFA we saw that rbb is accepted.

 If the input consists of only b’s, the set of accessible
states alternates between {5} and {1,3,7,9}, so only
even-length, nonempty strings of b’s are accepted.
 What about strings with at least one r?
30
 Formal Definition of NFA

 An NFA is a five-tuple:

M = (Q, Σ, δ, q0, F)

Q A finite set of states

Σ A finite input alphabet
q0 The initial/starting state, q0 is in Q
F A set of final/accepting states, which is a subset of Q
δ A transition function, which is a total function from Q x Σ to 2Q

δ: (Q x Σ)  2Q - 2Q is the power set of Q, the set of all subsets of Q

31
 NFA Differences with DFA

 Three major differences

1. The range of δ is in the power set 2Q

2. ε (empty string) transitions are possible in NFA. NFA
can make a transition without consuming an input
symbol.
3. In an NFA, the set δ(qi,a) may be empty; there is no
transition defined for this specific situation.

32
Example #1: some 0’s followed by some 1’s

0 1 0/1
Q = {q0, q1, q2}
Σ = {0, 1} 0 1
q0 q1 q2
Start state is q0
F = {q2}

δ: 0 1
{q0, q1} {}
q0
{} {q1, q2}
q1
{q2} {q2}
*
q2
33
 Example #2: pair of 0’s or pair of 1’s

Q = {q0, q1, q2 , q3 , q4}

Σ = {0, 1} 0/1 0/1
Start state is q0
0 0
F = {q2, q4} q0 q3 q4

1 0/1
δ: 0 1 1
q0 {q0, q3} {q0, q1}
q1 q2
q1 {} {q2}

{q2} {q2}
q2
*
{q4} {}
q3
{q4} {q4}
* q4 34
 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.

35
Equivalence of DFA’s, NFA’s

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

37
 Equivalence

 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 may have
exponentially more states than the NFA.
 Thus, NFA’s accept exactly the regular languages
like DFA’s.

38
 Subset Construction

 Given an NFA with states Q, inputs Σ, transition

function δN, start 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.

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

40
 Subset Construction
 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.

41
 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 Alert: What we’re doing here is
9 6,8 5 the lazy form of DFA construction,
where we only construct a state
if we are forced to. 42
 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

43
 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

44
 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

45
 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

46
 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

47
 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

48
 Example 1 : Convert NFA to DFA

M=({A,B},{0,1}, δ,A,{A}) where

0 1 δ is given by:

* A A B
B B A,B
0 1
* A A B
B B {A,B}
{A,B} {A,B} {A,B}
*

49
 Example 2 : Convert NFA to DFA

M=({q0,q1,q2},{a,b}, δ,q0,{q2}) where δ is given by:

a b
q0 q0,q1 q2
q1 q0 q1
a b
* q2  q0,q1
q0 {q0,q1} q2

* q2  {q0,q1}
{q0,q1} {q0,q1} {q1,q2}

* {q1,q2} q0 {q0,q1}
  
50
 Example 3 : Convert NFA to DFA

M=({P,Q,R,S},{0,1}, δ,P,{S}) where δ is given by:

0 1
0 1
P {P,Q} P
P P,Q P
{P,Q} {P,Q,R} {P,R}
Q R R
{P,R} {P,Q,S} P
R S 
{P,Q,R} {P,Q,R,S} {P,R}
* S S S
{P,Q,S} {P,Q,R,S} {P,R,S}
*
{P,R,S} {P,Q,S} {P,S}
*
{P,S} {P,Q,S} {P,S}
*
{P,Q,R,S} {P,Q,R,S} {P,R,S}51
*
 Example 4 : Convert NFA to DFA

M=({q0,q1,q2,q3},{a,b}, δ,q0,{q2,q3}) where δ is given by:

a b a b
q0 q0,q1 q0 q0 {q0,q1} q0
q1 q2 q1 {q0,q1} {q0,q1,q2} {q0,q1}
* q2 q3 q3
* {q0,q1,q2} {q0,q1,q2,q3} {q0,q1,q3}
* q3  q2
* {q0,q1,q3} {q0,q1,q2} {q0,q1,q2}

{q0,q1,q2,q3} {q0,q1,q2,q3} {q0,q1,q2,q3}

*

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

53
 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} ∅ ∅

54
 Closure of States

 CL(q) = set of states you can reach from state q

following only arcs labeled ε.
 Example: CL(A) = {A}; ε
CL(E) = {B, C, D, E}. B 1 C 1 D
1
A ε ε 0
0 E F
0

 Closure of a set of states = union of the closure of

each state. 55
 Extended Delta δ
˄

 Basis: δ˄ (q, ε) = CL(q).

 Induction: δ˄ (q, xa) is computed as follows:
1. Start with δ˄ (q, x) = S.
2. Take the union of CL(δ(p, a)) for all p in S.
 Intuition: δ˄ (q, w) is the set of states you can reach
from q following a path labeled w.

56
 Example: Extended Delta
ε
1 B 1 C 1 D
˄
 δ(A, ε) = CL(A) = {A}. A ε ε 0
 δ˄ (A, 0) = CL({E}) = {B, C, D, E}. 0 E 0 F
 δ˄ (A, 01) = CL({C, D}) = {C, D}.
 Language of an ε-NFA is the set of strings w
such that (q0, w) contains a final state.

57
 Equivalence of NFA, ε-NFA
 Every NFA is an ε-NFA.
 It just has no transitions on ε.
 Converse requires us to take an ε-NFA and
construct an NFA that accepts the same
language.
 We do so by combining ε–transitions with the
transition on a real input.

58
 Equivalence – (2)
 Start with an ε-NFA with states Q, inputs Σ, start
state q0, final states F, and transition function δE.
 Construct an “ordinary” NFA with states Q,
inputs Σ, start state q0, final states F’, and
transition function δN.

59
 Equivalence – (3)

Procedure to convert ε-NFA into NFA

Step 1: Find Closure of all states

Step 2: Extended Transition Function for all states:

˄
δ(q0,a)=CL( δ(CL(q0),a))
Step 3: Set of all final states F’ consists of all
states whose E-Closure contains a
final state in F. 60
Interesting
closures: Example: ε-NFA-to-NFA
CL(B) = {B,D}; ε
CL(E) = {B,C,D,E}
1 B 1 C 1 D
0 1
0 1 ε A {B,C,D,E}{B,D}
A ε ε 0
A {E} {B} ∅ ∅ 0 E F
*B {C} 0
B ∅ {C} {D} C ∅ {D}
C ∅ {D} ∅ ∅ ∅
*D
* D ∅ ∅ ∅
E {F} ∅ {B, C} *E {F} {C, D}
F {D} ∅
F {D} ∅ ∅
NFA without ε-Transition
Since closure of
ε-NFA E includes B and
Since closures of C; which have
B and E include transitions on 1
final state D. to C and D. 61
 Additional Examples …
1. Convert the following NFA with -transitions into
NFA without -transitions.
0 1 2

ε ε
q0 q1 q2

Answer:
0,1,2
0 1 2

0,1 1,2
q0 q1 q2

62
 Additional Examples …
2. Convert the following NFA with -transitions into
NFA without -transitions.
0

Answer: ε 1
q0 q1 q2
0
1
0 1
0
0 1 q3
0,1
q0 q1 q2
0
0 1
0
q3
0,1
63
 Exercise
Convert the following NFA with -transitions into NFAs
without -transitions. 1
a) 0 ε
q0 q1 q2

b) -NFA with the following transition table

0 1 ε
A {A} ∅ {B}
B ∅ {C} {D}
C {D} ∅ ∅
* D ∅ {C} {B}
64
 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!

65
 Minimization of DFA
 Steps in constructing minimum automata
Step 1: Remove all inaccessible states.
 This can be done by enumerating all simple paths of the
graph from the initial to the final. Any state which is not
part of some path is inaccessible.

Step 2: Construct partition zero (0)

 Partition the states of an automata as a set of final states
and non-final states

0 = {Q1,Q2}
66
 Minimization …

Step 3: Construction of 1, 2, … , n

 Subsets  are obtained by partitioning 
of i+1 i
 If δ(q1,a) = X and δ(q2,a) = Y for aΣ
If X and Y are in same subset of i, q1 and q2
are equivalent, else not.
If q1 and q2 are not equivalent, separate them.
REPEAT STEP 3 Until all pairs are marked.
STOP Partitioning if i+1 = i 67
 Minimization …
Step 4: Find the set of all equivalent states and for each
set, create a state labeled by the set.
Step 5: For each transition rule of M of the form
δ(qr,a) = qp , find the sets to which qr and qp belong. Let
qr is in set X and qp in Y, then add a transition rule
δ(x,a) = Y
 The initial state is the state whose label includes q0.
 The states that contain a final state are final states.

68
 Examples
Minimize the following Automata
a)
0 1
- q1 q3
>q0 0 = {q4}, {q0,q1,q2,q3}
q1 q2 q4
1 = {q4}, {q0}, {q1,q2,q3}
q2 q1 q4
q3 q2 q4 2 = {q4}, {q0}, {q1,q2,q3}
*q4 q4 q4

69
 Examples …
Minimize the following Automata
b)

70
 Examples …
Minimize the following Automata
c)

71
 Examples …
Minimize the following Automata
d)
0 1
- q1 q4
>q0
q1 q2 q3
q2 q2 q3
*q3 q5 q6
q4 q5 q6
q5 q2 q3
q6 q5 q6
72