Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức

Chương 4 Các tính chất của ngôn ngữ chính qui

(cid:132) NNCQ tổng quát là như thế nào? Có phải chăng mọi ngôn

ngữ hình thức đều là chính qui?

(cid:132) Khi chúng ta thực hiện các phép toán trên NNCQ thì kết

quả sẽ như thế nào, có còn là một NNCQ không?

(cid:132) Một ngôn ngữ nào đó có hữu hạn không? Có rỗng không? (cid:132) Làm thế nào để biết một ngôn ngữ đã cho có là chính qui

không?

Trang 130 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Chương 4 Các tính chất của ngôn ngữ chính qui

4.1 Tính đóng của ngôn ngữ chính qui. 4.2 Các câu hỏi cơ bản về ngôn ngữ chính qui.. 4.3 Nhận biết các ngôn ngữ không chính qui

Trang 131 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Tính đóng của NNCQ

(cid:132) Đóng dưới các phép toán tập hợp đơn giản. (cid:132) Định lý 4.1

(cid:132) Nếu L1 và L2 là các NNCQ, thì L1∪L2, L1∩L2 , L1L2, và L1* cũng vậy. Chúng ta nói rằng họ NNCQ là đóng dưới các phép hội, giao, kết nối, bù và bao đóng-sao.

(cid:132) Chứng minh

(cid:132) 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 BTCQ định nghĩa các ngôn ngữ L1∪L2, L1L2, và L1*. Vì vậy họ NNCQ là đóng đối với các phép toán này.

(cid:132) Để CM tính đóng đối với phép bù, cho M = (Q, Σ, δ, q0, F) là dfa chấp nhận L1, thì dfa = (Q, Σ , δ, q0, Q - F) chấp nhận . L

Trang 132 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Đóng dưới các phép toán tập hợp đơn giản

(cid:132) Để CM tính đóng đối với phép giao ta có hai cách như sau.

(cid:132) Dựa vào qui tắc De Morgan ta có

L 2

L 1

L 2 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ứ nhất

Cách thứ hai

,

lần lượt chấp nhận L1, L2. ^ ,^( QM =

)^), Fpq 0

(cid:132) Ta sẽ xây dựng một dfa cho L1 ∩ L2. (cid:132) Cho M1 = (Q, Σ, δ1, q0, F1) và M2 = (P, Σ, δ2, p0, F2) là các dfa (,^, δΣ (cid:132) Ta xây dựng dfa chấp nhận L1 ∩ L2 bằng thủ tục intersection sau.

Trang 133 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Thủ tục: intersection

(cid:132) Thủ tục: intersection

(,^, δΣ

(cid:132) Input: dfa M1 = (Q, Σ, δ1, q0, F1) và dfa M2 = (P, Σ, δ2, p0, F2) , (cid:132) Output: dfa

)^), Fpq 0

(cid:132)

^ ,^( QM = ^Q = Q × P, tức là

^Q Các chuyển trạng thái được xây dựng như sau ^δ

= {(qi, pj): trong đó qi ∈ Q còn pj ∈ P}.

((qi, pj), a) = (qk, pl)

nếu và chỉ nếu

δ1(qi, a) = qk và δ2(pj, a) = pl

Trang 134 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

= {(qi, pj): trong đó qi ∈ F1 còn pj ∈ F2}

Thủ tục: intersection (tt)

^δ

(cid:132) Cách xây dựng trên mô phỏng lại quá trình xử lý của đồng thời ^M hai dfa M1 và M2. Ngoài ra dựa vào định nghĩa của ta thấy chỉ chấp nhận những chuỗi mà được đồng thời cả hai dfa M1 và ^M M2 chấp nhận. Vì vậy chấp nhận L1 ∩ L2.

(cid:132) Ví dụ

(cid:132) Tìm dfa giao của L1={a2nbm: n, m ≥ 0} và L2={a3nb2m: n, m ≥ 0}

q1 p0

a q0 p2 a

a q0 p1 a

q0 a

q1 p1

p1 a

q1 p2 a

q2 p3

q0 p0

q2 p4

Trang 135 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

L2 L1 ∩ L2

Đóng dưới các phép toán tập hợp đơn giản (tt)

(cid:132) Định lý 4.2

(cid:132) Họ NNCQ là đóng dưới phép hiệu và nghịch đảo.

(cid:132) Chứng minh

(cid:132) Để chứng minh tính đóng đối với phép hiệu dựa vào các qui tắc

tập hợp ta có:

(cid:132) Dựa vào tính đóng của phép bù và phép giao đã được chứng

L1 - L2 = L1 ∩

(cid:132) Tính đóng của phép nghịch đảo đã được chứng minh ở Chương

minh, suy ra tính đóng cho phép hiệu.

Trang 136 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

3, slide 128.

Đóng dưới các phép toán khác

(cid:132) Phép đồng hình (homomorphism) (cid:132) Định nghĩa 4.1

(cid:132) Giả sử Σ và Γ là các bảng chữ cái, thì một hàm

(cid:132) Mở rộng nếu w = a1a2. . . an, thì

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ằng một chuỗi.

h(w) = h(a1)h(a2). . .h(an) (cid:132) Nếu L là ngôn ngữ trên Σ, thì ảnh đồng hình (homomorphic

image) của nó được định nghĩa là

Trang 137 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

h(L) = {h(w): w ∈ L}.

Ví dụ

(cid:132) Cho Σ ={a, b}, Γ ={a, b, c} và h được định nghĩa như sau h(a) = ab, h(b) = bbc.

(cid:132) Cho Σ ={a, b}, Γ ={ b, c, d } và h được định nghĩa như sau

Thì h(aba) = abbbcab. Ảnh đồng hình của L = {aa, aba} là ngôn ngữ h(L) = {abab, abbbcab}.

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)*,

