Chapter 02 - Finite Automata

Formal Language
and Automata Theory
Chapter 2
Finite Automata (include Lecture 2 and 3)
Finite Automata Behavior Definition Model Types

Transition diagram Transition table Example DFA
DFA Example NFA NFA Example NFA equivalence
of DFA & NFA
Transparency No. 2-1
Deterministic Finite Automata
Lecture 2
Recap
Automata:
Abstract model of a digital computer
Automata can read the input but not change
Temporary storage available
Two types:
Deterministic Automata
Nondeterministic Automata
Accepter:
Automaton output response is limited to simple YES or NO i
s called accepter
Transducer:
Automaton output response is strings of symbols, is called tran
sducer
Finite Automata
Finite Automata ( FA ):
Simplest form of an automaton
It consists of only input tape and finite control unit not temporar
y storage
Tape has a read only head
Input tape is divided in to cells and each
cell can hold one symbol
It will read the left to right, it can read
one symbol at a time
While reading if it found no symbol then it stop the operation of
automata
Control unit determines the state of the automata and control th
e movement of the head on the input tape
It will accepts the regular languages
Cont.,
Cont.,
Transition diagram:
Transition diagram is defined as collection of:
Finite set of states K
Finite set of symbols
Non empty set S of K, S is called start state
Set of F of K, F is called final state
Transition function
--- Represents the states

S
--- Start symbol
Final State
Cont.,
Examples 1:
Example 2:
Cont.,
Transition Table (Transition Matrix):

Tabular representation of the finite automata. For transition fun
ction is used
Example:
Cont.,
Transition Function:
Transition or Mapping function is denoted by . Two parameter
s are passed to this transition function: one is current state and ot
her is input symbol. The transition function returns a state which c
an be called as next state.
For example
= (, a)
current state
a input
next state
Cont.,
Solved Problems for FA:

Example 2.1: Design a FA which accepts the only input 101 ov
er the input set Z = { 0, 1}.
Problem statement is mentioned only input 101 will be accepted. S
o we can simply show the transition diagram for the input.
Example 2.2: Design a FA which checks whether the given bin

ary number is even.
Even any binary number ends with 0
Ex: 2 0010,
4 0100,
6 0110,
8 1000
Odd any binary number ends with 1
Ex: 1 0001,
3 0011,
5 0101,
7 0111
Cont.,
While designing FA, assume one start state,
One state ending with 0 and another one

ends with 1. we want to check whether the
given binary number is even or odd so fix
the final state for 0 value.
Let take 2 sample inputs one odd and one even:
Case 1: For even number
Case 2: For odd number
1000 => 1000
1011 => 1 011
=> 10 00
=> 10 11
=> 100 0
=> 101 1
=> 1000
=> 1011
In case1: now at the end of input we are at final or accept state so its e
ven number
In case2: now at the end of input we are at S1 state not in final state so
its not even (odd) number
Try Yourself
1. Design a FA which accepts only those strings which starts

with 1 and ends with 0
2. Design FA which accepts even number of 0s and even num
ber of 1s
3. Consider the given transition table and Find the language
accepted by the finite automata
Inputs
States
The finite automata is called Deterministic Finite Automata if there

is only one path for a specific input from current state to next stat
e.
From the given example transition diagram
From state for input a there is only one
path going to state .
Definition:
DFA definition is same as the finite automata
DFA is a five tuple notation denoted as:
A = ( Q, , , , F)
Q finite set of states
finite set of input symbols
transition function
start state
Cont.,
Example 2.3: Design a DFA which accepts string with even nu

mber 0s and ends with 1 over = { 0, 1 }. Give Transition table
Let take the sample strings:
1, 001, 1001, 0101, 0011
will accepts the odd numbers of 0s
will accepts the even number of 0s
It should be followed by binary 1. so
will be final state.
Example 2.4: Design a DFA which accepts all the strings not h
aving more than two as over = { a, b }.
From the problem statement DFA will accepts that strings contain
maximum two as. if we try to accept 3rd as it will not lead as to fina
l state.
Cont.,
Transition Table:
Cont.,
Example 2.5: Design a DFA

L = { | m 0 and n 1 }
Step 1: m=0 and n=1
=>
Step 2: m=1 and n=1
=>
Step 3: m=1 and n=2
=>
Final transition diagram is
for accepting all strings of

1
01
011
Nondeterministic Finite Automata (NFA):
NFA is exactly reverse of DFA

