Finite State Automata
Module - 2
• Finite State Automata
• Finite automata
• Deterministic Finite automata (DFA)
• Non-deterministic Finite automata (NFA)
Finite Automata (FA)
• An automaton is an abstract model of a digital computer
• Mathematical model of a system with discrete inputs and
outputs
• Example:
c
Working Principle of FA
• Input Tape:
• Inputs are written on a Input Tape
tape, read by automaton
but cannot change it String
• Input tape is divided into
cells, each of which can Output
hold one symbol
Finite “Accept”
• Finite Automaton
Automaton or
• Finite number of states
• Control state transitions / [Control Unit] “Reject”
changes
FSA Applications
• Lexical analysis (Compiler) recognition of tokens
• Thermostats (fridge)
• Elevators
• Train Track Switches
• Text editing
• Image compression
• Computer Network
Representation of FA
• A Finite Automaton (FA) is represented by a 5-tuple (Quintuple)
M = (Q, Σ, , S, F)
Where,
Q is the set of states (finite)
Σ is the alphabet (finite)
: Q Σ → Q is the transition function
S Q is the start state
F Q is the set of accept states
Q = {q0 , q1} , Σ = {a, b}
n(Q) = 2 , n(Σ) = 2
A x B = { (x, y) / x A , y B } - Cartesian Product of A and B
n(A x B) = n(A) . n(B)
Q x Σ = { (q0, a), (q0, b), (q1, a), (q1, b) }
n(Q x Σ) = n(Q). n(Σ) = 2 . 2 = 4
:QΣ→Q
:QΣ→Q
QΣ Q
(q0, a) q1
(q0, b)
q0
(q1, a)
(q1, b)
(q0, a) = q1
(q0, b) = q0
(q1, a) = q1
(q1, b) = q0
Transition Diagram
• A directed graph associated with the vertices of the graph
corresponds to the states of Finite Automata
• If there is a transition from state A to state B on input symbol ‘0’,
then there is an arc with label ‘0’ is drawn from state A to state B
• FA accepts a string, ‘x’, if the sequence of transitions
corresponding to the symbols of ‘x’ leads from the start state to
an accepting state
Example
q0 0,1
0 0
L(M) = {0, 1}*
1
q0 q1
1
L(M) = {w | w has an even number of 1s}
Checking acceptance of string using FA
11 1
0
0,1
1
0111 111 1
0 0
Read string left to right 1
The machine accepts a string if the process ends in a double circle
To accept a string:
all the input string is scanned
and the last state is accepting
To reject a string:
all the input string is scanned
and the last state is non-accepting
head Initial Configuration
Input Tape
a b b a
Input String
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
Initial state
Scanning the Input
a b b a
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
a b b a
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
a b b a
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
Input finished
a b b a
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
accept
Language Accepted: L abba
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
A Rejection Case
a b a
Input String
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
a b a
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
a b a
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
Input finished
a b a
a, b
reject
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
Another Rejection Case
Tape is empty
( )
Input Finished
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
reject
Another Example
L
a, b
q5
b a a a, b
b
q0 a q1 b q2 b q3 a q4
Accept Accept Accept
state state state
Empty Tape
( )
Input Finished a, b
q5
b a a a, b
b
q0 a q1 b q2 b q3 a q4
accept
Another Example
a a, b
b a, b
q0 q1 q2
Accept trap state
state
a a b
Input String
a a, b
b a, b
q0 q1 q2
a a b
a a, b
b a, b
q0 q1 q2
a a b
a a, b
b a, b
q0 q1 q2
Input finished
a a b
a a, b
accept
b a, b
q0 q1 q2
A rejection case
b a b
Input String
a a, b
b a, b
q0 q1 q2
b a b
a a, b
b a, b
q0 q1 q2
b a b
a a, b
b a, b
q0 q1 q2
Input finished
b a b
a a, b
b a, b
q0 q1 q2
reject
Language Accepted: L {a b : n 0 }
n
a a, b
b a, b
q0 q1 q2
Example 1 – String acceptance
1. Given a finite automata, M = ({q0, q1}, {0, 1}, , q0, {q1}) and
transition diagram as given below:
0 1
q0 q1 1
a) Check whether the input string 10101 is accepted by M or not.
b) Check whether the input string 101100 is accepted by M or
not.
Example 1 – cont…
a) 1 0 1 0 1 The string 10101 is accepted because it
q0 q1 q0 q1 q0 q1 ends in the final / acceptance state
Start Accepted
b) 1 0 1 1 0 0
q0 q1 q0 q1 q1 q0 q0
Start Not accepted
The string 101100 is not accepted because it does not ends
in the final / acceptance state
Example 2
2. Given a finite automata, M = ({a, b, c, d}, {0, 1}, , a, {a}) and
transition table as given below:
0 1
a c b
b d a
c a d
d b c
a) Check whether the input string 110101 is accepted by M or not.
b) Check whether the string 110011 is accepted by M or not.
Types of Finite Automata
1. Deterministic Finite Automata (DFA)
2. Non-deterministic Finite Automata (NFA / NDFA)
1. Deterministic Finite Automaton (DFA)
• On each input symbol, there is one and only one state to
which the automaton can have transition from its current state
M Q, , , q0 , F
Q : Set of states
: Input alphabet
: Transition function
q0 : Initial state
F : Set of accepting states
Set of States Q
Example
Q q0 , q1, q2 , q3 , q4 , q5
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
Input Alphabet
Example
a, b a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Initial State q0
Example
a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
Set of Accepting States F Q
Example
F q4 a, b
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4
Transition Function : Q Q
( q, x ) q
x
q q
Describes the result of a transition
from state q with symbol x
Example:
q0 , a q1
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
q0 , b q5
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
q2 , b q3
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Transition Table for
symbols
a b
q0 q1 q5
q1 q5 q2
q2 q5 q3
states
a, b
q3 q4 q5
q4 q5 q5 q5
a, b
q5 q5 q5 b a a b
q0 a q1 b q2 b q3 a q4
Extended Transition Function
To read zero / more symbols of input string at a time
:Q Q
* *
(q ,w ) q
*
Describes the resulting state
after scanning string w from state q
Cont.,
^
Extend to : Q * Q
a q1 b c
^ q0 q2 q3
1) (q, ) q, q Q
^ ^
( q 0 , abc ) ( ( q 0 , ab ), c )
x ,a ,q Q
* ^
2) ( ( ( q 0 , a ), b ), c )
^
^ ^
( ( ( ( q 0 , ), a ), b ), c )
(q, xa) ( (q, x), a)
( ( ( q 0 , a ), b ), c )
( ( q1 , b ), c )
( q 2 , c ) q3
Example:
* q0 , ab q2
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
* q0 , abbbaa q5
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
q1 , bba q4
*
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Special case: No transition,
for any state q
q, q
*
Language Accepted by DFA
Language of DFA: M
It is denoted as L M and contains all the strings
accepted by M
We say that a language L is accepted (or recognized)
by DFA M
if L M L
• For a DFA M Q, Σ, δ, q0, F
• Language accepted by M :
L M w *
: *
q 0 , w F
q0 w q q F
• Language rejected by : M
L M w : q0 ,w F
* *
q0 w q q F
Problems – Construction of DFA
1. Construct a DFA that accepts all and only the string of 0’s and
1’s that have the sequence 01 somewhere in the string.
Soln:
Language, L = {x 01 y | x and y any strings of 0’s and 1’s}
Alphabet, = {0, 1}
Transition diagram:
1 0 0, 1
start 0 1
q0 q1 q2
Problem 1 – cont…
• Transition States Transition table
(q0, 0) = q1
0 1
(q0, 1) = q0
(q1, 0) = q1 q0 q1 q0
(q1, 1) = q2 q1 q1 q2
(q2, 0) = q2 q2 q2 q2
(q2, 1) = q2
Therefore, the Automaton that accepts language L,
A = {(q0, q1, q2), (0, 1), , q0, q2}
Problem 2
Construct the DFA’s accepting the following language over the
alphabet {0, 1}
a) The set of all strings ending with ‘00’
b) The set of strings with three consecutive 0’s
Soln:
1
a) 1
0
start 0 0
q0 q1 q2
1
Problem 2 – cont…
Soln:
1
b) 1 0, 1
start 0 0 0
q0 q1 q2 q3
1
Problems
3. Construct DFA that accepts input string of 0’s and 1’s that end
with 11
0
0
1
start 1 1
q0 q1 q2
4. Construct DFA that accepts all strings with three consecutive
1’s at its end
0
0 1
start 1 1 1
q0 q1 q2 q3
0
0
Problems – cont…
5. Construct DFA for all strings with {0, 1} that has even number
of 0’s and 1’s. 1
start A B
1
0 0 0 0
1
C D
1
6. Construct DFA for the language L = {0n | n mod 3 = 2, n 0}
start 0 0
q0 q1 q2
0
Cont.,
• L(G) = { abnam / n ≥ 2, m ≥ 3 }
• L(G) = { w1abw2 / w1 , w2 {a, b}* }
Cont…
• Construct a DFA for the language accepting strings starting
with ‘ab’ over input alphabets ∑ = {a, b}
• Soln:
Construction of DFA
• All strings ending with ‘n’ length substring will always require
minimum (n+1) states in the DFA.
• All strings starting with ‘n’ length substring will always require
minimum (n+2) states in the DFA.
Problems – DFA to Language
1. Consider DFA with the following transition table. Find the language
accepted by DFA 0 1
a a b
*b b a
Soln: The language, L = { w | w is the string with odd number of 1’s}
0 1
2. Consider the following DFA and find language accepted by DFA.
a a b
*b - c
c c b
Soln: The language, L = { w | w set of strings ends with 1 and has odd
number of 1’s}
Non-Deterministic Finite Automata (NFA)
• The transition function that takes a state and input
symbol as arguments then returns zero or more states.
• Example
0, 1 0, 1
start 1
q1 q2
Representation of NFA
• A NFA can be represented as,
N Q, , , q0 , F
Q : Finite set of states
: Finite set of Input symbols
: Transition function, Q X { {}} 2Q
q0 : Initial / Start state
F : Set of accepting states
Problems – Construction of NFA
1. Construct NFA for set of all strings {0, 1} that end with string 00.
Soln:
Step 1: Language, L = {w | w is set of all strings that end with string 00}
Step 2: Alphabet, = {0, 1}
Step 3: Transition Diagram
0, 1
0
start 0 0
q0 q1 q2
1
1
Step 4: NFA, N = [{q0, q1, q2}, {0, 1}, , q0, {q2}]
Problems – Construction of NFA
2. Construct NFA with abb as substring.
Soln:
Step 1: Language, L = {x | x is set of all strings with abb as substring}
Step 2: Alphabet, = {a, b}
Step 3: Transition Diagram
a, b
a, b
start a b b
q0 q1 q2 q3
Step 4: NFA, N = [{q0, q1, q2 , q3}, {a, b}, , q0, {q3}]
Problems – Cont…
3. Construct NFA with 101 as substring.
1, 0
1, 0
start 1 0 1
q0 q1 q2 q3
4. Construct NFA for set of all strings that ends with three
consecutive 1’s at its end.
1, 0
1
start 1 1 1
q0 q1 q2 q3
Problem 1 – Checking acceptance of string
Construct an NFA for the set of strings with {0, 1} ending with 01
and draw the transition table for the same and check whether the
input string 00101 is accepted by NFA.
Soln:
Step 1: Language, L = {x | x is set of all strings ending with 01}
Step 2: Alphabet, = {0, 1}
Step 3: Transition Diagram
0, 1 0
start 0 1
q0 q1 q2
0, 1
Step 4: NFA, N = [{q0, q1, q2}, {a, b}, , q0, {q2}]
Cont…
0, 1 0
start 0 1
Step 5: Input String = 00101 q0 q1 q2
’(q0, ) = q0
’(q0, 0) = (q0, 0) = {q0, q1} 0, 1
’(q0, 00) = (’(q0, 0), 0) = ({q0, q1}, 0)
= (q0, 0) (q1, 0) = {q0, q1} {q1} = {q0, q1}
’(q0, 001) = (’(q0, 00), 1) = ({q0, q1}, 1)
= (q0, 1) (q1, 1) = {q0, q2}
’(q0, 0010) = (’(q0, 001), 0) = ({q0, q2}, 0)
= (q0, 0) (q2, 0) = {q0, q1}
’(q0, 00101) = (’(q0, 0010), 1) = ({q0, q1}, 1)
= (q0, 1) (q1, 1) = {q0, q2}
Cont..
Step 6:
To check the acceptance of the string
’(q0, 00101) F = {q0, q2} {q2} = {q2}
Therefore, the string 00101 is accepted.
Problem 2
• Consider the given NFA and check whether the input ‘abaab’ is
accepted or not.
a b
q0 {q0, q1} {q0, q3}
q1 {q2}
*q2 {q2} {q2}
q3 {q4}
*q4 {q4} {q4}
NFA with - transition
• NFA can be extended to NFA- transition for an empty string
• NFA- has 5-tuples, M=(Q, , , S, F) [Identical to NFA]
• In NFA-, there will be a state transition on an input symbol
start
q1 q2
Problems – Construction of NFA-
• Construct NFA- that end with string 11 for the set of all strings {0, 1}
Soln:
Step 1: Language, L = {w | w is set of all strings that end with string 11}
Step 2: Alphabet, = {0, 1}
Step 3: Transition Diagram
0, 1
1
start 1 1
q0 q1 q2
Step 4: NFA-, NE = [{q0, q1, q2}, {0, 1}, , q0, {q2}]
Problems – cont…
2. Construct NFA- with 011 as substring for set of all strings {0, 1}.
Soln:
Step 1: Language, L = {x | x is set of all strings with 011 as substring}
Step 2: Alphabet, = {a, b}
Step 3: Transition Diagram
1, 0
1, 0
start 0 1 1
q0 q1 q2 q3
Step 4: NFA-, NE = [{q0, q1, q2, q3, q4}, {0, 1}, , q0, {q3}]
Problems – Acceptance of strings
• -closure: the -closure of q0 [-closure(q0)] denotes the set of all
states ‘P’ such that there is a path or transitions from q0 to P on .
• Path from current state to set of states that has ‘’ transitions
• Set of all states that can be reached from q0 via one or more ε transitions
1. Consider the following NFA- and find the -closure for each
state and check whether the string ‘abb’ is accepted or not.
a b c
start
q0 q1 q2
a b
• Soln:
-closure(q0) = {q0, q1, q2} [Path from current state to set of states that has ‘’ transitions]
-closure(q1) = {q1, q2}
-closure(q2) = {q2}
Cont (1) start
a
b
c
q0 q1 q2
• Input string: ‘abb’
a b
’(q0, ) = -closure(q0) = {q0, q1, q2}
’(q0, a) = -closure(’((q0, ), a))
= -closure(({q0, q1, q2}, a))
= -closure((q0,a) (q1,a) (q2,a))
= -closure({q0, q1} )
= -closure({q0, q1})
= -closure(q0) -closure(q1)
= {q0, q1, q2} {q1, q2}
= {q0, q1, q2}
Cont (2) start
a
b
c
q0 q1 q2
a b
’(q0, ab) = -closure(’((q0, a), b))
= -closure(({q0, q1, q2}, b))
= -closure((q0,b) (q1,b) (q2,b))
= -closure( {q1, q2} )
= -closure({q1, q2})
= -closure(q1) -closure(q2)
= {q1, q2} {q2}
= {q1, q2}
a b c
Cont (3) start
q0
q1
q2
’(q0, abb) = -closure(’((q0, ab), b)) a b
= -closure(({q1, q2}, b))
= -closure((q1,b) (q2,b))
= -closure({q1, q2} )
= -closure({q1, q2})
= -closure(q1) -closure(q2)
= {q1, q2} {q2}
= {q1, q2}
Final State, F = {q2}
Therefore {q1, q2} F = {q1, q2} {q2} = {q2} ==> member in final state
So, the string ‘abb’ is accepted by NFA-