COS210 - Theoretical Computer Science
Finite Automata and Regular Languages (Part 1)
1
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
Consider a simple co↵ee vending machine:
The vending machine takes R1, R2 and R5 coins as an input
Co↵ee will be released after at least R7 have been inserted
The machine does not give change
Modelling questions:
What are the possible “states” of the machine?
How does the insertion of coins change the “state” of the machine?
2
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
0 1 2 3 4 5 6 7
3
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
1
0 1 2 3 4 5 6 7
4
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2 2
1 1
0 1 2 3 4 5 6 7
5 5
5
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2 2 2
1 1 1
0 1 2 3 4 5 6 7
5 5 5
6
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2 2 2 2
1 1 1 1
0 1 2 3 4 5 6 7
5
5 5 5
7
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2 2 2 2 2
1 1 1 1 1
0 1 2 3 4 5 6 7
5
5
5 5 5
8
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2 2 2 2 2 2,5
1 1 1 1 1 1
0 1 2 3 4 5 6 7
5
5
5 5 5
9
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2 2 2 2 2 2,5
1 1 1 1 1 1 1,2,5
0 1 2 3 4 5 6 7
5
5
5 5 5
10
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2,5 1,2,5
2 2 2 2 2
1 1 1 1 1 1 1,2,5
0 1 2 3 4 5 6 7
5
5
5 5 5
11
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2,5 1,2,5
2 2 2 2 2
1 1 1 1 1 1 1,2,5
0 1 2 3 4 5 6 7
5
5
5 5 5
Example of accepted input: 1, 5, 2
Example of rejected input: 2, 1, 2, 1
12
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Abstract Example
Consider the following abstract machine:
The machine takes finite sequences of bits as an input, e.g.
00101111010100011101011001000
which we call an input string
The machine only accepts input strings that end with 00
Such a machine can be modelled as a deterministic finite automaton
(DFA)
13
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Deterministic Finite Automaton for Abstract Example
1 0
0
q0 q1 0 q2
1
Figure: DFA that accepts only strings ending with 00
start state: q0 , accepting state: q2
transitions show how an input changes the state of the DFA
accepted inputs: 00, 0000, 110100, . . .
non-accepted inputs: 111, 1001, 00110, . . .
14
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Deterministic Finite Automaton for Abstract Example
1 0
0
q0 q1 0 q2
1
Figure: DFA that accepts only strings ending with 00
start state: q0 , accepting state: q2
transitions show how an input changes the state of the DFA
accepted inputs: 00, 0000, 110100, . . .
non-accepted inputs: 111, 1001, 00110, . . .
15
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
DFA: Formal Definition
Definition
A deterministic finite automaton is a 5-tuple M = (Q, ⌃, , q, F ), where
Q is a finite set, whose elements are called states,
⌃ is a finite set, called the alphabet;
I the elements of ⌃ are called symbols,
: Q ⇥ ⌃ ! Q is a function, called the transition function,
q is an element of Q; it is called the start state,
F is a subset of Q; the elements of F are called accept states.
16
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
DFA: Formal Definition
Definition
A deterministic finite automaton is a 5-tuple M = (Q, ⌃, , q, F ), where
Q is a finite set, whose elements are called states,
⌃ is a finite set, called the alphabet;
I the elements of ⌃ are called symbols,
: Q ⇥ ⌃ ! Q is a function, called the transition function,
q is an element of Q; it is called the start state,
F is a subset of Q; the elements of F are called accept states.
1 0
0
q0 q1 0 q2
M:
1
1 17
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
DFA Graphically and Formally
1 0
0
q0 q1 0 q2
M:
1
The transition function :
Q = {q0 , q1 , q2 }
⌃ = {0, 1} 0 1
q = q0 q0 q1 q0
q1 q2 q0
F = {q2 }
q2 q2 q0
18
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Motivating Example: Vending Machine
2,5 1,2,5
2 2 2 2 2
1 1 1 1 1 1 1,2,5
0 1 2 3 4 5 6 7
5
5
5 5 5
19
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Deterministic Finite Automaton for the Vending Machine
Consider the vending machine example:
Q = {q0 , q1 , q2 , q3 , q4 , q5 , q6 , q7 }
⌃ = {R1, R2, R5}
q0 is the start state, q = {q0 }
F = {q7 }
is given by (complete for homework):
R1 R2 R5
q0 q1 q2 q5
q1 q2 q3 q6
q2 q3 q4 q7
... ... ... ...
20
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Abstract Example 2
Consider the following extension of our earlier abstract example:
The machine takes finite sequences of bits as an input
The machine only accepts inputs that either end with 00 or with 11
Model this machine as a deterministic finite automaton
This can be done by extending and modifying the DFA for Abstract
Example 1
21
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
DFA for Abstract Example 2
1 0
0
q0 q1 0 q2
1
q0 : last processed bit was not 0
q1 : last processed bit was 0, but second last bit was not 0
q2 : last two processed bits were 0
22
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
DFA for Abstract Example 2
1 0
0
q0 q1 0 q2
1
1
1
q3 1 q4
q0 : last processed bit was not 0
q1 : last processed bit was 0, but second last bit was not 0
q2 : last two processed bits were 0
q3 : last processed bit was 1, but second last bit was not 1
q4 : last two processed bits were 1 23
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
DFA for Abstract Example 2
0
0
q0 q1 0 q2
1 1 1 1
q3 1 q4
q0 : no bits processed yet
q1 : last processed bit was 0, but second last bit was not 0
q2 : last two processed bits were 0
q3 : last processed bit was 1, but second last bit was not 1
q4 : last two processed bits were 1 24
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
DFA for Abstract Example 2
0
0
q0 q1 0 q2
1 0 1 0 1 1
q3 1 q4
q0 : no bits processed yet
q1 : last processed bit was 0, but second last bit was not 0
q2 : last two processed bits were 0
q3 : last processed bit was 1, but second last bit was not 1
q4 : last two processed bits were 1 25
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Language of an Automaton
A language is a set of strings over an alphabet.
The language L(M) of an automaton M is the set of all input strings
accepted by M.
General form:
L(M) = {w : string w accepted by M}
For our abstract Example 2 we get:
L(M) = {w : string w ends with a 00 or 11}
Subsequently, we will formally define what acceptance is.
26
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Runs and Acceptance
Definition
Let M = (Q, ⌃, , q, F ) be an automaton and let w = w1 . . . wn be a string
over ⌃. A run of M over w is a sequence of states q0 , . . . , qn such that
q0 = q,
(qi , wi+1 ) = qi+1 , for all i < n.
(the transitions along q0 , . . . , qn are labelled with w1 . . . wn )
A string w is accepted by M if the following holds for the run over w :
qn 2 F .
Otherwise a string is rejected by M.
Note that a string w may be the empty string, denoted by w = ✏. In this
case the run over w consists of the start state only.
27
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Runs and Acceptance
Definition
Let M = (Q, ⌃, , q, F ) be an automaton and let w = w1 . . . wn be a string
over ⌃. A run of M over w is a sequence of states q0 , . . . , qn such that
q0 = q,
(qi , wi+1 ) = qi+1 , for all i < n.
(the transitions along q0 , . . . , qn are labelled with w1 . . . wn )
Example:A string w is accepted by M if the following holds for the run over w :
For input w = 101100
qn 2run
The corresponding F .is q , q , q , q , q , q , q
0 0 1 0 0 1 2
Otherwise a string is rejected by M.
Note that a string w may be the empty string, denoted by w = ✏. In this
case the run over w consists of the start state only.
28
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Runs and Acceptance
Definition
Let M = (Q, ⌃, , q, F ) be an automaton and let w = w1 . . . wn be a string
over ⌃. A run of M over w is a sequence of states q0 , . . . , qn such that
q0 = q,
(qi , wi+1 ) = qi+1 , for all i < n.
(the transitions along q0 , . . . , qn are labelled with w1 . . . wn )
A string w is accepted by M if the following holds for the run over w :
qn 2 F .
Otherwise a string is rejected by M.
Note that a string w may be the empty string, denoted by w = ✏. In this
case the run over w consists of the start state only.
29
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Runs and Acceptance
Definition
Let M = (Q, ⌃, , q, F ) be an automaton and let w = w1 . . . wn be a string
over ⌃. A run of M over w is a sequence of states q0 , . . . , qn such that
q0 = q,
(qi , wi+1 ) = qi+1 , for all i < n.
(the transitions along q0 , . . . , qn are labelled with w1 . . . wn )
Example:A string w is accepted by M if the following holds for the run over w :
For input w = 101100
qn 2run
The corresponding F .is q , q , q , q , q , q , q
0 0 1 0 0 1 2
Otherwise a string is rejected by M.
Note that a string w may be the empty string, denoted by w = ✏. In this
case the run over w consists of the start state only.
30
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Runs and Acceptance
Definition
Let M = (Q, ⌃, , q, F ) be an automaton and let w = w1 . . . wn be a string
over ⌃. A run of M over w is a sequence of states q0 , . . . , qn such that
q0 = q,
(qi , wi+1 ) = qi+1 , for all i < n.
(the transitions along q0 , . . . , qn are labelled with w1 . . . wn )
A string w is accepted by M if the following holds for the run over w :
qn 2 F .
Otherwise a string is rejected by M.
Note that a string w may be the empty string, denoted by w = ✏. In this
case the run over w consists of the start state only.
31
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Regular Languages
Definition
Let M = (Q, ⌃, , q, F ) be an automaton. The language L(M) of M is
the set of all strings that are accepted by M:
L(M) = {w : w is a string over ⌃ and M accepts w }
Definition
A language L is called regular, if there exists a finite automaton M such
that
L = L(M).
How to prove that a language L is regular?
Construct finite automaton M with L(M) = L (proof by construction).
32
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Example
Is the following language regular? Is there an M with L(M) = L?
L = {w over {0, 1} : the third last symbol of w is 1}
Idea for the construction of M with L(M) = L:
we can observe that each string accepted by M must be of the form
w = . . . 1 y z where y , z 2 {0, 1}
we use the binary numbered states q000 , . . . , q111 for M
the digits shall represent the last three symbols along a run of M:
qxyz
the last symbol was z, the second last was y, the third last was x
we start in q000 (no 1’s encountered so far)
the accepting states are q100 , q101 , q110 , q111
33
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Example
Is the following language regular? Is there an M with L(M) = L?
L = {w over {0, 1} : the third last symbol of w is 1}
Idea for the construction of M with L(M) = L:
we can observe that each string accepted by M must be of the form
w = . . . 1 y z where y , z 2 {0, 1}
we use the binary numbered states q000 , . . . , q111 for M
the digits shall represent the last three symbols along a run of M:
qxyz
the last symbol was z, the second last was y, the third last was x
we start in q000 (no 1’s encountered so far)
the accepting states are q100 , q101 , q110 , q111
34
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Example
Is the following language regular? Is there an M with L(M) = L?
L = {w over {0, 1} : the third last symbol of w is 1}
Idea for the construction of M with L(M) = L:
we can observe that each string accepted by M must be of the form
w = . . . 1 y z where y , z 2 {0, 1}
we use the binary numbered states q000 , . . . , q111 for M
the digits shall represent the last three symbols along a run of M:
qxyz
the last symbol was z, the second last was y, the third last was x
we start in q000 (no 1’s encountered so far)
the accepting states are q100 , q101 , q110 , q111
35
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Example
Is the following language regular? Is there an M with L(M) = L?
L = {w over {0, 1} : the third last symbol of w is 1}
Idea for the construction of M with L(M) = L:
we can observe that each string accepted by M must be of the form
w = . . . 1 y z where y , z 2 {0, 1}
we use the binary numbered states q000 , . . . , q111 for M
the digits shall represent the last three symbols along a run of M:
qxyz
the last symbol was z, the second last was y, the third last was x
we start in q000 (no 1’s encountered so far)
the accepting states are q100 , q101 , q110 , q111
36
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
Example
000 100 010 110
001 101 011 111
37
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Example
000 100 010 110
001 101 011 111
38
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Example
000 100 010 110
0
1
001 101 011 111
39
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Example
0
000 100 010 110
0
1
1
001 101 011 111
40
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Example
0
000 100 010 110
0
1
1 0
001 101 011 111
1
41
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Example
0 0
000 100 010 110
1 0
1
1 0
001 101 011 111
1
42
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Example
0 0
000 100 010 110
1 0 0
1
1 0
1
001 101 011 111
1
43
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Example
0 0
0 0
000 100 010 110
1 0 0
1
1 1 0
1
001 101 011 111
1
44
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Example
0 0
0 0
000 100 010 110
1 0 0
1 0
1 1 0
1
001 101 011 111
1
1 1
45
Finite Automata and Regular Languages ©Cleghorn, Marshall, Timm
Regular
ExampleLanguages
Is the following language regular? Is there an M with L(M) = L?
Definition
Let M = (Q, L= ⌃,{w, q,over
F ) be
{0,an
1} automaton. language
Thesymbol
: the third last of w L(M)
is 1} of M is
the set of all strings that are accepted by M:
Idea for the construction of M with L(M) = L:
we canL(M) = {w
observe : weach
that is a string
string accepted
over ⌃ andby M must bewof} the form
M accepts
w = . . . 1 y z where y , z 2 {0, 1}
Definition
we use the binary numbered states q000 , . . . , q111 for M
A language L isshall
the digits called regular,the
represent if there existssymbols
last three a finitealong
automaton M M:
a run of such
that
L = L(M).
qxyz
the last symbol was z, the second last was y, the third last was x
How we start inthat
to prove q000a (no 1’s encountered
language L is regular? so far)
the accepting
Construct states areMq100
finite automaton , q101
with L(M), q110
=, Lq111
(proof by construction).
46
Finite Automata and Regular Languages c Cleghorn, Marshall, Timm
