Finite Automata

Ashim Dey
Lecturer, CSE, CUET

1
Slide courtesy: Prof. Dr. M. Moshiul Hoque, CSE, CUET
 Finite Automata
A finite automaton has a set of states
and it control moves from state to state
in response to external inputs
Deterministic: automation cannot be in
more than one state at any time
Nondeterministic: automation can be
several states at once

2
 Informal Picture of Finite
Automata
Finite automata are good models for
computers with an extremely limited amount
of memory
 -electromechanical devices
 The controller for an automatic door is one
example of such a device
• Often found in supermarket entrances/exits,
automatic doors swing open when sensing that a
person is approaching
3
 Informal Picture of Finite Automata
 Two states: OPEN or CLOSED
 04 input conditions: Front Rear
pad pad
1. FRONT (a person is standing
on the pad in front of the
doorway) door
2. REAR (a person is standing
on the pad to the rear of the REAR/BOTH/ FRONT/REAR /
NEITHER BOTH
doorway) FRONT

3. BOTH (people are standing

CLOSED
on both pads) Open

4. NEITHER (no one is standing

on either pad) NEITHER
4
 State table
Input signal
NEITHER FRONT REAR BOTH
CLOSED CLOSED OPEN CLOSED CLOSED
OPEN CLOSED OPEN OPEN OPEN

•Controller moves from state to state, depending on input

• when CLOSED state & input NEITHER/REAR, it remains in
CLOSED state
•If the input BOTH, it stays CLOSED because opening the door
Risks knocking someone over on the rear pad
•But if input FRONT, it moves to the OPEN state
•In the OPEN state, if input FRONT/REAR/BOTH, it remains OPEN
5
 Other Examples
This controller is a computer that has just
a single bit of memory, capable or
recording which is two states the
controller is in
Others: elevator controller, dishwashers,
thermostat, digital watches, calculators etc

6
Deterministic Finite Automata (DFA)
Deterministic: on each input there is one
state to which the automaton can transition
from its current state
In terms of 05 tuples:
A  (Q,  , , q0 , F )

A: DFA, Q: set of states, : input symbols,

: transition function, q0: start state, F: set
of accepting state
7
 DFA
 A formalism for defining languages,
consisting of:
1. A finite set of states (Q, typically).
2. An input alphabet (Σ, typically).
3. A transition function (δ, typically).
4. A start state (q0, in Q, typically).
5. A set of final states (F ⊆ Q, typically).
 “Final” and “accepting” are synonyms denoted by
Double Loops.
8
 The Transition Function
Takes two arguments: a state & an input
symbol; returns a state
δ represented by an arc between states
and the labels on the arcs.
δ(q, a) = the state that the DFA goes to
when it is in state q & input a is received.
q state (current) to p state (next): an arc
labeled with a
9
 How a DFA Process Strings
How the DFA decides whether or not to
‘accept’ a sequence of input symbols
The language of the DFA is the set of all
strings that the DFA accepts.
Sequence of input symbols: a1, a2, …….an
 initial state: q0
Transition function, (q0, a1)= q1 to find
state that the DFA A enters after
processing the first input symbol a1 10
 How a DFA Process Strings
Process next input symbol, a2: (q1, a2)= q2
 continue in this way, finding states q3, q4,..
qn, such that (qi-1, ai)= qi for each i
If qn is a member of F, then the input
a1a2…an is accepted,
if not then it is rejected.

11
 Example
Specify a DFA that accepts all and only the
strings of 0’s and 1’s that have the
sequence 01 somewhere in the string.
L as:
{w| w is of the form x01y for some strings
x & y consisting of 0’s & 1’s only}
 {x01y| x & y are any strings of 0’s & 1’s}
12
 Example
Strings: 01, 11010, 100011 exists in L
, 0, & 111000 not exist in L
={0,1}
(q0,1)=q0
(q0,0)=q2
(q2,0)=q2
(q2,1)=q1
(q1,0)=(q1,1)=q1 13
 Example
Q = {q0, q1, q2}, F = {q1}
The complete specification of the
automation A that accepts the L of
strings that have a 01 substring:
A = ({q0, q1, q2}, (0,1), , q0, {q1})

14
 Notations for DFA’s
Specifying a DFA as 5 tuple with a
detailed description of the  transition
function: tedious & hard to read
Two notations:
1. Transition diagram
2. Transition table

15
 Transition Diagram
Nodes = states.
Arcs represent transition function.
 Arc from state p to state q labeled by all
those input symbols that have transitions
from p to q.
Arrow labeled “Start” to the start state.
Final states indicated by double circles.

16
 Example
Draw the Transition Diagram for the DFA
accepting all string with a substring 01.

1 0 0,1
Start 0 1
q0 q2 q1

A=({q0,q1,q2},{0,1},  ,q0,{q1})
Check with the string 01,11010,100011,
0111,110101,11101101, 111000 17
 Another Example
 Accepts all strings without two consecutive 1’s.

0 0,1
1 1
A B C

Start 0
Previous Previous Consecutive
string OK, String OK, 1’s have
does not ends in a been seen.
end in 1. single 1.
18
 Transition Table
A conventional, tabular representation of a
function like  that takes two arguments & return
a value.
Rows: states; corresponding to state q
Columns: inputs; corresponding to input a is
the state (q,a)

 The start state is marked with an arrow and accepting

states are marked with a star.

19
 Example
0 0,1
1 1
A B C

Start 0
Final states
starred Columns =
0 1 input symbols
* A A B
Arrow for * B A C
start state C C C

Rows = states 20
 Example

1 0 0,1
Start 0 1
q0 q2 q1

 (q0,0)=q2
 (q0,1)=q0 0 1
 (q1,0)=q1 q0 q2 q0
 (q1,1)=q1
