Finite Automata

(FA)

Lecture 3.2
 Lecture Outline
● This lecture covers:
○ Finite automata
○ Finite automata classes
○ Deterministic finite automata
○ Nondeterministic finite automata
○ Finite automata formal definition
○ Applications of finite automata
 Finite Automata
• Finite Automata, FA (also called Finite State
Machine) is a model of computation with finite set of
states and which acts as a language acceptor
• FA state can change from one to another upon
receiving some input symbol
• FA has fixed memory capacity to handle information
and does not have auxiliary memory
 Finite Automata (II)
• When FA receives a string input, it can either accept
or reject it hence generally regarded as language
acceptors or language recognition device
• Any computer whose outputs are either “yes” or “no”
acts as a language acceptor
• The language the computer accepts is the set of
input strings that cause it to produce the answer yes
 Finite Automata (III)
• A language is called a regular language if some
finite automaton recognizes it
• Due to memory limitation, FA’s can only accept
simple languages which does not require
remembering more than the current state
 Finite Automata (IV)
• The machine reads the input
string one at a time until the
end of string
• If it winds up in one of the set
of final states the input string
is considered to be accepted
otherwise rejected
• The language accepted by
the machine is the set of FA Basic Design
strings it accepts
 Finite Automata (V)
• FA is the simplest
START
computational model,
with very limited
off
memory, but highly
PUSH PUSH
useful
• Example: a finite
automaton modeling an
on/off switch On
 Finite Automata Classifications
• Finite automata can be classified into two major
categories
1. Deterministic Finite Automata ( DFA)
2. Nondeterministic Finite Automata ( NFA )
Deterministic Finite Automata (DFA)
 Formal Definition of DFA
• DFA is defined by a 5 -tuple:
(Q, Σ, δ,q0, F)
1. Q: finite set of states
2. Σ: finite alphabet
3. δ: transition function, δ : Q x Σ →Q, takes a state
and input symbol as arguments, and returns a
state
4. q0∈Q: start state
5. F∈Q: set of accept states
 Finite State Diagram
• A graphic representation of a finite automaton
• A finite state diagram is a directed graph, where
nodes represent elements in Q (i.e., states) and
arrows are characters in Σ such that:
 Finite State Diagram (II)

● ((qa,a),qb) is a transition in δ: qa a qb

● The initial state is marked with:

● The final state(s) are marked with:

Formal Description of DFA - Example
FORMAL DESCRIPTION STATE TRANSITION DIAGRAM
● M = (Q, Σ, δ, q0, F), where 1
○ Q = {q1, q2, q3}
0
○ Σ = {0, 1} 1 0
○ δ(q1,0)=q1, δ(q1,1) = q2, δ q1 q2 q3
(q2,0) = q3, δ(q2,1) = q2, δ
0, 1
(q3,0) = q2, δ(q3,1) = q2 0 1
○ q1 is the start state q1 q1 q2 STATE
○ F = {q2} TRANSITION
q2 q3 q2 TABLE

q3 q2 q2
 Finite State Diagram(III)

transitions states
0 1
1 0
q1 q2 q3
0, 1
start state accept state
14
Finite State Diagram(III) - Example 1

0 1
1 0
q1 q2 q3
0, 1
● on input “0110”, the machine goes:
q1→q2→q2→q3 = “reject”
Finite State Diagram(IV) - Example 2

0 1
1 0
q1 q2 q3
0, 1
on input “101”, the machine goes:
q1→q2→q3→q2 = “accept”
Finite State Diagram(V) - Example 3
What is the language
accepted by this
0 1 Machine?
1 0
q1 q2 q3
0, 1
010: reject
11: accept
0110100: accept
010000010010: reject
17
Finite State Diagram(V) - Example 4
• Given language L1 =
{x ∈ {a, b}∗ | x ends with aa}
• DFA to recognise L1
(accepting the strings
ending with aa)
• What is the transition from
start to accept state on
– aabbaa
– ababaa
– aaaaaa
Finite State Diagram(V) - Example 6
• Given language L2 =
{x ∈ {a, b}∗ | x ends with b and
does not contain the substring
aa}
• What is the transition from
start to accept state on
– abab
– abbbbab
 Finite State Machine Language