Many paths for a specific input from current state to next state
From the transition diagram

Current state
Specific input a
Multi path: ,
Cont.,
Definition:
NFA formally defined as a collection of five tuple:
A = ( Q, , , , F)
transition function
start state (initial)
F set of final state
Difference between DFA and NFA:

In DFA for a given input we reach to the deterministic or unique
state
In NFA it lead to more than one state for a given input
DFA is a subset of NFA
Cont.,
Example 2.6: Construct the NFA for the given transition table
Example 2.7: Draw the transition diagram for NFA over { a, b }

containing substring aabb.
Definition of Substring: Any string of consecutive symbols in some
string is said to be a substring of that string.
For example w = abbab u = bba
String u is a substring of string w
Cont.,
Step1: For only Substring aabb
Step2: Values in front of substring: aaabb, baabb, abaabb, baaab

b
Step3: Values behind substring:aaabba, baabbb, abaabbab, baaa

bbba
Example 2.8: Draw transition diagram for NFA over {0, 1} cont
aining substring 01 and 10
This example is similar to Example 2.7:
Substring 01
Substring 10
Combine both:
= =>
Try Yourself
1. Draw the transition diagram and table for NFA in which do

uble 1 is followed by double 0 over { 0, 1 }.
2. Construct NFA accepting binary strings with two consecuti
ve 0s. consider input set = { 0, 1 }
3. Design NFA accepting all strings end with 01, over = {0,
1}
Lecture 3
NFA equivalence of DFA & NFA
NFA with
Significance of NFA:
Basically computers are deterministic machines
DFA will produce the predictable output for the certain input
Constructing deterministic machine is very difficult
NFA easy to construct
NFA can easily convert to DFA
This conversion mechanism is majorly used in compiler
NFA serves as a bridge between input given and DFA constructed
Cont.,
NFA with Transition:

In order to move from one state to another state without havin
g any symbol of input set .
With out any input symbol from q state to p state transition is happ
ened by moves
The above automata will accepts only the L = { | m, n, p 0}

For the sample input 01. First self transition happened for the stat
e for the input 0. For the second input symbol there is no transiti
on path so with transition automata reaching the state from . Af
ter that self transition happened for the input 1 in state . At last, a
utomata reaching the final state with transition from the state
Cont.,
Definition of NFA with :

language L is accepted by NFA with . M = ( Q, , , , F )
where
transition function Q x { U } to
start state
F final state
Cont.,
Definition of closure:
set of all states which are reachable from particular one state on
transition.
Example 2.9: Find the closure for the following NFA with
closure() = {, , } means self state + reachable states

closure() = {, } is a self state + is a state obtained from with in
put.
closure() = {}
Conversions and Equivalence:
NFA with can be converted to NFA without and this NFA without
can be converted to DFA. Here we are going to discuss these conv
ersions and will find them equivalent to each others
Conversion from NFA with to NFA without :

Step1: Find out all the transition from each state from Q. (find
closure for each states from Q)
Step2: Find transition (means closure on with moves)
Step3: repeat step2 for each input symbol and for each state
Step4: From the resultant transition table can construct the NFA wi
thout
Cont.,
Example 2.10: Convert the given NFA with to NFA without

Step1: Find closure for each states:
Step2: Find transition for each state on each input symbol:
Cont.,
Cont.,
Cont.,
Example 2.11: convert the following NFA with to NFA withou

t
Step1: Find closure for each states:
Step2: Find transition for each state on each input symbol:
Cont.,
Cont.,
Cont.,
Cont.,
NFA without to DFA:

Let M = ( Q, , , , F ) is a NFA which accepts the language L(M)
M = ( Q, , , , F ) is a DFA which accepts the language L(M)
Steps:
1. Start state of the NFA will be the start state of DFA
2. Find transition for each state in Q and for each input symbols c
an obtained as:
([q0, q1, q2], a) = (q0, a) U (q1, a) U (q2, a)
= [q0, q1, q2. qn ] some states
Add the state to DFA if it is not added already in Q
If no new state is generated then stop the step 2 process
3. Fix the final state
Cont.,
Example 2.12: Construct the DFA for the given NFA transition
table.
From the given transition table:
left side and states are
available. In right side {, }
new state is available. For this
new state, we have to find the transition for new state {, } on each i
nput {0, 1}
Cont.,
Cont.,
Example 2.13: Convert the given NFA to DFA

