Lecture 1,2,3
Lecture 1,2,3
Lecture 1,2,3
Finite Automata
UNIT I
FINITE AUTOMATA
UNIT-I SYLLABUS
Input
String
Output
“Accept”
Finite
or
Automaton
“Reject”
Finite Automata
• Finite automata are used to recognize patterns.
• 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.....}.
• 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
M Q, , , q0 , F where
q0 : initial state
Automata Simulators
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 LM contains
all input strings accepted by M
a, b
q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
accept
Example
LM , 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
LM {a b : n 0}
n
a a, b
q0 b q1 a, b q2
: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