Nếu L ñược chấp nhận bởi một DFA, thì L ñược
ký hiệu bởi một BTCQ
• L ñược chấp nhận bởi DFA M({q1, q2,., qn}, Σ, δ, q1, F)
• ðặt
R k i
j= {x | δ(qi, x) = qjvà nếu δ(qi, y) = ql(y ⊂x) thì l ≤ k}
(hay
R k i
jlà tập hợp tất cả các chuỗi làm cho automata ñi từ
trạng thái i ñến trạng thái j mà không ñi ngang qua trạng
thái nào lớn hơn k)
• ðịnh nghĩa ñệ quy của Rkij :
k
i j = Rk-1 ik(Rk-1 kk)*Rk-1 kj ∪Rk-1 ij
0
i j
{a | δ(qi, a) = qj}, nếu i ≠ j
{a | δ(qi, a) = qj} ∪ {ε}, nếu i = j
8 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1003 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Bài giảng Tin học - Chương 3: Automata hữu hạn và biểu thức chính qui, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
1• Khái niệm DFA & NFA
• Sự tương ñương giữa DFA & NFA
• Biểu thức chính quy
• Các tính chất của tập chính quy
2
(
F
inite
A
utomata)
D
eterministic
F
inite
A
utomata
N
ondeterministic
F
inite
A
utomata
3
Start
1
1
0
0
0
0 1
1
a b
c
d
q
1
q
0
q
3
q
2
I
n p u
t
B
ñ
i
u
k h i
n
10100110
: tập hữu hạn các trạng thái (p, q)
: bộ chữ cái nhập (a, b ; w, x, y )
: hàm chuyển, ánh xạ: Q x Σ → Q
0 ∈ Q : trạng thái bắt ñầu.
F ⊆ Q : tập các trạng thái kết thúc.
M=(Q, Σ, δ, q0, F)
Trạng thái bắt ñầu
Trạng thái kết thúc
x
Phép chuyển trên nhãn x
4
ε
∀
0 ∈
Ngôn ngữ
chính quy chuỗi nhập w=110101
• δ(q0, 1) = q1
• δ(q0, 11) = δ(q1, 1) = q0
• δ(q0, 110) = δ(q1, 10) = δ(q0, 0) = q2
• δ(q0, 1101) = δ(q1, 101) = δ(q0, 01) = δ(q2, 1) = q3
• δ(q0, 11010) = = δ(q3, 0) = q1
• δ(q0, 110101) = = δ(q1, 1) = q0 ∈ F
Printed with FinePrint - purchase at www.fineprint.com
5• kiểm tra một chuỗi nhập có thuộc ngôn ngữ
ñược chấp nhận bởi automata .
• chuỗi nhập
• câu trả lời ‘ ’ hoặc ‘ ’
•
q := q0 ;
c := nextchar ;
{
c
l
à
k
ý
h
i
u n
h
p
ñ
ư c
ñ
c
t
i
p
t h
e o
}
While c $ do
begin
q := δ(q, c);
c := nextchar ;
end
If (q in F) then write("YES") else write("NO");
6
• Ứng với một trạng thái và một ký tự nhập, có thể có
không, một hoặc nhiều phép chuyển trạng thái.
• DFA là một trường hợp ñặc biệt của NFA
Start 0
1
1
0
1
0
q
0
q
3
q
4
1
0
q
1
q
2
0
1
• cho automata M (hình vẽ) và xét chuỗi nhập
0
0
10010
1 0 0 1
1
q0 q0 q0 q0 q0 q0
q3 q1 q3 q3 q1
q4 q4
7
: khái niệm là tập hợp tất cả các trạng thái p
sao cho có phép chuyển từ trạng thái q trên nhãn a.
• ε
• có một trạng thái r trong mà p∈
• ∪ q∈P với ∀ ⊆
: tập hữu hạn các trạng thái.
: bộ chữ cái nhập.
: hàm chuyển ánh xạ Q x Σ →
Q
0 ∈ Q : trạng thái bắt ñầu.
F ⊆ Q : tập các trạng thái kết thúc.
M=(Q, Σ, δ, q0, F)
8
• 0 1 2 3 4 0 2 4
{q4}{q4}q4
Ø{q4}q3
{q2}{q2}q2
{q2}Øq1
{q0,q1} {q0,q3} q0
10Trạng thái
Input
δ • δ(q0, 0) = {q0,q3}
• δ(q0, 01) = δ( δ(q0, 0), 1)
= δ({q0, q3},1) = δ(q0, 1)
∪ δ(q3, 1) = {q0, q1}
• δ(q0, 010) = {q0, q3}
• δ(q0, 0100) = {q0, q3, q4}
• δ(q0, 01001) = {q0, q1, q4}
Do 4∈ nên ∈
Printed with FinePrint - purchase at www.fineprint.com
9Nếu là tập ñược chấp nhận bởi một thì tồn
tại một chấp nhận .
Giả sử 0 chấp nhận L
Ta xây dựng 0 chấp nhận L
•
Q
Một phần tử trong ñược ký hiệu là [q0, q1,
, qi] với q0, q1, , qi ∈
• 0 0
• là tập hợp các trạng thái của có chứa ít nhất một
trạng thái kết thúc trong tập F của M
• Hàm chuyển 1 2 i 1 2 j nếu và
chỉ nếu 1 2 i 1 2 j
10
NFA 0 1 0 1 với hàm chuyển
(q0,0) = {q0, q1}, (q0,1) = {q1}, (q1,0) = ∅, (q1,1) = {q0, q1}
Ta sẽ xây dựng DFA tương ñương 0
• = {∅ [q0], [q1], [q0, q1]}
• = {[q1], [q0, q1]}
• Hàm chuyển
∅ ∅ ∅
([q0], 0) = [q0, q1]
([q0], 1) = [q1]
([q1], 0) = ∅
([q1], 1) = [q0, q1]
([q0, q1], 0) = [q0, q1]
([q0, q1], 1) = [q0, q1]
11
ε ε
: ε 0
• δ : hàm chuyển ánh xạ Q x ( ∪ ε ) → 2Q
• Khái niệm là tập hợp các trạng thái p sao cho
có phép chuyển nhãn từ q tới p, với a ∈ (Σ ∪ {ε})
NFA chấp nhận chuỗi 0+1+2+
q
0
q
1
q
2
ε
0 1 2
Start
ε
q
0
q
1
q
3
0
0 1 2
Start 1 q
2
2
xây dựng NFA chấp nhận chuỗi 0*1*2*
12
ε
ε
● ε (q) = { p | có ñường ñi từ q tới p theo nhãn ε }
● ε (P) = ∪ q∈ P ε (q)
mở rộng thành
• Q x → 2Q
• (q, w) = { p | có ñường ñi từ q tới p theo nhãn , trên
ñường ñi có thể chứa cạnh nhãn ε }
• δ*(q, ε) = ε-CLOSURE(q)
• δ*(q,a) = ε-CLOSURE(δ(δ*(q, ε),a))
• δ*(q, wa) = ε-CLOSURE( δ( δ*(q, w), a) )
Cách khác: δ*(q, wa) = ε-CLOSURE(P)
với P = { p | r ∈ δ*(q, w) và p ∈ δ(r, a) }
• δ*(R, w) = ∪ q∈ R δ*(q, w)
Printed with FinePrint - purchase at www.fineprint.com
13
ε
q
0
q
1
q
2
ε
0 1 2
Start
ε
Xét chuỗi nhập
• δ*(q0, ε) = ε-CLOSURE(q0) = {q0, q1, q2}
• δ*(q0, ) = ε-CLOSURE(δ(δ*(q0, ε), 0))
= ε-CLOSURE(δ({q0, q1, q2}, 0)) = ε-CLOSURE(δ(q0, 0) ∪
δ(q1, 0) ∪ δ(q2, 0) ) = ε-CLOSURE( {q0} ∪ ∅ ∪ ∅ )
= ε-CLOSURE({q0}) = {q0, q1, q2}
• δ*(q0, ) = ε-CLOSURE(δ(δ*(q0, 0), 1))
= ε-CLOSURE(δ({q0, q1, q2}, 1)) = ε-CLOSURE({q1})
= {q1,q2}
• δ*(q0, ) = ε-CLOSURE(δ(δ*(q0, 01), 2))
= ε-CLOSURE(δ({q1, q2}, 2)) = ε-CLOSURE({q2}) = {q2}
• Do q2 ∈ F nên w ∈ L(M)
14
ε
mô phỏng hoạt ñộng của NFAε
chuỗi nhập
câu trả lời ‘YES’ (x ñược chấp nhận) hoặc ‘NO’
q := ε
C L O S U R E
(q0) ;
c := nextchar ;
{
c
l
à
k
ý
h
i
u n
h
p
ñ
ư c
ñ
c
t
i
p
t h
e o
}
While c $ do
begin
q := ε
C L O S U R E
(δ(q, c));
c := nextchar ;
end
If (q in F) then write("YES") else write("NO");
15
ε
nếu L ñược chấp nhận bởi một NFA có ε-dịch
chuyển thì L cũng ñược chấp nhận bởi một NFA không có
ε-dịch chuyển.
ε M(Q, Σ, δ, q0, F) chấp nhận L
Ta xây dựng: M’={Q, Σ, , q0, }
Với:
• ∪ 0 nếu ε-CLOSURE(q0) chứa một trạng thái thuộc F.
Ngược lại,
• (q, a) = (q, a)
16
Xây dựng NFA tương ñương M’={Q, Σ, , q0, }
• Q = {q0, q1, q2}
• Σ = {0, 1, 2}
• Trạng thái bắt ñầu: q0
• = {q0, q2}
• Hàm chuyển
{q2}∅∅q2
{q2}{q1, q2}∅q1
{q2}{q1, q2}{q0, q1, q2}q0
210Trạng thái
Inputsδ’
q
0
q
1
q
2
0, 1
0 1 2
Start 1, 2
0, 1, 2
q
0
q
1
q
2
ε
0 1 2
Start ε
ε
Printed with FinePrint - purchase at www.fineprint.com
17
ε
xây dựng DFA tương ñương với NFAε sau:
= (Q={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Σ={a, b}, δ, 0, F={10})
a
b
ε
ε
ε
ε
εε
ε
ε
2 3
6 7 8 9
1 0
0 1
4 5
a b bStart
Ta xây dựng = (Q’, Σ, δ’, q0’, F’) tương ñương
• Trạng thái bắt ñầu: q0’ ↔ ε-CLOSURE(q0)
• F’ = { | trong ký hiệu của có chứa ít nhất một trạng
thái của F }
• Xây dựng hàm chuyển δ’
18
T := ε
C
L
O S
U R E
(q0) ;
T
c
h
ư a
ñ
ư c
ñ á
n
h d
fi
u ;
T
h ê
m
T
v
à
o
t
$
p c
á
c
t
r 'n g
t
h á i Q ’
c
,
a
D F A
;
While
C ó
m
2
t t
r 'n g
t
h á i
T
c
,
a
D F A
c
h
ư a
ñ
ư c
ñ á
n
h d
fi
u do
Begin
ð
á
n
h d
fi
u
T
; { xét trạng thái T}
For
V
5 i
m
6
i k ý h i 9
u n
h $
p a
do
begin
U
: =
ε
c
l
o s u r e
(
δ
(
T
,
a
) )
If
U
k h ô
n g c
ó
t
r o n g
t
$
p
t
r 'n g
t
h á i Q ’
c
,
a
D F A
then
begin
T
h ê
m
U
v
à
o
t
$
p c
á
c
t
r 'n g
t
h á i Q ’
c
,
a
D F A
;
T
r 'n g
t
h á i
U
c
h
ư a
ñ
ư c
ñ á
n
h d
fi
u ;
δ
[
T
,
a
]
: =
U
; {δ[T, a] là phần tử của bảng chuyển DFA}
end;
end;
End;
19
ε
● ε-CLOSURE(q0) = {0, 1, 2, 4, 7} → q0’ = [0, 1, 2, 4, 7] =
● ε-CLOSURE(δ(A, a)) = ε-CLOSURE({3, 8}) = {1, 2, 3, 4, 6,
7, 8} →
● ε-CLOSURE(δ(A, b)) = ε-CLOSURE({5}) = {1, 2, 4, 5, 6, 7}
→
● ε-CLOSURE(δ(B, a)) = ε-CLOSURE({3, 8}) → B
● ε-CLOSURE(δ(B, b)) = ε-CLOSURE({5, 9}) = {1, 2, 4, 5, 6,
7, 9} →
● ε-CLOSURE(δ(C, a)) = ε-CLOSURE({3, 8}) → B
● ε-CLOSURE(δ(C, b)) = ε-CLOSURE({5}) = → C
● ε-CLOSURE(δ(D, a)) = ε-CLOSURE({3, 8}) → B
● ε-CLOSURE(δ(D, b)) = ε-CLOSURE({5,10}) = {1, 2, 4, 5,
6, 7, } →
● ε-CLOSURE(δ(E, a)) = ε-CLOSURE({3, 8}) → B
● ε-CLOSURE(δ(E, b)) = ε-CLOSURE({5}) = → C
20
• Bảng hàm chuyển
EA
a
a
a
a
a
b
b
b
b
bB D
C
Start
CBE
EBD
CBC
DBB
CBA
ba
K ý h i N
u n
h Q
p
T
r U n g
t h á i
• Ký hiệu bắt ñầu: q0’ = A (↔ ε-CLOSURE(q0) )
• Tập trạng thái kết thúc: F’ = {E} (vì trong E có chứa trạng
thái 10 ∈ )
ε
Printed with FinePrint - purchase at www.fineprint.com
21
• : là biểu thức chính quy biểu diễn tập {00}
• : tập hợp tất cả các chuỗi số 0 và số 1, kể cả
chuỗi rỗng = {ε, 0, 1, 00, 01, 10, 11, 010, 011, 0010
... }
• * : ký hiệu cho tất cả các chuỗi 0, 1 tận cùng
bởi 011 = {011, 0011, 1011, 00011, 11011, ... }
• : tập hợp tất cả các chuỗi 0,1 có ít nhất
hai số 0 liên tiếp = {00, 000, 100, 0000, 0001, 1000,
1001, 011001, ... }
• ε : tất cả các chuỗi không có hai số 0 liên
tiếp = {ε, 0, 01, 010, 1, 10, 01010, 0111, ... }
• * * * : {ε, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, ... }
• : tất cả các chuỗi trong tập 0*1*2* với ít nhất
một ký hiệu 0, 1 và 2 ↔ viết gọn thành
+ + +
22
cho Σ là một bộ chữ cái. BTCQ trên Σ là các tập
hợp mà chúng mô tả ñược ñịnh nghĩa ñệ quy như sau:
● ∅ là BTCQ ký hiệu cho tập rỗng
● ε là BTCQ ký hiệu cho tập {ε}
● ∀a ∈ Σ, là BTCQ ký hiệu cho tập {a}
● Nếu và là các BTCQ ký hiệu cho các tập hợp R và
S thì , và là các BTCQ ký hiệu cho các
tập hợp R ∪ S, RS và R* tương ứng
• Biểu thức có thể viết là
23
• r + ∅ = ∅ + r = r
• r + r = r
• r + s = s + r
• (r + s) + t = r + (s + t) = r + s + t
• rε = εr = r
• r∅ = ∅r = ∅
• (r + s) t = rt + st
• r (s + t) = rs + rt
• ε* = ε
• ∅* = ∅
• r*r* = r*
• (r*)* = r*
• r* = ε + r + r2 + + rk +
• r* = ε + r+
• (ε + r)+ = (ε + r)* = r*
• r*r = r r* = r+
• (r* + s*)* = (r*s*)* = (r + s)*
• (rs)*r = r(sr)*
• (r*s)* r* = (r + s)*
24
ε
nếu r là BTCQ thì tồn tại một NFA với ε-dịch
chuyển chấp nhận L(r)
quy nạp theo
• Xét không có phép toán nào
Start
q0 q0 q0 qfqf
Start Start
r = ε r = ∅ r = a
a
Các NFAε cho các kết hợp ñơn
• Xét có i phép toán: 1 2, 1 2 hoặc 1
Xây dựng NFAε 1 = (Q1, Σ1, δ1, q1, {f1}) và 2 = (Q2,
Σ2, δ2, q2, {f2}) sao cho L(M1) = L(r1) và L(M2) = L(r2)
Xây dựng NFAε như sau:
Printed with FinePrint - purchase at www.fineprint.com
25
ε
q1 f1
f0
M1
q2 f2M2
q0
Start
ε
ε
ε
ε
εq1 f1M1 f0q0
ε
ε
ε
Start
•
r = r
1
+
r
2
•
r = r
1
r
2
•
r = r
1
*
q2 f2M2q1 f1M1
Start ε
26
ε
xây dựng NFAε chấp nhận BTCQ
• r có dạng: r = r1 + r2 với r1 = 01* và r2 = 1
• r1 có dạng r1 = r3r4 với r3 = 0 và r4 = 1*
• r4 có dạng r4 = r5* với r5 = 1
q1 q2
1Start
r
2
q3 q4
0Start
r
3
ε
q5 q6
1Start q7 q8
ε ε
ε
r
4
= r
5
*
=
1 *
ε
ε
ε
q7 q5
1
Start q3 q8
ε ε
q4
0
q6
r
1
= r
3
r
4
=
0 1 *
ε
ε
εq4 q7
Start q9 q10
ε
ε
q3
0 q5
q1 q2
q6 q8
1ε
1
ε
ε ε
r = r
1
+
r
2
=
0 1 *
+
1
q5 q6
1Start
r
5
27
Nếu L ñược chấp nhận bởi một DFA, thì L ñược
ký hiệu bởi một BTCQ
•
L
ñược chấp nhận bởi DFA
M
({q1, q2,..., qn}, Σ, δ, q1, F)
• ðặt
R
k
i j = {x | δ(qi, x) = qj và nếu δ(qi, y) = ql (y ⊂ x) thì l ≤ k}
(hay
R
k
i j là tập hợp tất cả các chuỗi làm cho automata ñi từ
trạng thái i ñến trạng thái j mà không ñi ngang qua trạng
thái nào lớn hơn k)
• ðịnh nghĩa ñệ quy của Rkij :
k
i j = Rk-1ik(R
k-1
kk)*R
k-1
kj ∪ R
k-1
ij
0
i j
{a | δ(qi, a) = qj}, nếu i ≠ j
{a | δ(qi, a) = qj} ∪ {ε}, nếu i = j
28
• Quy nạp theo
k
:
k = 0: R0ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc ε
Giả sử ta có ñịnh lý ñúng với k-1, tức là tồn tại
BTCQ rk-1lm sao cho L(rk-1lm) = Rk-1lm
Vậy ñối với rkij ta có thể chọn BTCQ
(rk-1ik)(r
k-1
kk)*(r
k-1
kj) + r
k-1
ij
Ta có nhận xét:
L(M) = ∪qj ∈F Rn1j
Vậy L có thể ñược ký hiệu bằng BTCQ
r = rn1j1 + r
n
1j2 + + r
n
1jp
với F = {qj1, qj2, , qjp}
Printed with FinePrint - purchase at www.fineprint.com
29
viết BTCQ cho DFA
Ta cần viết biểu thức:
3
1 2
3
1 3
Ta có:
• r312 = r
2
13(r
2
33)*r
2
32 + r
2
12
• r313 = r213(r233)*r233 + r213
1
1
q1 q2 q3
0
0 0, 1
Start
30
Thay vào và rút gọn, ta có:
r = ε
ε + (0 + 1)0*1εεr
k
3 3
(0 + 1)(00)*0 + 10 + 1r
k
3 2
(0 + 1)(00)*0∅∅r
k
3 1
0*11 + 011r
k
2 3
(00)*ε + 00εr
k
2 2
0(00)*00r
k
2 1
0*111r
k
1 3
0(00)*00r
k
1 2
(00)*εεr
k
1 1
k
=
2k
=
1k
=
0
31
DFA
NFAε
NFA
RE
ð
n
h l ý
4
ð
n
h l ý
2
ð
n
h l ý
1
ð
n
h l ý
3
Printed with FinePrint - purchase at www.fineprint.com
Các file đính kèm theo tài liệu này:
- ba_i_gia_ng_tin_ho_c_li_thuye_t_vo_huy_nh_tramslide3_print_4411.pdf