Acceptance
• If A is the set of all strings that finite automaton machine
M accepts, we say that A is the language of machine M
and write L(M) = A.
• We can also say that M recognizes A or that M accepts A
• A machine may accept several strings, but it always
recognizes only one language.
• If the machine accepts no strings, it still recognizes one
language namely, the empty language ∅
 Class Exercise
• SU cafeteria has installed an ice cream vending
machine to automatically dispense ice cream to
students and staff. The cost of a can of ice cream is
Kshs 60 and the machine only accepts coins in the
denomination of 20 & 40 only and the machine does
not give change.
 Exercise (II)
a) Formally define this machine as a finite automaton.
i.e. in terms of ( Q, Σ, δ, q0, F )
b) Draw the state transition diagram for the machine
defined in (a) above
c) Draw the state transition table for the machine
defined in (a) and (b) above
Designing Finite Automata
 Designing Finite Automata
• Given Σ ={0,1}, L = {w | w has odd number of 1’s},
design a FA to recognize L.
– What is the necessary information to remember?
Is the number of 1’s seen so far even or odd?
– Two possibilities
 Designing Finite Automata (III)

• Σ ={0,1}, L = {w | w has odd number

of 1‘s}, design a FA to recognize L
• What is the necessary information qeve
qodd
to remember? n

• Is the number of 1’s seen so far

even or odd?
• Two possibilities
• Assign a state to each possibility
 Designing Finite Automata (IV)
● Σ ={0,1}, L = {w | w has odd
number of 1‘s}, design a FA to
recognize L. 0 1
0
● What is the necessary
information to remember?
● Is the number of 1s seen so far qeven qodd
even or odd? Two possibilities.
● Assign a state to each possibility.
● Assign the transitions from one
1
possibility to another upon
reading a symbol
 Designing Finite Automata (V)
● Σ ={0,1}, L = {w | w has odd
number of 1‘s}, design a FA to
recognize L. 0 1
0
● What is the necessary
information to remember?
● Is the number of 1s seen so far
qeven qodd
even or odd? Two possibilities.
● Assign a state to each
possibility.
● Assign the transitions from one 1
possibility to another upon
reading a symbol
● Set the start and accept states
 Designing DFA Example
• Σ ={0,1}, L = {w | w contains 001 as a substring},
design a DFA to recognize L
• Four possibilities:
1. haven’t seen any symbols of 001 - q
2. have just seen a 0 - q0
3. have just seen a 00 - q00
4. have seen the entire pattern 001 - q001
Designing DFA Example (II)

0
1 0 0, 1
0
1
q q0 q q
00 001
1
 Designing DFA Example (III)
• Σ ={0,1}, L = {w | w has even number of 0’s and
even number of 1’s}, design a DFA to recognize L.
• What to remember?
• How many possibilities?
Designing DFA Example (IV)

q q
00 01
0 0
0 0 1
1
q q
10 11

1
Nondeterministic Finite Automata
(NFA)
 Introduction to NFA
• Deterministic Finite Automata (DFA): At any point
when the machine is in a state with an input symbol,
there is a unique next state to go
• Non-Deterministic (NFA): There can be more than
one next state for each state-input pair

33
 Introduction to NFA (II)
• In NFA, for each state there can be zero, one,
two, or more transitions corresponding to a
particular symbol
• If NFA gets to state with more than one possible
transition corresponding to the input symbol, we
say it branches
• If NFA gets to a state where there is no Valid
Transition, then that branch dies
• Example : NFA accepting all strings ending in 01 34
NFA Operation - Example 1
0, 1

0 1
q0 q1 q2

● NFA Machine, M1

35
 NFA Operation - Example 1(II)
0,1
0 1
q0 q1 q2

q0 q0 q0 q0 q0 q0

q1 q1 q1
(die) q2 q2 ACCEPT
(die)
Input: 0 0 1 0 1
How does this NFA compute? When do NFA accept?
36
 NFA Operation - Example 2

● L = { w|w contains 00
or 11 substring}

● Some sets of strings

accepted by this NFA?

37
 NFA Operation (II)
• An NFA accepts the input string if there exists some
choice of transitions that leads to ending in an
accept state.
• Thus, one accepting branch is enough for the overall
NFA to accept, but every branch must reject for the
overall NFA to reject

38
 DFA vs NFA
