Bài giảng Mô hình hóa toán học - Chapter 3: Automata
Automata
TVHoai, HTNguyen,
NAKhuong, LHTrang
Chapter 3
Automata
Mathematical Modeling
Contents
Motivation
Alphabets, words and
languages
Regular expression or
rationnal expression
Non-deterministic
finite automata
(Materials drawn from this chapter in:
Jones & Bartlett Learning, 2011.
Deterministic finite
automata
- John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullamn. Introduction to
Automata Theory, Languages, and Computation (3rd Ed.), Prentice Hall,
2006.
Recognized languages
Determinisation
Minimization
Információs K¨ozpont, 2011. )
TVHoai, HTNguyen, NAKhuong, LHTrang
Faculty of Computer Science and Engineering
University of Technology, VNU-HCM
3.1
Automata
Contents
TVHoai, HTNguyen,
NAKhuong, LHTrang
1 Motivation
2 Alphabets, words and languages
3 Regular expression or rationnal expression
4 Non-deterministic finite automata
5 Deterministic finite automata
6 Recognized languages
Contents
Motivation
Alphabets, words and
languages
Regular expression or
rationnal expression
Non-deterministic
finite automata
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
7 Determinisation
8 Minimization
3.2
Automata
Course outcomes
TVHoai, HTNguyen,
NAKhuong, LHTrang
Course learning outcomes
L.O.1
L.O.2
Understanding of predicate logic
L.O.1.1 – Give an example of predicate logic
L.O.1.2 – Explain logic expression for some real problems
L.O.1.3 – Describe logic expression for some real problems
Contents
Motivation
Alphabets, words and
languages
Understanding of deterministic modeling using some discrete
structures
L.O.2.1 – Explain a linear programming (mathematical statement)
L.O.2.2 – State some well-known discrete structures
L.O.2.3 – Give a counter-example for a given model
L.O.2.4 – Construct discrete model for a simple problem
Regular expression or
rationnal expression
Non-deterministic
finite automata
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
L.O.3
Be able to compute solutions, parameters of models based on data
L.O.3.1 – Compute/Determine optimal/feasible solutions of integer
linear programming models, possibly utilizing adequate libraries
L.O.3.2 – Compute/ optimize solution models based on automata,
. . . , possibly utilizing adequate libraries
3.3
Automata
Introduction
TVHoai, HTNguyen,
NAKhuong, LHTrang
Standard states of a process in operating system
•
•
O with label: states
→: transitions
Contents
Resource
Motivation
Alphabets, words and
languages
Waiting
Blocked
Regular expression or
rationnal expression
Non-deterministic
finite automata
Resource
Deterministic finite
automata
CPU
Recognized languages
Determinisation
Minimization
CPU
Resource
Running
3.4
Automata
Why study automata theory?
TVHoai, HTNguyen,
NAKhuong, LHTrang
A useful model
for many important kinds of software and hardware
Contents
1 designing and checking the behaviour of digital circuits
Motivation
Alphabets, words and
languages
2 lexical analyser of a typical compiler: a compiler component
that breaks the input text into logical units
Regular expression or
rationnal expression
3 scanning large bodies of text, such as collections of Web
pages, to find occurrences of words, phrases or other patterns
Non-deterministic
finite automata
Deterministic finite
automata
4 verifying pratical systems of all types that have a finite
number of distinct states, such as communications protocols
and other protocols for securely information exchange, etc.
Recognized languages
Determinisation
Minimization
3.5
Automata
Alphabets, symbols
Definition
TVHoai, HTNguyen,
NAKhuong, LHTrang
Alphabet Σ (bảng chữ cái) is a finite and non-empty set of
symbols (or characters).
For example:
Contents
Motivation
•
•
•
•
Σ = {a, b}
Alphabets, words and
languages
The binary alphabet: Σ = {0, 1}
The set of all lower-case letters: Σ = {a, b, . . . , z}
The set of all ASCII characters.
Regular expression or
rationnal expression
Non-deterministic
finite automata
Deterministic finite
automata
Remark
Recognized languages
Determinisation
Minimization
Σ is almost always all available characters (lowercase letters,
capital letters, numbers, symbols and special characters such as
space or newline).
But nothing prevents to imagine other sets.
3.6
Automata
Strings (words)
TVHoai, HTNguyen,
NAKhuong, LHTrang
Definition
•
A string/word u (chuỗi/từ) over Σ is a finite sequence (possibly
empty) of symbols (or characters) in Σ.
Contents
Motivation
•
•
A empty string is denoted by ε.
Alphabets, words and
languages
The length of the string u, denoted by |u|, is the number of
characters.
Regular expression or
rationnal expression
All the strings over Σ is denoted by Σ∗.
A language L over Σ is a sub-set of Σ∗.
•
•
Non-deterministic
finite automata
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
Remark
The purpose aims to analyze a string of Σ∗ in order to know
whether it belongs or not to L.
3.7
Automata
Example
TVHoai, HTNguyen,
NAKhuong, LHTrang
Let Σ = {0, 1}
•
ε is a string with length of 0.
Contents
•
•
•
•
•
•
•
0 and 1 are the strings with length of 1.
Motivation
00, 01, 10 and 11 are the strings with length of 2.
∅ is a language over Σ . It’s called the empty language.
Σ∗ is a language over Σ . It’s called the universal language.
{ε} is a language over Σ .
{0, 00, 001} is also a language over Σ .
The set of strings which contain an odd number of 0 is a language
Alphabets, words and
languages
Regular expression or
rationnal expression
Non-deterministic
finite automata
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
over Σ.
•
The set of strings that contain as many of 1 as 0 is a language
over Σ.
3.8
Automata
String concatenation
TVHoai, HTNguyen,
NAKhuong, LHTrang
Contents
Intuitively, the concatenation of two strings 01 and 10 is 0110.
Concatenating the empty string ε and the string 110 is the string
110.
Motivation
Alphabets, words and
languages
Regular expression or
rationnal expression
Definition
Non-deterministic
finite automata
String concatenation is an application of Σ∗ × Σ∗ to Σ∗.
Deterministic finite
automata
Concatenation of two strings u and v in Σ is the string u.v.
Recognized languages
Determinisation
Minimization
3.9
Automata
Languages
TVHoai, HTNguyen,
NAKhuong, LHTrang
Specifying languages
A language can be specified in several ways:
a
enumeration of its words, for example:
•
•
•
L1 = {ε, 0, 1},
Contents
L2 = {a, aa, aaa, ab, ba},
Motivation
L3 = {ε, ab, aabb, aaabbb, aaaabbbb, . . .},
Alphabets, words and
languages
b a property, such that all words of the language have this property
but other words have not, for example:
Regular expression or
rationnal expression
L4 = {anbn|n = 0, 1, 2, . . .},
•
•
•
Non-deterministic
finite automata
L5 = {uu−1|u ∈ Σ∗} with Σ = {a, b},
L6 = {u ∈ {a, b}∗|na(u) = nb(u)} where na(u) denotes the
number of letter ’a’ in word u.
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
c
its grammar, for example:
•
Let G = (N, T, P, S) where
N = {S}, T = {a, b}, P = {S → aSb, S → ab}
i.e. L(G) = {anbn|n ≥ 1} since
S ⇒ aSb ⇒ a2Sb2 ⇒ . . . ⇒ anSbn
3.10
Automata
Operations on languages
TVHoai, HTNguyen,
NAKhuong, LHTrang
L, L1, L2 are languages over Σ
• union
L1 ∪ L2 = {u ∈ Σ∗ | u ∈ L1 or u ∈ L2},
• intersection
L1 ∩ L2 = {u ∈ Σ∗ | u ∈ L1 and u ∈ L2},
Contents
• difference
L1 \ L2 = {u ∈ Σ∗ | u ∈ L1 and u ∈ L2},
Motivation
Alphabets, words and
languages
• complement
L = Σ∗ \ L,
Regular expression or
rationnal expression
• multiplication
Non-deterministic
finite automata
L1L2 = {uv | u ∈ L1, v ∈ L2},
• power
Deterministic finite
automata
L0 = {ε},
Ln = Ln−1L , if n ≥ 1,
Recognized languages
Determinisation
Minimization
• iteration or star operation
∞
[
L∗ =
Li = L0 ∪ L ∪ L2 ∪ · · · ∪ Li ∪ · · · ,
i=0
We will use also ∞the notation L+
[
L+
=
Li = L ∪ L2 ∪ · · · ∪ Li ∪ · · · .
i=1
The union, product and iteration are called regular operations.
3.11
Automata
Example
TVHoai, HTNguyen,
NAKhuong, LHTrang
Let Σ = {a, b, c}, L1 = {ab, aa, b}, L2 = {b, ca, bac}
a
L1 ∪ L2 =? L1 ∪ L2 = {ab, aa, b, ca, bac},
b L1 ∩ L2 =? L1 ∩ L2 = {b},
c
L1 \ L2 =? L1 \ L2 = {ab, aa},
Contents
d L1L2 =?
Motivation
L1L2 = {abb, aab, bb, abca, aaca, bca, abbac, aabac, bbac},
L2L1 =?
L2L1 = {bab, baa, bb, caab, caaa, cab, bacab, bacaa, bacb}.
Alphabets, words and
languages
e
Regular expression or
rationnal expression
Non-deterministic
finite automata
Let Σ = {a, b, c} and L = {ab, aa, b, ca, bac}
Deterministic finite
automata
L2 =? L2 = u.v, with u, v ∈ L including the following strings:
Recognized languages
Determinisation
Minimization
•
abab, abaa, abb, abca, abbac,
•
aaab, aaaa, aab, aaca, aabac,
•
bab, baa, bb, bca, bbac,
•
caab, caaa, cab, caca, cabac,
•
bacab, bacaa, bacb, bacca, bacbac.
3.12
Automata
Regular expressions
TVHoai, HTNguyen,
NAKhuong, LHTrang
Regular expressions (biểu thức chính quy)
Permit to specify a language with strings consist of letters and ε,
parentheses (), operating symbols +, ., ∗. This string can be
empty, denoted ∅.
Contents
Motivation
Regular operations on the languages
Alphabets, words and
languages
•
•
•
union ∪ or +
product of concatenation
transitive closure ∗
Regular expression or
rationnal expression
Non-deterministic
finite automata
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
Example on the aphabet set Σ = {a, b}
(a + b)∗ represent all the strings
a∗(ba∗)∗ represent the same language
•
•
(a + b)∗aab represent all strings ending with aab.
•
3.15
Automata
Regular expressions
TVHoai, HTNguyen,
NAKhuong, LHTrang
•
•
•
•
∅ is a regular expression representing the empty language.
ε is a regular expression representing language {ε}.
If a ∈ Σ, then a is a regular expression representing language {a}.
If x, y are regular expressions representing languages X and Y
Contents
respectively, then (x + y), (xy), x∗ are regular expression
Motivation
S
representing languages X Y , XY and X∗ respectively.
Alphabets, words and
languages
x + y
(x + y) + z
(xy)z
≡
≡
≡
≡
≡
≡
≡
≡
≡
y + x
Regular expression or
rationnal expression
x + (y + z)
Non-deterministic
finite automata
x(yz)
Deterministic finite
automata
(x + y)z
xz + yz
Recognized languages
Determinisation
Minimization
x(y + z)
xy + xz
(x + y)∗ ≡ (x∗ + y)∗
(x + y∗)∗ ≡ (x∗ + y∗)∗
(x + y)∗
(x∗y∗)∗
x∗
(x∗)∗
x∗x
xx∗ + ε
xx∗
x∗
3.16
Automata
Regular expressions
TVHoai, HTNguyen,
NAKhuong, LHTrang
Contents
Motivation
Kleene’s theorem
Alphabets, words and
languages
Language L ⊆ Σ∗ is regular if and only if there exists a regular
Regular expression or
rationnal expression
expression over Σ representing language L.
Non-deterministic
finite automata
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
3.17
Automata
Finite automata
TVHoai, HTNguyen,
NAKhuong, LHTrang
Finite automata (Automat hữu hạn)
•
•
The aim is representation of a process system.
It consists of states (including an initial state and one or
several (or one) final/accepting states) and transitions
(events).
Contents
Motivation
Alphabets, words and
languages
•
The number of states must be finite.
Regular expression or
rationnal expression
Non-deterministic
finite automata
b
a, b
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
q0
q1
Regular expression
b∗(a + b)
3.22
Automata
Exercise
TVHoai, HTNguyen,
NAKhuong, LHTrang
Give regular expression for the following finite automata.
a, b
b
b
Contents
a
Motivation
a
b
q0
q1
b
q0
a
q1
Alphabets, words and
languages
Regular expression or
rationnal expression
Non-deterministic
finite automata
a
Deterministic finite
automata
q0
q1
q0
q1
Recognized languages
Determinisation
Minimization
b
a, b
a
a
b
q2
q2
3.25
Automata
Nondeterministic finite automata
Definition
TVHoai, HTNguyen,
NAKhuong, LHTrang
A nondeterministic finite automata (NFA, Automat hữu hạn phi
đơn định) is mathematically represented by a 5-tuples
(Q, Σ, q0, δ, F) where
Contents
Motivation
•
Q a finite set of states.
Alphabets, words and
languages
•
Σ is the alphabet of the automata.
Regular expression or
rationnal expression
•
•
•
q0 ∈ Q is the initial state.
δ : Q × Σ → Q is a transition function.
F ⊆ Q is the set of final/accepting states.
Non-deterministic
finite automata
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
Remark
According to an event, a state may go to one or more states.
3.27
Automata
NFA with empty symbol ε
TVHoai, HTNguyen,
NAKhuong, LHTrang
Other definition of NFA
Contents
Finite automaton with transitions defined by character x (in Σ) or
empty character ε.
Motivation
Alphabets, words and
languages
Regular expression or
rationnal expression
a, b
b
a
Non-deterministic
finite automata
ε
b
Deterministic finite
automata
q0
q1
q2
Recognized languages
Determinisation
Minimization
3.28
Automata
Deterministic finite automata
Definition
TVHoai, HTNguyen,
NAKhuong, LHTrang
A deterministic finite automata (DFA, Automat hữu hạn đơn
định) is given by a 5-tuplet (Q, Σ, q0, δ, F) with
Contents
Motivation
•
Q a finite set of states.
Alphabets, words and
languages
•
Σ is the input alphabet of the automata.
Regular expression or
rationnal expression
•
•
•
q0 ∈ Q is the initial state.
δ : Q × Σ → Q is a transition function.
F ⊆ Q is the set of final/accepting states.
Non-deterministic
finite automata
Deterministic finite
automata
Recognized languages
Determinisation
Minimization
Condition
Transition function δ is an application.
3.34
Tải về để xem bản đầy đủ
33 trang
22720
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mô hình hóa toán học - Chapter 3: Automata", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mo_hinh_hoa_toan_hoc_chapter_3_automata.pdf