*q1 q1 q1
 (q2,0)=q2
 (q2,1)=q1 q2 q2 q1
21
 Extended Transition Function
An Extended Transition Function that describes
what happen when we start in any state and
follow any sequence of inputs.

 Transition Function
^
δ  Extended Transition Function
a function that takes a state q & a string w & returns a
state p-the state that the automaton reaches when starting
in state q & processing the sequence of inputs w
22
 Extended Transition Function
We describe the effect of a string of
inputs on a DFA by extending δ to a
state and a string.
Induction on length of string.
Basis: ^δ (q, ε) = q
Induction: δ (q,wa) =δ( δ (q,w),a)
^ ^

 w is a string; a is an input symbol.

23
 Induction
2. ^
δ (q,w)= ( ^δ (q,x),a)=  (p,a)
w xa
a last symbol = 1
w string = 1101
x string consisting of all but the
last symbol = 110

24
 Extended δ: Intuition
Convention:
 … w, x, y, z are strings.
 a, b, c,… are single symbols.
Extended δ is computed for state q and
inputs a1a2…an by following a path in
the transition graph, starting at q and
selecting the arcs with labels a1, a2,…,an
in turn.
25
Example: Extended Delta
0 1
A A B
B A C
C C C

^ ^
δ (B,011) = δ(δ (B,01),1) = δ(δ(δ(B,0),1),1) =

δ(δ(A,1),1) = δ(B,1) = C

26
 Delta-hat
In book, the extended δ has a “hat” to
distinguish it from δ itself.
Not needed, because both agree when
the string is a single symbol.
˄ ˄
δ(q, a) = δ(δ(q, ε), a) = δ(q, a)

Extended deltas

27
 Example
Let us design a DFA to accept the language
L={w | w has both an even number of 0’s
and even number of 1’s} q00(even) 1 (even)
q10(even) 1 (odd)
1
q20(odd) 1 (even)
q30(odd) 1 (odd)
Start
q q
0
1 1
0 1
*q0 q2 q1 0 0 0 0
q1 q3 q0
1
q2 q0 q3 q q
2 3
q3 q3 q1 1 28
 Example with Transition Table
0 1
^
*q0 q2 q1  (q0, €) = q0
^ ^
q1 q3 q0
 (q0,1) = ((q0, €),1) = (q0,1) = q1
q2 q0 q3
q3 q3 q2  (q0,11) = ((q^0, 1),1) = (q1,1) = q0
^
^ ^
 (q0,110) = ((q0,11),0) = (q0,0) = q2
 w= 110101 ^
(q0,1101) = ((q^
 0,110),1) = (q2,1) = q3

 x= 11010  ^
(q ,11010) = ((q^,1101),0) = (q ,0) = q
0 0 3 1
^
 a= 1  ^
(q0,110101) = ((q0,11010),1) = (q1,1) = q0
^
δ (q0,110101)=q0
Accepted

29
 Example: Try Yourself
A = {w | w contains at least one 1 and
an even number of 0s follow the last 1
Hints: A1 = (Q, , , q1, F)
1. Q = {q1, q2, q3}
2.  = {0, 1}
3.  try yourself
4. Start state: q1
5. Final state: {q2}
30
31
 Example
0 1 1

q1 q2
0

A2= ({q1, q2}, (0,1), , q1, {q2})

Transition function,  0 1
Try: 1101, 11010, 0011010 q1 q1 q2
L(A2) = {w | w ends in a 1} *q2 q1 q2
32
 Example
0 1 1

q1 q2
0

A3= ({q1, q2}, (0,1), , q1, {q1})

Transition function,  0 1
Try: 1101, 11010, 0011010 *q1 q1 q2
L(A3) = {w | w is  or ends q2 q1 q2
in a 0} 33
 Example
A4 accepts all strings that start and end
with a or that start and end with b
A4 accepts strings, that start and end with
the same symbol

a s b
a b
q1 r1
b a a b
q2
b r2
a
34
 Language of a DFA
Automata of all kinds define languages.
If A is an automaton, L(A) is its
language.
For a DFA A, L(A) is the set of strings
labeling paths from the start state to a
final state.
Formally: L(A) = the set of strings w
such that δ(q0, w) is in F.
35
Example: String in a Language
String 101 is in the language of the DFA below.
Start at A.

0 0,1
1 1
A B C

Start 0

36
Example: String in a Language
String 101 is in the language of the DFA below.

Follow arc labeled 1.

0 0,1
1 1
A B C

Start 0

37
Example: String in a Language
String 101 is in the language of the DFA below.

Then arc labeled 0 from current state B.

0 0,1
1 1
A B C

Start 0

38
Example: String in a Language
String 101 is in the language of the DFA below.
Finally arc labeled 1 from current state A. Result
is an accepting state, so 101 is in the language.
0 0,1
1 1
A B C

Start 0

39
 Example – Concluded
The language of our example DFA is:
{w | w is in {0,1}* and w does not have
two consecutive 1’s}

Such that… These conditions

about w are true.
Read a set former as
“The set of strings w…
40
 Try Yourself
Give DFA’s accepting the following
languages over the alphabet {0,1}
a) The set of all strings ending in 00
b) The set of all strings with three
consecutive 0’s (not necessarily at the
end)
c) The set of strings with 011 as a
substring
41
String ending in 00

42
43
011

44
 Try Yourself
Give DFA’s accepting the following languages
over the alphabets {0,1}
a) The set of all strings such that each block of
five consecutive symbols contains at least
two 0’s
b) The set of al strings whose tenth symbol
from right end is a 1
c) The set of strings such that the number of
0’s is divisible by five, and the number of 1’s
is divisible by 3 45
(a) 5 block But how ??????????????

46