• The difference between DFA and NFA are as follows:
– Every state of a DFA always has exactly one
exiting transition arrow for each symbol in the
alphabet - NFA shown (pg 35), state q0 has one
exiting arrow for 1, but it has two for 0
– In a DFA, labels on the transition arrows are
symbols from the alphabet on the other hand,
NFA can have a transition on ε

39
 NFA Formal Definition
• Formally, an NFA is a 5-tuple N = (Q, Σ, δ, q0, F),
where all is as DFA, but:
δ: Q x Σ → 𝜬(Q)
• 𝜬(Q) is a transition function from Q x Σ to the power
set of Q

40
 NFA Formal Definition (II)
• NFA is defined by a 5 -tuple:
(Q, Σ, δ,q0, F)
1. Q: finite set of states
2. Σ: finite alphabet
3. δ: transition function, δ : Q x (Σ⋃ε) → 𝜬(Q)
4. q0∈Q: start state
5. F∈Q: set of accept states

41
 NFA Description Example

• M = (Q, Σ, 𝛿, q0, F)
where 0 1
q0 {q0,q1} {q0}
• – Q = { q 0 , q1 , q2 }
q1 ∅ {q2}
– Σ = {0, 1 }
– 𝛿(q0, 1 ) = {q0} ,𝛿(q0, 0) = {q0,q1} q2
∅ ∅
𝛿(q1,1) = {q2} 0, 1

– q0 is the start state

0 1
q0 q1 q2
– F = {q2}
42
 NFA Description- Example 2
• Which sets of strings
are accepted by the
following NFA given Σ =
{a,b}
• Write down the formal
description

43
 NFA Description - Example 3
• NFA which accepts ε, a,
baba, and baa, but not b,
bb, and babba
• Write down the formal
description

44
NFA Description Definition - Example 4
• Other examples of
strings accepted by
this NFA?
• Write down the
formal description

45
 NFA with ε Transitions
• Allows ε to be a label on arcs.
• Transition function 𝛿 of an ε-NFA is from
Q x Σ∪{ε} → P(Q)
• Nothing else changes: acceptance of string w is
still the existence of a path from the start state to
an accept state with label w.
• But ε can appear on arcs, and means the empty
string
46
NFA AND DFA EQUIVALENCE
Assignment 01*

47
 Exercise
• The channel selection switch of a television
– The channel selection switch of a television
set can be turned both clockwise and
counterclockwise to select among three possible
channels
– In the first case, channels A, B, and C are selected
in the order
– Model this using a Finite Automaton
48
 Applications of Finite Automata
• Finite automata are good models for computers
with an extremely limited amount of memory.
• What can a computer do with such a small
memory?
• Many useful things!
Applications of Finite Automata (II)
• In fact, we interact with such computers all the
time, as they lie at the heart of various
electromechanical devices.
– The controller for an automatic door is one
example of such a device
– Often found at supermarket entrances and
exits, automatic doors swing open when
sensing that a person is approaching
Applications of Finite Automata (III)
• In fact, we interact with such computers all the
time, as they lie at the heart of various
electromechanical devices.
– An automatic door has a pad in front to detect
the presence of a person about to walk
through the doorway
Applications of Finite Automata (IV)
• In fact, we interact with such computers all the
time, as they lie at the heart of various
electromechanical devices.
– Another pad is located to the rear of the
doorway so that the controller can hold the
door open long enough for the person to pass
all the way through and also so that the door
does not strike someone standing behind it as
it opens
Applications of Finite Automata (V)
• Other applications of Finite Automata include:
○ Software for designing and checking the
behaviour of digital circuits
○ The “lexical analyzer” of a typical compiler, i.e.
the compiler component that breaks the input
text into logical units, such as identifiers,
keywords, and punctuation
Applications of Finite Automata (VI)
• Other applications of Finite Automata include:
○ Software for scanning large bodies of text, such
as collections of web pages, to find occurrences
of words, phrases, or other patterns.
○ Software for verifying systems of all types that
have a finite number of distinct states, such as
communication protocols or protocols for secure
exchange of information
LIMITATIONS OF FINITE STATE
MACHINES (FSM)
• The fundamental limitation of FSMs is that they
have no capacity for remembering arbitrarily
large amounts of information.
• Any computation that requires the memory of
arbitrarily long sequences cannot be carried out
on a FSM

55
Questions