Chapter 2: Finite Automata
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (155.63 KB, 40 trang )
Chapter 2: Finite Automata
Objectives
Mastering the following concepts:
–
Deterministic Finite Accepter (DFA)
–
Nondeterministic Finite Accepter (NFA)
–
DFA and NFA Equivalence
Deterministic Finite Accepter (DFA)
M = (Q, ∑, δ, q
0
, F)
Q: finite set of internal states
∑: finite set of symbols - input alphabet
δ: Q × ∑ → Q transition function
q
0
∈Q: initial state
F⊆Q: set of final states
Operational Mechanism
Control unit
q
0
Input file
yes/no
Question: What is the
difference between a
general automaton and
a DFA?
Transition Graph
M = (Q, ∑, δ, q
0
, F)
•
|Q| vertices (circles)
•
Edge (q
i
, q
j
) labelled a for δ(q
i
, a) = q
j
•
Initial vertice q
0
•
Final vertices (double circles) in F
Example 2.1
M = ({q
0
, q
1
, q
2
}, {0, 1}, δ, q
0
, {q
1
})
δ(q
0
, 0) = q
0
δ(q
0
, 1) = q
1
δ(q
1
, 0) = q
0
δ(q
1
, 1) = q
2
δ(q
2
, 0) = q
2
δ(q
2
, 1) = q
1
q
0
q
1
1
q
2
1
0
0
0
1
Example 2.2
1
2
3
Letter
Digit
Letter or Digit
Letter or Digit
2
Extended Transition Function
δ
*
(q, λ) = q
δ
*
(q, wa) = δ(δ
*
(q, w), a)
Example 2.2: δ(q
0
, a) = q
1
& δ(q
1
, b) = q
2
⇒
δ
*
(q
0
,
ab) = q
2
Languages and DFAs
M = (Q, ∑, δ, q
0
, F)
L(M) = {w∈∑
*
| δ
*
(q
0
, w)∈F}
L(M) = {w∈∑
*
| δ
*
(q
0
, w)∉F}
Example 2.3
M = ({q
0
, q
1
, q
2
}, {a, b}, δ, q
0
, {q
1
})
L(M) = {a
n
b}
q
0
q
1
q
2
a, b
a, b
a
b
Trap State
A state at which the corresponding dfa is
unable to stop
Can be either final states or not
Example 2.4:
trap state
q
0
q
1
q
2
a, b
a, b
a
b
Theorem 2.1
M = (Q, ∑, δ, q
0
, F)
G
M
: associated transition graph
w∈∑
+
δ
*
(q
i
, w) = q
j
iff there is a walk labelled w
from q
i
to q
j
Transition Table
A table used to represent an automaton
Rows headers: states
Columns headers: input symbols
Entries: next states
Example 2.5
a b
q
o
q
o
q
1
q
1
q
2
q
2
q
2
q
2
q
2
q
0
q
1
q
2
a, b
a, b
a
b
Example 2.6
L(M) = {w∈{a, b}
*
| w starts with ab}
q
0
q
1
q
2
b
a, b
b
a
trap state
q
3
a
a, b
Example 2.7
L(M) = {w∈{0, 1}
*
| w does not contain
001}
λ 0 001
0
0, 1
1
1
00
0 1
0
trap state
Regular Languages
L is regular iff L = L(M) for some DFA M
Example 2.8
L = {awa | w∈{a, b}
*
}
q
0
q
2
q
3
b
a
b
a
trap state
q
1
a
a, b
b
Example 2.9
L
2
= {aw
1
aaw
2
a | w
1
, w
2
∈{a, b}
*
}
q
4
q
5
b a
b
a
trap state
q
1
a
a, b
b
q
0
q
2
q
3
b
b
a
a
b
Nondeterministic Finite Accepter (NFA)
M = (Q, ∑, δ, q
0
, F)
Q: finite set of internal states
∑: finite set of symbols - input alphabet
δ: Q × (∑ ∪ {λ}) → 2
Q
transition function
q
0
∈Q: initial state
F⊆Q: set of final states
Example 2.10
q
1
q
2
q
3
a
a
q
4
q
5
a
a
q
0
a
a
Example 2.11
q
0
q
1
q
2
1
0
0, 1
λ
Extended Transition Function
δ
*
(q
i
, w) = Q
j
δ
*
(q
i
, w) contains q
j
iff there is a walk
labelled w from q
i
to q
j
Example 2.12
δ
*
(q
1
, a) = {q
0
, q
1
, q
2
}
δ
*
(q
2
, λ) = {q
0
, q
2
}
q
0
q
1
q
2
λ
a
λ
