• Ta sẽ chứng minh (quy nạp theo k) bổ đề sau: với mọi Rkij đều tồn tại một
biểu thức chính quy ký hiệu cho Rkij .
k = 0: R0
ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc
Giả sử ta có bổ đề trên đú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
ij = (rk-1ik)(rk-1kk)*(rk-1kj) + rk-1ij
34 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 805 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Giải tích 1 - Chương 3: Automata hữu hạn và biểu thức chính quy, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1
Automata hữu hạn &
Biểu thức chính quy
Nội dung:
• 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
Chương 3:
2
Định nghĩa ôtômát (automata)
Định nghĩa: là máy trừu tượng có cơ cấu và hoạt động
đơn giản nhưng có khả năng đoán nhận ngôn ngữ
• Con người phải lập trình sẵn cho máy một ‘lộ trình’ để thực hiện
Bộ điều khiển
INPUT
OUTPUT
BỘ NHỚ
3
Phân loại automata
Automata đơn định (Deterministic Automata):
• Mỗi bước di chuyển chỉ được xác định duy nhất bởi cấu hình hiện
tại (hàm chuyển của automata là đơn trị)
Automata không đơn định (Non-deterministic Automata):
• Tại mỗi bước di chuyển, nó có vài khả năng để lựa chọn (hàm
chuyển của automata là đa trị)
4
Phân loại FA
FA
(Finite Automata)
DFA
Deterministic
Finite Automata
NFA
Nondeterministic
Finite Automata
Biểu thức
chính quy
5
Start
1
1
0
0
0
0 1
1
a b
c
d
q1 q0
q3 q2
Ví dụ:
Input
Bộ điều khiển
1 0 1 0 0 1 1 0
Q : 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
q0 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
Automata hữu hạn đơn định (DFA)
6
Mở rộng hàm chuyển trạng thái
1. δ(q, ) = q
2. δ(q, wa) = δ( δ(q,w), a) với w, a
Ngôn ngữ được chấp nhận:
L(M) = { x | δ( q0, x ) F }
Ngôn ngữ
chính quy Ví dụ: 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
7
Giải thuật hình thức
• Mục đích: kiểm tra một chuỗi nhập x có thuộc ngôn ngữ
L(M) được chấp nhận bởi automata M.
• Input: chuỗi nhập x$
• Output: câu trả lời ‘YES’ hoặc ‘NO’
• Giải thuật:
q := q0 ;
c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo}
While c $ do
begin
q := δ(q, c);
c := nextchar ;
end
If (q in F) then write("YES") else write("NO");
8
Automata hữu hạn không đơn định (NFA)
Nhận xét:
• Ứ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
q0 q3 q4
1
0
q1
q2
0
1
• Ví dụ: cho automata M (hình vẽ) và xét chuỗi nhập 01001
0
0
1 0 0 1 0
1 0 0 1
1
q0 q0 q0 q0 q0 q0
q3 q1 q3 q3 q1
q4 q4
9
Định nghĩa NFA
Chú ý: khái niệm δ(q, a) 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.
Hàm chuyển trạng thái mở rộng:
• δ(q, ) = {q}
• δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà pδ(r, a) }
= δ( δ(q,w), a)
• δ(P, w) = qP δ(q, w) với P Q
Q : 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 Σ → 2Q
q0 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)
10
Ví dụ: xét chuỗi nhập w=01001 và NFA đã cho ở trên
• M( {q0, q1, q2, q3, q4}, {0, 1}, δ, q0, {q2, q4} )
{q4} {q4} q4
Ø {q4} q3
{q2} {q2} q2
{q2} Ø q1
{q0,q1} {q0,q3} q0
1 0 Trạ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 q4 F nên w=01001 L(M)
Ví dụ về NFA
11
Sự tương đương giữa DFA & NFA
Định lý 1: Nếu L là tập được chấp nhận bởi một NFA thì tồn
tại một DFA chấp nhận L.
Giả sử NFA M={Q, Σ, δ, q0, F} chấp nhận L
Ta xây dựng DFA M’={Q’, Σ, δ’, q0’, F’} chấp nhận L
• Q’ = 2Q . Một phần tử trong Q’ được ký hiệu là [q0, q1, , qi] với q0, q1,
, qi Q
• q0’ = [q0]
• F’ là tập hợp các trạng thái của Q’ 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 δ’([q1, q2,..., qi], a) = [p1, p2,..., pj] nếu và chỉ nếu δ({q1,
q2,..., qi }, a) = {p1, p2,..., pj}
12
Ví dụ về sự tương đương giữa DFA & NFA
Ví dụ: NFA M ({q0, q1}, {0, 1}, δ, q0, {q1}) 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 M’ (Q’, {0, 1}, δ’, [q0], F’)
• Q’ = {, [q0], [q1], [q0, q1]}
• F’ = {[q1], [q0, q1]}
• Hàm chuyển δ’
δ’(, 0) = δ’(, 1) =
δ’([q0], 0) = [q0, q1]
δ’([q0], 1) = [q1]
δ’([q1], 0) =
δ’([q1], 1) = [q0, q1]
δ’([q0, q1], 0) = [q0, q1]
δ’([q0, q1], 1) = [q0, q1]
13
NFA với - dịch chuyển (NFA)
Định nghĩa: NFA M(Q, Σ, δ, q0, F)
• δ : hàm chuyển ánh xạ Q x (Σ {}) → 2Q
• Khái niệm δ(q, a) là tập hợp các trạng thái p sao cho có phép chuyển
nhãn a từ q tới p, với a (Σ {})
q0 q1 q2
0 1 2
Start
Ví dụ: xây dựng NFA chấp nhận chuỗi 0*1*2*
q0 q1 q2
0, 1
0 1 2
Start 1, 2
0, 1, 2
14
Mở rộng hàm chuyển trạng thái cho NFA
Định nghĩa -CLOSURE:
● -CLOSURE(q) = { p | có đường đi từ q tới p theo nhãn }
● -CLOSURE(P) = qP -CLOSURE(q)
Hàm chuyển trạng thái mở rộng: mở rộng δ thành δ*
• δ* : Q x Σ* → 2Q
• δ*(q, w) = { p | có đường đi từ q tới p theo nhãn w, trên đường đi có thể
chứa cạnh nhãn }
Ta có:
• δ*(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) = qR δ*(q, w)
15
Mở rộng hàm chuyển trạng thái cho NFA
Ví dụ:
q0 q1 q2
0 1 2
Start
• δ*(q0, ) = -CLOSURE(q0) = {q0, q1, q2}
• δ*(q0, 0) = -CLOSURE(δ(δ*(q0, ), 0))
= -CLOSURE(δ({q0, q1, q2}, 0)) = -CLOSURE(δ(q0, 0)
δ(q1, 0) δ(q2, 0) ) = -CLOSURE( {q0} )
= -CLOSURE({q0}) = {q0, q1, q2}
• δ*(q0, 01) = -CLOSURE(δ(δ*(q0, 0), 1))
= -CLOSURE(δ({q0, q1, q2}, 1)) = -CLOSURE({q1})
= {q1,q2}
• δ*(q0, 012) = -CLOSURE(δ(δ*(q0, 01), 2))
= -CLOSURE(δ({q1, q2}, 2)) = -CLOSURE({q2}) = {q2}
• Do q2 F nên w L(M)
Xét chuỗi nhập w = 012
16
Giải thuật hình thức cho NFA
Mục đích: mô phỏng hoạt động của NFA
Input: chuỗi nhập x$
Output: câu trả lời ‘YES’ (x được chấp nhận) hoặc ‘NO’
Giải thuật:
q := -CLOSURE (q0) ;
c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo}
While c $ do
begin
q := -CLOSURE (δ(q, c));
c := nextchar ;
end
If (q in F) then write("YES") else write("NO");
17
Sự tương đương giữa NFA và NFA
Định lý 2: 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.
Giả sử: NFA M(Q, Σ, δ, q0, F) chấp nhận L
Ta xây dựng: NFA M’={Q, Σ, δ’, q0, F’}
Với:
• F’ = F q0 nếu -CLOSURE(q0) chứa một trạng thái thuộc F.
Ngược lại, F’ = F
• δ’(q, a) = δ*(q, a)
18
Ví dụ:
Xây dựng NFA tương đương M’={Q, Σ, δ’, q0, F’}
• Q = {q0, q1, q2}
• Σ = {0, 1, 2}
• Trạng thái bắt đầu: q0
• F’ = {q0, q2}
• Hàm chuyển δ’
{q2} q2
{q2} {q1, q2} q1
{q2} {q1, q2} {q0, q1, q2} q0
2 1 0 Trạng thái
Inputs δ’
q0 q1 q2
0, 1
0 1 2
Start 1, 2
0, 1, 2
q0 q1 q2
0 1 2
Start
Sự tương đương giữa NFA và NFA
19
Xây dựng DFA từ NFA()
Ví dụ: xây dựng DFA tương đương với NFA sau:
M = (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 10 0 1
4 5
a b b Start
Ta xây dựng DFA M’= (Q’, Σ, δ’, q0’, F’) tương đương M
• Trạng thái bắt đầu: q0’ ↔ -CLOSURE(q0)
• F’ = { p | trong ký hiệu của p có chứa ít nhất một trạng thái của F }
• Xây dựng hàm chuyển δ’
20
Giải thuật xây dựng hàm chuyển δ’
Giải thuật:
T := -CLOSURE (q0) ; T chưa được đánh dấu ;
Thêm T vào tập các trạng thái Q’ của DFA ;
While Có một trạng thái T của DFA chưa được đánh dấu do
Begin
Đánh dấu T; { xét trạng thái T}
For Với mỗi ký hiệu nhập a do
begin
U:= -closure((T, a))
If U không có trong tập trạng thái Q’ của DFA then
begin
Thêm U vào tập các trạng thái Q’ của DFA ;
Trạng thái U chưa được đánh dấu;
[T, a] := U;{[T, a] là phần tử của bảng chuyển DFA}
end;
end;
End;
21
Xây dựng DFA từ NFA()
● -CLOSURE(q0) = {0, 1, 2, 4, 7} → q0’ = [0, 1, 2, 4, 7] = A
● -CLOSURE(δ(A, a)) = -CLOSURE({3, 8}) = {1, 2, 3, 4, 6,
7, 8} → B
● -CLOSURE(δ(A, b)) = -CLOSURE({5}) = {1, 2, 4, 5, 6, 7}
→ C
● -CLOSURE(δ(B, a)) = -CLOSURE({3, 8}) → B
● -CLOSURE(δ(B, b)) = -CLOSURE({5, 9}) = {1, 2, 4, 5, 6,
7, 9} → D
● -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, 10} → E
● -CLOSURE(δ(E, a)) = -CLOSURE({3, 8}) → B
● -CLOSURE(δ(E, b)) = -CLOSURE({5}) = → C
22
• Bảng hàm chuyển
E A
a
a
a
a
a
b
b
b
b
b
B D
C
Start
C B E
E B D
C B C
D B B
C B A
b a
Ký hiệu nhập
Trạng thá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 F)
Xây dựng DFA từ NFA()
23
Biểu thức chính quy (RE)
Vài ví dụ:
• 00 : là biểu thức chính quy biểu diễn tập {00}
• (0+1)* : 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 ... }
• (0+1)*011 : 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, ... }
24
Biểu thức chính quy (RE)
• (0+1)*00(0+1)* : 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, ... }
• (0+ )(1+10)* : 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* : {, 0, 1, 2, 01, 02, 12, 012, 0012, 0112,
... }
• 00*11*22* : 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
0+1+2+
25
Biểu thức chính quy (RE)
Định nghĩa: 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 Σ, a là BTCQ ký hiệu cho tập {a}
● Nếu r và s là các BTCQ ký hiệu cho các tập hợp R và S thì (r + s), (rs)
và ( r*) là các BTCQ ký hiệu cho các tập hợp R S, RS và R* tương ứng
Thứ tự ưu tiên:
Phép bao đóng > Phép nối kết > Phép hợp
Ví dụ:
• Biểu thức ((0(1*)) + 1) có thể viết là 01*+1
26
Tính chất đại số của BTCQ
Phép hợp:
• r + = + r = r
• r + r = r
• r + s = s + r
• (r + s) + t = r + (s + t) = r + s + t
Phép nối kết:
• r = r = r
• r = r =
• (r + s) t = rt + st
• r (s + t) = rs + rt
Phép bao đóng:
• * =
• * =
• r*r* = r*
• (r*)* = r*
• r* = + r + r2 + + rk +
• r* = + r+
• ( + r)+ = ( + r)* = r*
• r*r = r r* = r+
Tổng hợp:
• (r* + s*)* = (r*s*)* = (r + s)*
• (rs)*r = r(sr)*
• (r*s)* r* = (r + s)*
27
Sự tương đương giữa NFA và BTCQ
Định lý 3: 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)
Chứng minh: quy nạp theo số phép toán
• Xét r không có phép toán nào
Start
q0 q0 q0 qf qf
Start Start
r = r = r = a
a
Các NFA cho các kết hợp đơn
• Xét r có i phép toán: r = r1 + r2, r = r1r2 hoặc r = r1*
Xây dựng NFA M1 = (Q1, Σ1, δ1, q1, {f1}) và M2 = (Q2, Σ2, δ2, q2, {f2}) sao
cho L(M1) = L(r1) và L(M2) = L(r2)
Xây dựng NFA M như sau:
28
Sự tương đương giữa NFA và BTCQ
q1 f1
f0
M1
q2 f2
M2
q0
Start
q1
f1 M1 f0 q0
Start
• r = r1 + r2
• r = r1r2
• r = r1*
q2 f2 M2 q1 f1 M1
Start
29
Sự tương đương giữa NFA và BTCQ
Ví dụ: xây dựng NFA chấp nhận BTCQ r = 01* + 1
• 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
1 Start
r2
q3 q4
0 Start
r3
q5 q6
1 Start q7 q8
r4 = r5* = 1*
q7 q5
1
Start q3 q8
q4
0
q6
r1 = r3r4 = 01*
q4 q7
Start
q9 q10
q3
0 q5
q1 q2
q6 q8
1
1
r = r1 + r2 = 01* + 1
q5 q6
1 Start
r5
30
Sự tương đương giữa DFA và BTCQ
Định lý 4: Nếu L được chấp nhận bởi một DFA, thì L được
ký hiệu bởi một BTCQ
Chứng minh:
• L được chấp nhận bởi DFA M({q1, q2,..., qn}, Σ, δ, q1, F) • Đặt Rkij = {x | δ(qi, x) = qj và nếu δ(qi, y) = ql (y x) thì l ≤ k} (hay Rkij 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 :
Rkij = R
k-1
ik(R
k-1
kk)*R
k-1
kj R
k-1
ij
R0ij =
{a | δ(qi, a) = qj}, nếu i ≠ j
{a | δ(qi, a) = qj} {}, nếu i = j
31
Sự tương đương giữa DFA và BTCQ
• Ta sẽ chứng minh (quy nạp theo k) bổ đề sau: với mọi Rkij đều tồn tại một
biểu thức chính quy ký hiệu cho Rkij .
k = 0: R0ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc
Giả sử ta có bổ đề trên đúng với k-1, tức là tồn tại BTCQ rk-1lm sao
cho L(rk-1lm) = R
k-1
lm
Vậy đối với Rkij ta có thể chọn BTCQ
rkij = (r
k-1
ik)(r
k-1
kk)*(r
k-1
kj) + r
k-1
ij
→ bổ đề đã được chứng minh
● Ta có nhận xét:
L(M) = qj F R
n
1j
● 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}
32
Sự tương đương giữa DFA và BTCQ
Ví dụ: viết BTCQ cho DFA
Ta cần viết biểu thức:
r = r312 + r
3
13
Ta có:
• r312 = r
2
13(r
2
33)*r
2
32 + r
2
12
• r313 = r
2
13(r
2
33)*r
2
33 + r
2
13
1
1
q1
q2
q3
0
0 0, 1
Start
33
Thay vào và rút gọn, ta có:
r = 0*1((0 + 1)0*1)* ( + (0 + 1)(00)*) + 0(00)*
+ (0 + 1)0*1 rk33
(0 + 1)(00)* 0 + 1 0 + 1 rk32
(0 + 1)(00)*0 rk31
0*1 1 + 01 1 rk23
(00)* + 00 rk22
0(00)* 0 0 rk21
0*1 1 1 rk13
0(00)* 0 0 rk12
(00)* rk11
k = 2 k = 1 k = 0
Sự tương đương giữa DFA và BTCQ
34
Mối liên hệ giữa FA và BTCQ
Sơ đồ liên hệ:
DFA
NFA
NFA
RE
Định lý 4 Định lý 2
Định lý 1
Định lý 3
Các file đính kèm theo tài liệu này:
- slide3_new_3388.pdf