CSE322
Finite Automata
YUMS APP
Lecture #2
Topics
➢ Acceptability of a String by a Finite Automaton
➢ Transition Graph and Properties of Transition Functions
YUMS APP
Finite Automaton
Input
String
YUMS APP
Output
“Accept”
Finite
or
Automaton
“Reject”
Transition Graph
a, b
q5
a YUMS a, b
b a APP b
q0 a q1 b q2 b q3 a q4
initial accepting
state state
transition
state
Initial Configuration
Input String
a b b a
a, b
YUMS APP
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
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b b a
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b b a
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b b a
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Input finished
a b b a
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
accept
Rejection
a b a
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b a
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b a
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a b a
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Input finished
a b a
a, b
YUMS APP reject
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Another Rejection
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
reject
Another Example
a a b
a YUMS APP
a, b
b a, b
q0 q1 q2
a a b
a YUMS APP
a, b
b a, b
q0 q1 q2
a a b
a YUMS APP
a, b
b a, b
q0 q1 q2
a a b
a YUMS APP
a, b
b a, b
q0 q1 q2
Input finished
a a b
a YUMS APP
a, b
accept
b a, b
q0 q1 q2
Rejection Example
b a b
a YUMS APP
a, b
b a, b
q0 q1 q2
b a b
a YUMS APP
a, b
b a, b
q0 q1 q2
b a b
a YUMS APP
a, b
b a, b
q0 q1 q2
b a b
a YUMS APP
a, b
b a, b
q0 q1 q2
Input finished
b a b
a YUMS APP
a, b
b a, b
q0 q1 q2
reject
Languages Accepted by FAs
FA M
Definition:
The language L( M ) contains
all input strings accepted by M
YUMS APP
L(M ) = { strings that bring M
to an accepting state}
L(M ) = abba M
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
accept
Example
L(M ) = , ab, abba M
a, b
YUMS APP
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 YUMS APP
a, b
b a, b
q0 q1 q2
accept trap state
Transition Function
:Q → Q
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
(q0 , a ) = q1
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
(q0 , b ) = q5
a, b
YUMS APP
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
(q2 , b ) = q3
a, b
YUMS APP
q5
a a, b
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 YUMS APP 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
YUMS APP
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
* (q0 , ab ) = q2
YUMS APP
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
* (q0 , abba ) = q4
YUMS APP
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
* (q0 , abbbaa ) = q5
YUMS APP
a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
Recursive Definition
* (q , ) = q
* (q, w ) = ( * (q, w), )
q w
YUMS APP
q1 q
* (q , w ) = q
* (q, w ) = (q1, )
(q1, ) = q
* (q, w ) = ( * (q, w), )
* (q, w) = q1
YUMS APP a, b
q5
a a, b
b a b
q0 a q1 b q2 b q3 a q4
YUMS APP a, b
q5
a, b
b
q0 q1 b q3 a q4
