COMP30026 Models of Computation – Finite-State Automata
COMP30026 Models of Computation
Finite-State Automata
Bach Le / Anna Kalenkova
Lecture Week 7 Part 1
Semester 2, 2021
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 1 / 15
This Lecture is Being Recorded
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 2 / 15
Machines vs Languages
Regular
Context-free
Context
sensitive
Decidable
Turing recognisable
Finite
automata
Pushdown
automata
Linear-
bounded
automata
Halting
Turing
machines
Turing machines
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 3 / 15
An Example Automaton
Imagine a vending machine selling tea or coffee for $2. It accepts 1-
and 2-dollar coins.
If we let ‘1’ (‘2’) stand for the event that a 1-dollar (2-dollar) coin
enters the coin slot, and C (T ) stand for the push of button ‘C’ (‘T’)
and subsequent delivery of a cup of coffee (tea), then the following
automaton describes the acceptable event sequences:
1 1, 2
2
C ,T
1, 2
That’s “acceptable” from a greedy vending machine owner’s point of
view, for example, 2T11C22C is accepted, but 111C1T is not.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 4 / 15
Example 2
Here is an automaton for recognising Haskell variable identifier:
1 2
3
s
s, l , d , , ′
s, l , d , , ′
s is an abbreviation for a, . . . , z (the small or lower-case letters)
l is an abbreviation for A, . . . ,Z (the large or upper-case letters)
d is an abbreviation for 0, . . . , 9 (the digits)
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 5 / 15
Formal Definition
A finite automaton is a 5-tuple (Q,Σ, δ, q0, F ), where
Q is a finite set of states,
Σ is a finite alphabet,
δ : Q × Σ → Q is the transition function,
q0 ∈ Q is the start state, and
F ⊆ Q are the accept states.
Here δ is a total function, that is, δ must be defined for all possible
inputs.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 6 / 15
Back to Example 2
To make it clear that the transition function is total, we should add a
new state 4 and arcs to state 4 from state 1:
1 2
34
s
s, l , d , , ′
s, l, d, , ′
l , d , ′
s, l , d , , ′
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 7 / 15
Strings and Languages
An alphabet Σ can be any non-empty finite set.
The elements of Σ are the symbols of the alphabet. Usually we
choose symbols such as a, b, c, 1, 2, 3, . . . .
A string over Σ is a finite sequence of symbols from Σ.
We write the concatenation of a string y to a string x as xy .
The empty string is denoted by ǫ.
A language (over alphabet Σ) is a (finite or infinite) set of finite
strings over Σ.
Σ∗ denotes the set of all finite strings over Σ.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 8 / 15
Examples of Languages over Alphabet Σ = {0, 1}
∅
{ǫ}
{ǫ, 0, 1}
{00, 01, 10, 11}
{ǫ, 0, 00, 000, . . .}
{ǫ, 0, 1, 00, 11, 000, 111, . . .}
{ǫ, 01, 0011, 000111, . . .}
{w | w contains odd number of 0}
{w | the length of w is a multiple of 3}
{w | w is not empty string}
{w | w does not contain 001}
Σ∗
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 9 / 15
Example 3
q1 q2 q3
1 1
0
0, 1
0
The automaton M1 (above) can be described precisely as
M1 = ({q1, q2, q3}, {0, 1}, δ, q1, {q1}) with
δ 0 1
q1 q1 q2
q2 q1 q3
q3 q1 q1
L(M1) =
{
w
∣
∣
∣
∣
w is ǫ, or ends with ‘0’, or the number of
‘1’ symbols ending w is a multiple of 3
}
is the language recognised by M1.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 10 / 15
Acceptance and Recognition, Formally
What does it mean for an automaton to accept a string?
Let M = (Q,Σ, δ, q0, F ) and let w = v1v2 · · · vn be a string from Σ
∗.
M accepts w iff there is a sequence of states r0, r1, . . . , rn, with each
ri ∈ Q, such that
1. r0 = q0
2. δ(ri , vi+1) = ri+1 for i = 0, . . . , n − 1
3. rn ∈ F
M recognises language A iff A = {w | M accepts w}.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 11 / 15
Exercise
Consider the alphabet Σ = {0, 1}. Build an automaton over Σ that
recognises a language that contains all strings of odd length and only
them.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 12 / 15
Regular Languages
A language is regular iff there is a finite automaton that recognises it.
We shall soon see that there are languages which are not regular.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 13 / 15
Regular Operations
Remember that, to us, a language is simply a set of strings.
Let A and B be languages. The regular operations are:
Union: A ∪ B
Concatenation: A ◦ B = {xy | x ∈ A, y ∈ B}
Kleene star: A∗ = {x1x2 · · · xk | k ≥ 0, each xi ∈ A}
Note that the empty string, ǫ, is always in A∗.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 14 / 15
Regular Operations: Example
Let A = {aa, abba} and B = {a, ba, bba, bbba, . . .}.
A ∪ B = {a, aa, abba, ba, bba, bbba, . . .}.
A ◦ B = {aaa, abbaa, aaba, abbaba, aabba, abbabba, . . .}.
A∗ =
{
ǫ, aa, abba, aaaa, aaabba, abbaaa, abbaabba,
aaaaaa, aaaaabba, aaabbaaa, aaabbaabba, . . .
}
.
The regular languages are closed under the regular operations.
It will be easier to show this after we have considered
non-deterministic automata.
Models of Computation (Sem 2, 2021) Finite-State Automata © University of Melbourne 15 / 15