Trang 138 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

là BTCQ biểu thị cho h(L). Từ đó dẫn ta tới định lý sau

Định lý

(cid:132) Định lý 4.3

(cid:132) Cho h là một đồng hình. Nếu L là một NNCQ, thì ảnh đồng

(cid:132) Phép thương đúng (cid:132) Định nghĩa 4.2

(cid:132) Cho w, v ∈ Σ* thì thương đúng (right quotient) của w cho v

hình của nó h(L) cũng là NNCQ. Họ các NNCQ vì vậy là đóng dưới phép đồng hình bất kỳ.

đượ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. (cid:132) Cho L1 và L2 là các ngôn ngữ trên bảng chữ cái giống nhau, thì

thương đúng của L1 với L2 được định nghĩa là

L1/L2 = {w/v: w ∈ L1, v ∈ L2 }

Trang 139 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

= {x : xy ∈ L1 với một y nào đó ∈ L2 }

Ví dụ

(cid:132) Cho L1 = {anbm: n ≥ 1, m ≥ 0} ∪ {ba} và L2 = {bm: m ≥ 1}, thì

(cid:132) Vì L1, L2, và L1 /L2 là các NNCQ , điều này gợi ý cho chúng ta

L1 /L2 = { anbm: n ≥ 1, m ≥ 0}.

(cid:132) Bổ đề

(cid:132) 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 những trạng thái q có tính chất này thì ta sẽ có một dfa mà chấp nhận L1/L2.

Trang 140 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

rằng thương đúng của hai NNCQ cũng là NNCQ.

Định lý

x y

q M1 q0 qf

*(q0, x) = q

∀x mà δ1

thì x ∈ L1/L2 y

(cid:132) Nếu L1 và L2 là các NNCQ, thì L1/L2 cũng chính qui. Chúng ta

M2 p0 (cid:132) Định lý 4.4

(cid:132) Chứng minh

(cid:132) Cho L1 = L(M) trong đó M = (Q, Σ, δ, q0, F) là một dfa. Ta xây dựng một dfa khác =( Q, Σ, δ, q0, ), 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ông Tin

nói rằng họ NNCQ là đóng dưới phép thương đúng.

Thủ tục: right quotient

(cid:132) Thủ tục: right quotient

(cid:132) Input: dfa M1 = (Q, Σ, δ1, q0, F1) và dfa M2 = (P, Σ, δ2, p0, F2) ^M ^F (cid:132) Output: dfa = (Q, Σ, δ1, q0, ^F (cid:132) Ta xác định bằng cách xác định với mỗi qi ∈ Q, có tồn tại

)

(cid:132) Đ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 có tính chất đã nói ở trên và thêm qi vào . Thực hiện điều này ^M ^F ∀ qi ∈ Q, ta sẽ xác định được và vì vậy xây dựng được .

Trang 142 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

hay không chuỗi y ∈ L2 sao cho δ*(qi, y) ∈ F. Nếu đúng thì đưa ^F qi vào .

Ví dụ

(cid:132) Tìm L1/L2 cho

a L1 = L(a*baa*), L2 = L(ab*). a a a

L1/L2 M1 b a a b

q2 q0 q0 q1 q2 q1

M2 a

Trang 143 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

p1 p0

Các câu hỏi cơ bản về NNCQ

(cid:132) Cho một ngôn ngữ L và một chuỗi w, chúng ta có thể xác định

(cid:132) Đâ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.

(cid:132) Một ngôn ngữ đã cho là hữu hạn hay vô hạn? (cid:132) Hai ngôn ngữ nào đó có giống nhau không? (cid:132) Có hay không một ngôn ngữ là tập con của một ngôn ngữ khác?

(cid:132) Biểu diễn chuẩn (Standard representation)

(cid:132) 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ạng sau đây: một ôtômát hữu hạn, một BTCQ hoặc một VPCQ.

