CS计算机代考程序代写 Haskell COMP30026 Models of Computation – Finite-State Automata

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