CSE322

Finite Automata
 UNIT I
FINITE AUTOMATA
 UNIT-I SYLLABUS

• FINITE AUTOMATA : The Equivalence of

Deterministic and Non-deterministic Finite Automata,
Definition and Description of a Finite Automaton,
Deterministic and Non-deterministic Finite State
Machines, Acceptability of a String by a Finite
Automaton, Mealy and Moore Machines, Minimization
of Finite Automata, Basics of Strings and Alphabets,
Transition Graph and Properties of Transition
Functions, Regular Languages.
Finite Automaton

Input
String
Output
“Accept”
Finite
or
Automaton
“Reject”
Finite Automata
• Finite automata are used to recognize patterns.

• It takes the string of symbol as input and changes its

state accordingly. When the desired symbol is found,
then the transition occurs.

• At the time of transition, the automata can either move

to the next state or stay in the same state.

• Finite automata have two states, Accept

state or Reject state. When the input string is
processed successfully, and the automata reached its
final state, then it will accept.
 Theory of Automata

• Theory of automata is the study of abstract

machines and the computation problems that can
be solved using these machines.

• The abstract machine is called the automata.

• The automaton consists of states and transitions.
The State is represented by circles, and
the Transitions is represented by arrows.

• Automata is the kind of machine which takes

some string as input and this input goes through a
finite number of states and may enter in the final
state.
Terminologies used in Automata

• Symbols:
• Symbols are an entity or individual objects,
which can be any letter, alphabet or any
picture.

• Example:
• 1, a, b, #
• Alphabets:
• Alphabets are a finite set of symbols. It is denoted by ∑.

• Examples:
• ∑ = {a, b}
• ∑ = {A, B, C, D}
• ∑ = {0, 1, 2}
• ∑ = {0, 1, ....., 5}
• ∑ = {#, β, Δ}
• String:
• It is a finite collection of symbols from the alphabet. The
string is denoted by w.
• Example 1:
• If ∑ = {a, b}, various string that can be generated from ∑
are {ab, aa, aaa, bb, bbb, ba, aba.....}.

• A string with zero occurrences of symbols is known as an

empty string. It is represented by ε.
• The number of symbols in a string w is called the length of a
string. It is denoted by |w|.
• Example 2:
• w = 010
• Length of String |w| = 3
• Language:
• A language is a collection of appropriate string. A language
which is formed over Σ can be Finite or Infinite.

• Example: 1
• L1 = {Set of string of length 2} = {aa, bb, ba, ab} Finite
Language
• Example: 2
• L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb,
abbb, ababb} Infinite Language
Types of Automata

• There are two types of finite automata:

1. DFA(deterministic finite automata)
2. NFA(non-deterministic finite automata)
Automaton:

An automaton is defined as a system where

- energy, materials and information are
- transformed, transmitted and used
- for performing some functions without direct participation of man.
 Finite Automata Model:

• Finite automata can be represented by input

tape and finite control.
• Input tape: It is a linear tape having some number of
cells. Each input symbol is placed in each cell.

• Finite control: The finite control decides the next state

on receiving particular input from input tape. The tape
reader reads the cells one by one from left to right, and
at a time only one input symbol is read.
Formal Definition of Finite Automaton

M  Q, ,  , q0 , F  where

Q : Finite non-empty set of states

 : Finite non empty set of input alphabets

 : (direct) transition function that maps Q x ∑ -> Q

q0 : initial state

F : set of final states

There are numerous applications of Formal languages and
Automata Theory like:

 Text processing, Compilers and Hardware Design

 Motors and Vending machines

 Sensors and Transducers

 Automata Simulators

 And many more ….

 Transition Diagram
• A transition diagram or state transition diagram is a
directed graph which can be constructed as follows:

• There is a node for each state in Q, which is represented

by the circle.

• There is a directed edge from node q to node p labeled a

if δ(q, a) = p.

• In the start state, there is an arrow with no source.

• Accepting states or final states are indicating by a double

circle.
Notations used in the transition diagram
Transition Graph

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

initial final/accepting
state state
transition
state
Initial Configuration
Input String
a b b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Reading the Input

a b b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Input finished

a b b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

accept
a b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b a

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Input finished

a b a

a, b

reject
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
 

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
 

a, b

q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4

reject
Another Example

a a b

a a, b

q0 b q1 a, b q2
a a b

a a, b

q0 b q1 a, b q2
a a b

a a, b

q0 b q1 a, b q2
a a b

a a, b

q0 b q1 a, b q2
 Input finished

a a b

a a, b
accept

q0 b q1 a, b q2
Rejection Example

b a b

a a, b

q0 b q1 a, b q2
b a b

a a, b

q0 b q1 a, b q2
b a b

a a, b

q0 b q1 a, b q2
b a b

a a, b

q0 b q1 a, b q2
Input finished

b a b

a a, b

q0 b q1 a, b q2

reject
Languages Accepted by FAs
FA M

Definition:
The language LM  contains
all input strings accepted by M

LM  = { strings that bring M

to an accepting state}
LM   abba M

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
accept
 Example
LM    , ab, abba M

a, b

q5
b a a a, b
b
q0 a q1 b q2 b q3 a q4
accept accept accept
 Example

LM   {a b : n  0}
n

a a, b

q0 b q1 a, b q2

accept trap state

Transition Function 

 :Q  Q

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
  q0 , a   q1

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
  q0 , b   q5

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
  q2 , b   q3

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
Transition Function 
 a b
q0 q1 q5
q1 q5 q2
q2 q5 q3
q3 q4 q5 a, b
q4 q5 q5
q5 q5 q5 q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
Extended Transition Function *

 * : Q  *  Q

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
  * q0 , ab   q2

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
  * q0 , abba   q4

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
  * q0 , abbbaa   q5

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
 Recursive Definition
 * q,    q
 * q, w    ( * (q, w), )

q w q1  q

 * q, w   q
 * q, w    (q1, )
 (q1, )  q
 * q, w    ( * (q, w), )
 * q, w  q1
 a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
 a, b

q5
a, b
b
q0 q1 b q3 a q4