(cid:132) 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ông Tin

được w có phải là một phần tử của L hay không?

Các định lý

(cid:132) Định lý 4.5

(cid:132) Cho một biểu diễn chuẩn của một NNCQ L bất kỳ trên Σ và

(cid:132) Chứng minh

(cid:132) Chúng ta biểu diễn ngôn ngữ bằng một dfa rồi kiểm tra xem w

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.

(cid:132) Định lý 4.6

(cid:132) 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.

Trang 145 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

có được chấp nhận bởi dfa này không.

Các định lý (tt)

(cid:132) Chứng minh

(cid:132) 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.

(cid:132) Để xác định ngôn ngữ có vô hạn không, ta tìm tất cả các đỉnh

Trang 146 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

mà có chu trình đi qua nó. Nếu có một đỉnh trong số này thuộ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.

Các định lý (tt)

(cid:132) Định lý 4.7

(cid:132) Cho các biểu diễn chuẩn của hai NNCQ L1 và L2, tồn tại giải

(cid:132) Chứng minh

(

)

(

)

(cid:132) Sử dụng L1 và L2 chúng ta xây dựng ngôn ngữ: =

L 1

L 3

L 2

L 2 (cid:132) 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úng 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.

Trang 147 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

thuật để xác định có hay không L1 = L2.

Nhận biết các NN không CQ

(cid:132) Sử dụng nguyên lý chuồng chim bồ câu

(cid:132) Nếu chúng ta đặt n vật thể vào trong m hộp, và nếu n > m, thì ít

(cid:132) Câu trả lời là không, như chúng ta sẽ chứng tỏ bằng cách sử

nhất có một hộp chứa nhiều hơn một vật thể. (cid:132) Ngôn ngữ L = {anbn : n ≥ 0} có chính qui không?

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, theo nguyê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

Trang 148 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

δ*(q0, an) = q và δ*(q0, am) = q, với n ≠ m.

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 .

(cid:132) Nhận xét

(cid:132) 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ọi tiế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ột m 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ông Tin

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.

Bổ đề bơm

(cid:132) Định lý 4.8

(cid:132) 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ân tích w thành bộ ba

w = xyz,

với |xy| ≤ m, và |y| ≥ 1, sao cho

wi =xyiz ∈ L

(cid:132) Chứng minh

(cid:132) Nếu L là chính qui, thì ∃ một dfa chấp nhận nó. Lấy một dfa

∀ i = 0, 1, 2, ...

Trang 150 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

như thế có tập trạng thái Q = {q0, q1, q2, ... ,qn}. Chọn m = |Q| = n + 1.

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

Trang 151 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

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 ,

Trang 152 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

∀ i = 0, 1, 2 , … Đến đây định lý được chứng minh.

Vận dụng bổ đề bơm

(cid:132) Sử dụng bổ đề bơm để chứng minh L = {anbn: n ≥ 0} là

không chính qui.

(cid:132) Giả sử L là chính qui, dễ thấy L vô hạn. Theo bổ đề bơm tồn tại

(cid:132) Chọn w = ambm ∈ L, |w|=2m ≥ m. Theo bổ đề bơm ∃ một cách

số nguyên dương m.

phân tích w thành bộ ba

(cid:132) Từ cách chọn w có m kí hiệu a đi đầu, kết hợp với (1) suy ra xy

w = xyz, trong đó |xy|≤ m (1), |y|= k ≥ 1 (2).

(cid:132) 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.

Trang 153 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

chỉ chứa a, từ đây suy ra y cũng chỉ chứa a. Vậy y = ak.

Vận dụng bổ đề bơm (tt)

(cid:132) Nhận xét

(cid:132) Lý luận này có thể được trực quan hóa như một trò chơi chú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 khi đố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. (3) Đối thủ chọn phân hoạch xyz, thõa |xy| ≤ m, |y| ≥ 1. Chúng ta phải giả thiết rằng đối thủ chọn lựa làm sao cho chúng ta khó thắng ván chơi nhất.

Trang 154 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

(4) Chúng ta chọn i sao cho chuỗi được bơm lên ∉ L.

Vận dụng bổ đề bơm (tt)

(cid:132) Bước quyết định ở đây là bước (2). Trong khi chúng ta không thể ép buộc đối thủ lấy một phân hoạch cụ thể của chuỗi w, chúng ta có thể chọn chuỗi w sao cho đối thủ bị hạn chế nghiêm ngặt trong bước (3), ép buộc một sự chọn lựa của x, y, z sao cho cho phép chúng ta tạo ra một mâu thuẫn với bổ đề bơm trên bước kế tiếp của chúng ta.

(cid:132) Ví dụ

Trang 155 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Chứng minh các ngôn ngữ sau là không chính qui. (cid:132) L1 = {wwR: w ∈ {a, b}*} (cid:132) L2 = {anbl: n ≠ l}