From the given table: In left side
,, , are the states. In right side
{, } new state available. So we have
to find the transition for the new {, }
state on each input {0, 1}.
Cont.,
New state {, , } is created in the previous computation, so again fin

d the transition for the new state {, , } on each input.
([, , ], 0) = (,0) U (,0) U (,0)
= {, } U { U { = {, , , }
Here also new state {, , , } is generated
([, , ], 1) = (,1) U (,1) U (,1)
= { U { U { = {, , }
Here also new state {, , } is generated. Again find the transition for
the above two new states on each input.
([, , , ], 0) = (,0) U (,0) U (,0) U (,0)
= {, } U { U { U = {, , , }
([, , , ], 1) = (,1) U (,1) U (,1) U (,1)
= { U { U { U { = {, , , }
No more new states so we can finish the computation
Cont.,
In the given NFA q is a final state so in DFA where ever exits that s
3
tate become final state of DFA.
Try yourself
1. Convert the given NFA to DFA
End of Chapter - 02
Problems
Solved Problems
Cont.,
1. Design a FA which accepts only those strings which starts

with 1 and ends with 0
2. Design FA which accepts even number of 0s and even num

ber of 1s
Cont.,
3. Consider the given transition table and Find the language a

ccepted by the finite automata
Cont.,
Draw the transition diagram for the given transition table
It will accepts the even no of 1s and even no of 0s. for example: st

rings are: 0011, 1010. 1001, 111100, etc.,
Cont.,
4. Draw the transition diagram and table for NFA in which do

uble 1 is followed by double 0 over { 0, 1 }.
Finite Automata for double 1
Automata for double 1 is followed by 0
Prefix and suffix on the previous automata
Sample input string: 1100, 11100, 01100

101100, 01100, 11000, 11001, 110000
110010
Cont.,
5. Construct NFA accepting binary strings with two consecutiv

e 0s. consider input set = { 0, 1 }
Automata for consecutive two 0s:
Prefix and suffix input values on consecutive 0s
Sample input string: 00, 000, 100, 0000, 0100, 000, 001, 0001, 00
10
Cont.,
6. Design NFA accepting all strings end with 01, over = {0,
1}
Automata for 01
String end with 01. So automata with prefix input values
Sample input: 01, 001, 101, 0001, 0101, 1001, 1101


Chapter 02 - Finite Automata

Uploaded by

Copyright:

Available Formats

Chapter 02 - Finite Automata

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 02 - Finite Automata

Uploaded by

Copyright:

Available Formats

Formal Language

and Automata Theory

Finite Automata Behavior Definition Model Types

Transparency No. 2-1

Deterministic Finite Automata

Transparency No. 2-2

Deterministic Finite Automata

Deterministic Finite Automata

Deterministic Finite Automata

Transparency No. 2-5

Deterministic Finite Automata

--- Represents the states

--- Start symbol

Transparency No. 2-6

Deterministic Finite Automata

Transparency No. 2-7

Deterministic Finite Automata

Transition Table (Transition Matrix):

Transparency No. 2-8

Deterministic Finite Automata

Transparency No. 2-9

Deterministic Finite Automata

Solved Problems for FA:

Example 2.2: Design a FA which checks whether the given bin

Deterministic Finite Automata

While designing FA, assume one start state,

One state ending with 0 and another one

Deterministic Finite Automata

1. Design a FA which accepts only those strings which starts

Transparency No. 2-12

Deterministic Finite Automata

Deterministic Finite Automata

The finite automata is called Deterministic Finite Automata if there

Deterministic Finite Automata

Example 2.3: Design a DFA which accepts string with even nu

Deterministic Finite Automata

Transparency No. 2-15

Deterministic Finite Automata

Example 2.5: Design a DFA

for accepting all strings of

Transparency No. 2-16

Deterministic Finite Automata

Nondeterministic Finite Automata (NFA):

NFA is exactly reverse of DFA

From the transition diagram

Deterministic Finite Automata

Difference between DFA and NFA:

Deterministic Finite Automata

Example 2.7: Draw the transition diagram for NFA over { a, b }

Deterministic Finite Automata

Step1: For only Substring aabb

Step2: Values in front of substring: aaabb, baabb, abaabb, baaab

Step3: Values behind substring:aaabba, baabbb, abaabbab, baaa

Transparency No. 2-20

Deterministic Finite Automata

Transparency No. 2-21

Deterministic Finite Automata

1. Draw the transition diagram and table for NFA in which do

Transparency No. 2-22