Chương 4 Các tính chất của
4.3 Nhận biết các ngôn ngữ không chính qui
Trang131
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Tính đóng của NNCQ
Đóng dưới các phép toán tập hợp đơn giản.
Định lý 4.1
Nếu L1 và L2 là các NNCQ, thì L1∪L2, L1∩L2 , L1L2, L và L1*
cũng vậy. Chúng ta nói rằng họ NNCQ là đóng dưới các p hép
hội, giao, kết nối, bù và bao đóng-sao.
Chứng minh
Nếu L1, L2 là chính qui thì ∃ các BTCQ r1, r2 sao cho L1= L(r1),
L2= L(r2). Theo định nghĩa r1 + r2, r1r2 và r1* là các BTC Q định
nghĩa các ngôn ngữ L1∪L2, L1L2, và L1*. Vì vậy họ NNC Q là
đóng đối với các phép toán này.
Để CM tính đóng đối với phép bù, cho M = (Q, Σ, δ, q0, F ) là
dfa chấp nhận L1, thì dfa M = (Q, Σ , δ, q0, Q - F) chấp nhậ n L.
Trang132
Lý thuyếtÔtômát&NNHT -KhoaCông NghệThôngTin
Đóng dưới các phép toán
^
Ta xây dựng dfa chấp nhận L1 ∩L2)^),,(,^,,( 00 FpqQMδ Σ=
tập hợp đơn giản
Để CM tính đóng đối với phép giao ta có hai cách như sau .
Cách thứ nhất
Dựa vào qui tắc De Morgan ta có
L1 I L2 = L1 I L2 = L1 U L2
Dựa vào tính đóng của phép bù và phép hội vừa được chứ ng minh ở trên ta suy ra tính đóng đối với phép giao.
Cách thứ hai
Ta sẽ xây dựng một dfa cho L1 ∩L2.
Cho M1 = (Q, Σ, δ1, q0, F1) và M2 = (P, Σ, δ2, p0, F2) là cá c dfa
lần lượt chấp nhận L1, L2.
^ ^
bằng thủ tục intersection sau.
Trang133
Lý thuyếtÔtômát &NNHT- KhoaCông NghệThôngTin
Thủ tục: intersection
Thủ tục: intersection
Input: dfa M1 = (Q, Σ, δ1, q0, F1) và dfa M2 = (P, Σ, δ2, p0, F2)
^ ^
Q = Q ×P, tức là Q = {(qi, pj): trong đó qi ∈ Q còn pj ∈ P}.
Các chuyển trạng thái được xây dựng như sau
δ ((qi, pj), a) = (qk, pl)
nếu và chỉ nếu
Output: dfa )^),,(,^,,( 00 FpqQMδ Σ=
^ ^
^
δ1(qi, a) = qk và δ2(pj, a) = pl F = {(qi, pj): trong đó qi ∈ F1 còn pj ∈ F2}
Trang 134
Lýthuyết Ôtômát& NNHT-Khoa Công NghệThôngTin
^
Thủ tục: intersection (tt)
Cách xây dựng trên mô phỏng lại quá trình xử lý của đồng
thời ^
^ Ví dụ
Tìm dfa giao của L1={a2nbm: n, m ≥ 0} và L2={a3nb2m: n, m ≥ 0}
L1
L
2
a
p2 a
q1
q0 a
p0 a
b
p
1
a
b p3 b p4
δ ^
hai dfa M1 và M2. Ngoài ra dựa vào định nghĩa của ta thấy M chỉ chấp nhận những chuỗi mà được đồng thời cả hai dfa M1 và M2 chấp nhận. Vì vậy M chấp nhận L1 ∩L2.
q2
b b
L1 ∩L2 q
2 p3
Trang 135
q0 p1
a q1 p2
aq1 p
0
q0 p0 a
q0 p2 a
q1 p1 a
b
b
b q2 p4
Lýthuyết Ôtômát&NNHT-Khoa Công NghệThôngTin
Đóng dưới các phép toán tập hợp đơn giản (tt)
Định lý 4.2
Họ NNCQ là đóng dưới phép hiệu và nghịch đảo.
Chứng minh
Để chứng minh tính đóng đối với phép hiệu dựa vào các q ui tắc
tập hợp ta có:
L1 - L2 = L1 ∩L2
Dựa vào tính đóng của phép bù và phép giao đã được chứn g
minh, suy ra tính đóng cho phép hiệu.
Tính đóng của phép nghịch đảo đã được chứng minh ở Ch ương
3, slide 128.
Trang 136
Lýthuyết Ôtômát &NNHT-Khoa Công NghệThôngTin
Đóng dưới các phép toán khác
Phép đồng hình (homomorphism) Định nghĩa 4.1
Giả sử Σ và Γ là các bảng chữ cái, thì một hàm
h: Σ → Γ*
được gọi là một phép đồng hình. Bằng lời, một phép đồng hình
là một sự thay thế trong đó mỗi kí hiệu đơn được thay thế bằngmột chuỗi.
Mở rộng nếu w = a1a2. . . an, thì
h(w) = h(a1)h(a2). . .h(an)
Nếu L là ngôn ngữ trên Σ, thì ảnh đồng hình (homomorph ic image) của nó được định nghĩa là
h(L) = {h(w): w ∈ L}.
Trang 137
Lý thuyếtÔtômát &NNHT- KhoaCông NghệThôngTin
Ví dụ
Cho Σ ={a, b}, Γ ={a, b, c} và h được định nghĩa như sau h(a) = ab,
h(b) = bbc.
Thì h(aba) = abbbcab. Ảnh đồng hình của L = {aa, aba} là ngôn ngữ h(L) = {abab, abbbcab}.
Cho Σ ={a, b}, Γ ={ b, c, d } và h được định nghĩa như sau h(a) = dbcc, h(b) = bdc.
Nếu L là ngôn ngữ được biểu thị bởi BTCQ r = (a + b*)(aa)*, thì
r1 = (dbcc + (bdc)*)(dbccdbcc)*,
là BTCQ biểu thị cho h(L). Từ đó dẫn ta tới định lý sau
Trang138
Lýthuyết Ôtômát& NNHT-Khoa CôngNghệ ThôngTin
Định lý
Định lý 4.3
Cho h là một đồng hình. Nếu L là một NNCQ, thì ảnh đồn g hình của nó h(L) cũng là NNCQ. Họ các NNCQ vì vậy là đóngdưới phép đồng hình bất kỳ.
Phép thương đúng Định nghĩa 4.2
Cho w, v ∈ Σ* thì thương đúng (right quotient) của w cho v được kí hiệu và định nghĩa là w/v = u nếu w = uv, nghĩa là nếu v
là tiếp vĩ ngữ của w thì w/v là tiếp đầu ngữ tương ứng của w.
Cho L1 và L2 là các ngôn ngữ trên bảng chữ cái giống nha u, thì
thương đúng của L1 với L2 được định nghĩa là L1/L2 = {w/v: w ∈ L1, v ∈ L2 }
= {x : xy ∈ L1 với một y nào đó ∈ L2 }
Trang139
LýthuyếtÔtômát& NNHT-Khoa CôngNghệ ThôngTin
Ví dụ
Cho L1 = {anbm: n ≥ 1, m ≥ 0} ∪{ba} và L2 = {bm: m ≥ 1}
, thì
L1 /L2 = { anbm: n ≥ 1, m ≥ 0}.
Vì L1, L2, và L1 /L2 là các NNCQ , điều này gợi ý cho chún g ta
rằng thương đúng của hai NNCQ cũng là NNCQ.
Bổ đề
Cho M1 = (Q1, Σ, δ1, q0, F1) là một dfa cho L1. Nếu một tr ạng
thái q nào đó ∈ Q1 có tính chất tồn tại một chuỗi y nào đó
∈ L2
sao cho δ1*(q, y) ∈ F1 thì ∀ x mà δ1*(q0, x) = q, x sẽ ∈ L1/ L2.
Và vì vậy nếu thay những trạng thái kết thúc của M bằng n hữngtrạng thái q có tính chất này thì ta sẽ có một dfa mà chấp n hận
L1/L2.
Trang 140
Lýthuyết Ôtômát& NNHT-Khoa Công NghệThôngTin
Định lý
M1 M2
q0 p0
x y q
y
qf pf
∀x mà δ1*(q0, x) = q thì x ∈ L1/L2
Định lý 4.4
Nếu L1 và L2 là các NNCQ, thì L1/L2 cũng chính qui. Chún g ta
nói rằng họ NNCQ là đóng dưới phép thương đúng.
Chứng minh
Cho L1 = L(M) trong đó M = (Q, Σ, δ, q0, F) là một dfa. Ta
xây
^ ^
dựng một dfa khác M =( Q, Σ, δ, q0, F ), chấp nhận L1/L2,b ằng
cách chỉ thay đổi tập F thông qua thủ tục sau.
Trang 141
Lýthuyết Ôtômát& NNHT-Khoa Công NghệThôngTin
Thủ tục: right quotient
Thủ tục: right quotient
Input: dfa M1 = (Q, Σ, δ1, q0, F1) và dfa M2 = (P, Σ, δ2, p0 , F2)
^
Ta xác định F bằng cách xác định với mỗi qi ∈ Q, có tồn t ại
Output: dfa = (Q, Σ, δ1, q0, )M
^F
có tính chất đã nói ở trên và thêm qi vào . Thực hiện điều này^ F∀ qi ∈ Q, ta sẽ xác định được và vì vậy xây dựng được .^F
M
^
^
hay không chuỗi y ∈ L2 sao cho δ*(qi, y) ∈ F. Nếu đúng t hì đưa
qi vào F.
Điều này có thể thực hiện được bằng cách xét các dfa Mi = (Q,
Σ, δ1, qi, F). chính là M nhưng trạng thái khởi đầu q0 được thay
bằng qi. Rồi xét xem L2 ∩L(Mi) có ≠ ∅không. Nếu khác thì qi
^
Trang142
Lýthuyết Ôtômát& NNHT-Khoa CôngNghệ ThôngTin
Ví dụ
Tìm L1/L2 cho
L1 = L(a*baa*), a
L2 = L(ab*).
a a a
M1 b a L1/L2 b a
M2
b a
Trang 143
LýthuyếtÔtômát& NNHT-Khoa CôngNghệ ThôngTin
q0 q1 q2 q0 q1 q2
p0 p1
Các câu hỏi cơ bản về NNCQ
Cho một ngôn ngữ L và một chuỗi w, chúng ta có thể xác định
được w có phải là một phần tử của L hay không?
Đây là một câu hỏi thành viên (membership) và phương pháp để tr ả lời
nó được gọi là giải thuật thành viên.
Một ngôn ngữ đã cho là hữu hạn hay vô hạn?
Hai ngôn ngữ nào đó có giống nhau không?
Có hay không một ngôn ngữ là tập con của một ngôn ngữ khác?
Biểu diễn chuẩn (Standard representation)
Chúng ta nói rằng một NNCQ là được cho trong một dạng biểu
diễn chuẩn nếu và chỉ nếu nó được mô tả bởi một trong ba dạngsau đây: một ôtômát hữu hạn, một BTCQ hoặc một VPCQ .
Chú ý từ một dạng biểu diễn chuẩn này luôn có thể xác định được các
dạng biểu diễn chuẩn khác nhờ vào các định lý đã được CM trước đây.
Trang 144
Lýthuyết Ôtômát &NNHT-Khoa Công NghệThôngTin
Các định lý
Định lý 4.5
Cho một biểu diễn chuẩn của một NNCQ L bất kỳ trên Σ v à
một chuỗi w bất kỳ ∈ Σ*, thì tồn tại giải thuật để xác định w có
∈ L hay không.
Chứng minh
Chúng ta biểu diễn ngôn ngữ bằng một dfa rồi kiểm tra xe m w
có được chấp nhận bởi dfa này không.
Định lý 4.6
Tồn tại giải thuật để xác định một NNCQ đã cho trong một dạng biểu diễn chuẩn có trống, hữu hạn, vô hạn hay không.
Trang145
LýthuyếtÔtômát& NNHT-Khoa CôngNghệ ThôngTin
Các định lý (tt)
Chứng minh
Chúng ta biểu diễn ngôn ngữ bằng một dfa. Nếu tồn tại m ột con
đường đi từ trạng thái khởi đầu đến một trạng thái kết thúc nào
đó thì ngôn ngữ là khác trống.
Để xác định ngôn ngữ có vô hạn không, ta tìm tất cả các đ ỉnh
mà có chu trình đi qua nó. Nếu có một đỉnh trong số này t huộc
một con đường nào đó đi từ trạng thái khởi đầu đến một tr ạng
thái kết thúc thì ngôn ngữ là vô hạn, ngược lại thì là hữu h ạn.
Trang146
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Các định lý (tt)
Định lý 4.7
Cho các biểu diễn chuẩn của hai NNCQ L1 và L2, tồn tại gi ải
thuật để xác định có hay không L1 = L2.
Chứng minh
Sử dụng L1 và L2 chúng ta xây dựng ngôn ngữ:
L3 = (L1 I L2 ) U (L1 I L2 )
Theo lý thuyết tập hợp ta có L1 = L2 khi và chỉ khi L3 = ∅. Vậy
thay vì kiểm tra L1 có bằng L2 không ta chuyển về kiểm tra L3
có bằng ∅không. Bằng tính đóng L3 là chính qui, và chúng ta có thể tìm thấy dfa M mà chấp nhận L3. Thêm vào đó chún g ta
đã có giải thuật trong Định lý 4.6 để xác định xem L3 có bằ ng trống không. Nếu L3 = ∅thì L1 = L2, ngược lại thì không.
Trang147
LýthuyếtÔtômát& NNHT-Khoa CôngNghệ ThôngTin
Nhận biết các NN không CQ
Sử dụng nguyên lý chuồng chim bồ câu
Nếu chúng ta đặt n vật thể vào trong m hộp, và nếu n > m, t hì ít
nhất có một hộp chứa nhiều hơn một vật thể.
Ngôn ngữ L = {anbn : n ≥ 0} có chính qui không?
Câu trả lời là không, như chúng ta sẽ chứng tỏ bằng cách s ử dụng phương pháp phản chứng sau.
Giả sử L là chính qui thì ∃ dfa M = (Q, {a,b}, δ, q0, F) nào đó cho L.
Xét δ*(q0, ai) với i = 0, 1, 2, 3, ... Vì có một số không giới hạn
các i, nhưng chỉ có một số hữu hạn các trạng thái trong M, theonguyên lý chuồng chim bồ câu thì phải có một trạng thái nà o đó, chẳng hạn q, sao cho
δ*(q0, an) = q và δ*(q0, am) = q, với n ≠ m.
Trang148
LýthuyếtÔtômát& NNHT-Khoa CôngNghệ ThôngTin
Nhận biết các NN không CQ
Nhưng vì M chấp nhận anbn nên ta có
δ*(q, bn) = qf ∈ F.
Kết hợp với ở trên ta suy ra
δ*(q0, ambn) = δ*(q, bn) = qf .
Vì vậy M chấp nhận cả chuỗi ambn với n ≠ m. Điều này m âu thuẫn với định nghĩa của L, suy ra L không chính qui.
Nhận xét
Trong lý luận này, nguyên lý chuồng chim bồ câu đơn giả n phát
biểu rằng một ôtômát hữu hạn có một bộ nhớ hữu hạn. Để chấp
nhận tất cả các chuỗi anbn, một ôtômát phải phân biệt giữa mọitiếp đầu ngữ an và am. Nhưng vì chỉ có một số hữu hạn cá c trạng thái nội để thực hiện điều này, nên phải có một n và mộtm nào đó mà đối với chúng ôtômát không thể phân biệt đư ợc.
Trang 149
Lýthuyết Ôtômát &NNHT-Khoa Công NghệThôngTin
Bổ đề bơm
Định lý 4.8
Cho L là một NNCQ vô hạn, thì tồn tại một số nguyên dư ơng m
nào đó sao cho ∀ w ∈ L và |w| ≥ m đều tồn tại một cách phântích w thành bộ ba
w = xyz, với |xy| ≤ m, và |y| ≥ 1, sao cho
∀ i = 0, 1, 2, ...
wi =xyiz ∈ L
Chứng minh
Nếu L là chính qui, thì ∃ một dfa chấp nhận nó. Lấy một d fa như thế có tập trạng thái Q = {q0, q1, q2, ... ,qn}. Chọn m =
|Q| =
n + 1.
Trang 150
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Chứng minh bổ đề bơm (tt)
Lấy một chuỗi w bất kỳ ∈ L và |w| = k ≥ m. Xét một
dãy các trạng thái mà ôtômát đi qua khi xử lý chu ỗi w,
giả sử là
q0, qi, qj, . . . .,qf
Vì |w| = k suy ra dãy này có k + 1 phần tử. Vì k + 1 >
n + 1 nên có ít nhất một trạng thái phải được lặp l ại, và
sự lặp lại này nằm trong n + 2 phần tử đầu tiên củ a
dãy. Vì vậy dãy trên phải có dạng
q0 , qi , qj , ... , qr , ... , qr , ... , qf
Trang151
Lý thuyếtÔtômát&NNHT -KhoaCông NghệThôngTin
Chứng minh bổ đề bơm (tt)
suy ra phải có các chuỗi con x, y, z của w sao cho δ*(q0, x) = qr ,
δ*(qr, y) = qr , δ*(qr, z) = qf ,
với |xy| ≤ n + 1 = m, vì sự lặp lại trạng thái xảy ra trong n + 2 phần tử đầu tiên, và |y| ≥ 1. Từ điều này suy ra
δ*(qr, xz) = qf , cũng như
δ*(qr, xyiz) = qf ,
∀ i = 0, 1, 2 , … Đến đây định lý được chứng minh.
Trang152
Lý thuyếtÔtômát &NNHT -Khoa CôngNghệThôngTin
Vận dụng bổ đề bơm
Sử dụng bổ đề bơm để chứng minh L = {anbn: n ≥ 0}
là
không chính qui.
Giả sử L là chính qui, dễ thấy L vô hạn. Theo bổ đề bơm tồ n tại
số nguyên dương m.
Chọn w = ambm ∈ L, |w|=2m ≥ m. Theo bổ đề bơm ∃ một cách
phân tích w thành bộ ba
w = xyz, trong đó |xy|≤ m (1), |y|= k ≥ 1 (2).
Từ cách chọn w có m kí hiệu a đi đầu, kết hợp với (1) suy r a xy
chỉ chứa a, từ đây suy ra y cũng chỉ chứa a. Vậy y = ak. Xét wi = xyiz với i = 0, ta có w0 = an - kbn ∈ L theo bổ đề bơ m,
nhưng điều này mâu thuẫn với định nghĩa của L. Vậy L là không chính qui.
Trang153
LýthuyếtÔtômát & NNHT-Khoa CôngNghệ ThôngTin
Vận dụng bổ đề bơm (tt)
Nhận xét
Lý luận này có thể được trực quan hóa như một trò chơi c húng
ta đấu với một đối thủ. Mục đích của chúng ta là thắng vá n chơi
bằng cách tạo ra một sự mâu thuẫn của bổ đề bơm, trong k hi
đối thủ thử chặn đứng chúng ta. Có bốn bước đi trong trò chơi
này như sau.
(1) Đối thủ lấy m.
(2) Với m đã cho chúng ta lấy một chuỗi w ∈ L thõa |w| ≥ m.