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

Chương 3 Ngôn ngữ chính qui và văn phạm chính qui

3.1 Biểu thức chính qui (Regular Expression) 3.2 Mối quan hệ giữa BTCQ và ngôn ngữ chính qui 3.3 Văn phạm chính qui (Regular Grammar)

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

Biểu thức chính qui

(cid:132) Biểu thức chính qui (BTCQ) là gì?

(cid:132) Là một sự kết hợp các chuỗi kí hiệu của một bảng chữ cái ∑ nào đó, các dấu ngoặc, và các phép toán +, ., và *. trong đó phép + biểu thị cho phép hội, phép . biểu thị cho phép kết nối, phép * biểu thị cho phép bao đóng sao.

(cid:132) Ví dụ

(cid:132) Ngôn ngữ {a} được biểu thị bởi BTCQ a. (cid:132) Ngôn ngữ {a, b, c} được biểu thị bởi BTCQ a + b + c. (cid:132) Ngược lại BTCQ (a + b.c)* biểu thị cho ngôn ngữ {λ, a, bc, aa,

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

abc, bca, bcbc, aaa, aabc, ...}.

Định nghĩa hình thức BTCQ

(cid:132) Định nghĩa 3.1

(cid:132) Cho ∑ là một bảng chữ cái, thì 1. ∅, λ, và a ∈ ∑ tất cả đều là những BTCQ hơn nữa chúng được

gọi là những BTCQ nguyên thủy.

2. Nếu r1 và r2 là những BTCQ, thì r1 + r2, r1. r2, r1*, và (r1) cũng

vậy.

(cid:132) Ví dụ

(cid:132) Cho ∑ = {a, b, c}, thì chuỗi (a + b.c)*.(c + ∅) là BTCQ, vì nó được xây dựng bằng cách áp dụng các qui tắc ở trên. Còn (a + b +) không phải là BTCQ.

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

3. Một chuỗi là một BTCQ nếu và chỉ nếu nó có thể được dẫn xuất từ các BTCQ nguyên thủy bằng một số lần hữu hạn áp dụng các quy tắc trong (2).

Ngôn ngữ tương ứng với BTCQ

(cid:132) Định nghĩa 3.2

(cid:132) Ngôn ngữ L(r) được biểu thị bởi BTCQ bất kỳ là được định

nghĩa bởi các qui tắc sau.

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

1. ∅ là BTCQ biểu thị tập trống, 2. λ là BTCQ biểu thị {λ}, 3. Đối với mọi a ∈ ∑, a là BTCQ biểu thị {a}, Nếu r1 và r2 là những BTCQ, thì 4. L(r1 + r2) = L(r1) ∪ L(r2), 5. L(r1.r2) = L(r1).L(r2), 6. L((r1)) = L(r1), 7. L(r1*) = (L(r1))*.

Ngôn ngữ tương ứng với BTCQ (tt)

(cid:132) Qui định về độ ưu tiên

(cid:132) Độ ưu tiên của các phép toán theo thứ tự từ cao đến thấp là

(cid:132) Ví dụ

(cid:132) L(a* . (a + b)) = L(a*) L(a + b)

1. bao đóng – sao, 2. kết nối, 3. hội.

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

= (L(a))* (L(a) ∪ L(b)) = {λ, a, aa, aaa, . . .}{a, b} = {a, aa, aaa, . . . , b, ab, aab, . . .}

Xác định ngôn ngữ cho BTCQ

(cid:132) Tìm ngôn ngữ của các BTCQ sau

(cid:132) r1 = (aa)*(bb)*b (cid:132) r2 = (ab*a + b)* (cid:132) r3 = a(a + b)*

(cid:132) Kết quả

(cid:132) L(r1) = {a2nb2m+1: n ≥ 0, m ≥ 0} (cid:132) L(r2) = {w ∈ {a, b}*: na(w) chẵn} (cid:132) L(r3) = {w ∈ {a, b}*: w được bắt đầu bằng a}

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

Tìm BTCQ cho ngôn ngữ

(cid:132) Tìm BTCQ cho các ngôn ngữ sau

(cid:132) L1 = {tập tất cả các số thực của Pascal} (cid:132) L2 = {w ∈ {0, 1}*: w không có một cặp số 0 liên tiếp nào} (cid:132) L3 = {w ∈ {0, 1}*: n0(w) = n1(w)}

(cid:132) Kết quả

(cid:132) r1 = (‘+’ + ‘-’ + λ)(0 + 1 + … + 9)+(‘.’ (0 + 1 + … + 9)+ + λ)

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

(‘E’ (‘+’ + ‘-’ + λ)(0 + 1 + … + 9)+ + λ) (cid:132) r2 = [(1* 011*)* + 1*] (0 + λ) hoặc (1 + 01)* (0 + λ) (cid:132) Không tồn tại BTCQ biểu diễn cho L3

Một số phép toán mở rộng

(cid:132) Phép chọn lựa r? hoặc [r]

(cid:132) Phép bao đóng dương +

r ? = [r] = (r + λ)

(cid:132) Chú ý

(cid:132) (r*)* = r* (cid:132) (r1* + r2)* = (r1 + r2)* (cid:132) (r1r2* + r2)* = (r1 + r2)* (cid:132) Trong một số tài liệu phép cộng (+) được kí hiệu bằng dấu | thay cho dấu + . Chẳng hạn (a + b).c thì được viết là (a | b).c

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

r+ = r.r*

BTCQ biểu thị NNCQ

(cid:132) Định lý 3.1

(cid:132) Cho r là một BTCQ, thì tồn tại một nfa mà chấp nhận L(r). Vì

(cid:132) Bổ đề

(cid:132) Với mọi nfa có nhiều hơn một trạng thái kết thúc luôn luôn có

vậy, L(r) là NNCQ.

một nfa tương đương với chỉ một trạng thái kết thúc.

qf1 qf1 λ

tương đương với qf

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

λ qfn qfn

Thủ tục: re-to-nfa

(cid:132) Từ bổ đề trên mọi nfa có thể được biểu diễn bằng sơ đồ

qf q0

như sau (cid:132) Chứng minh (cid:132) Thủ tục: re-to-nfa

(cid:132) Input: Biểu thức chính qui r. (cid:132) Output: nfa M = (Q, Σ, δ, q0, F).

B1. Xây dựng các nfa cho các BTCQ nguyên thủy

a λ

q0 q0 q1 q1 q0 q1

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

(a) nfa chấp nhận ∅ (b) nfa chấp nhận {λ} (c) nfa chấp nhận {a}

Thủ tục: re-to-nfa (tt)

B2. Xây dựng các nfa cho các BTCQ phức tạp

(cid:132) nfa cho BTCQ r1 + r2

M(r1)

qf1 q01 M(r1) λ λ

hoặc

M(r2) λ λ M(r2) qf2 q02

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

ĐK: 1. Không có cạnh đi vào q01 và q02 2. Không có cạnh đi ra qf1 và qf2

Thủ tục: re-to-nfa (tt)

(cid:132) nfa cho BTCQ r1r2

M(r1)

M(r2)

qf1 qf2 q01 q02

M(r1)

M(r2)

hoặc

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

ĐK: 1. Không có cạnh đi ra qf1 hoặc 2. Không có cạnh đi vào q02

Thủ tục: re-to-nfa (tt)

(cid:132) nfa cho BTCQ r*

M(r)

hoặc q0≡ qf q0 qf

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

ĐK: 1. Không có cạnh đi vào q0 2. Không có cạnh đi ra qf

Ví dụ

(cid:132) Xây dựng nfa cho BTCQ sau

r = (a + bb)(ba + λ)

λ a

a a

λ b Hoặc theo phương pháp cải tiến

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

b λ b

Bài tập BTCQ

(cid:132) Xây dựng nfa cho các BTCQ sau

(cid:132) r1 = aa* + aba*b* (cid:132) r2 = ab(a + ab)* (b + aa) (cid:132) r3 = ab*aa + bba*ab (cid:132) r4 = a*b(ab + b)*a* (cid:132) r5 = (ab* + a*b)(a + b*a)* b (cid:132) r6 = (b + a*)(ba* + ab)*(b*a + ab)

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

BTCQ cho NNCQ

(cid:132) Đồ thị chuyển trạng thái tổng quát (generallized transition

graphs):

(cid:132) Là một ĐTCTT ngoại trừ các cạnh của nó được gán nhãn bằng

(cid:132) Ngôn ngữ được chấp nhận bởi nó là tập tất cả các chuỗi được

các BTCQ.

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

sinh ra bởi các BTCQ mà là nhãn của 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 nào đó của ĐTCTT tổng quát (ĐTCTTTQ).

Đồ thị chuyển trạng thái tổng quát

(cid:132) Hình bên biểu diễn một ĐTCTTTQ.

a* c*

(cid:132) NN được chấp nhận bởi nó là L(a*(a + b)c*)

(cid:132) Nhận xét

(cid:132) ĐTCTT của một nfa bất kỳ có thể được xem là ĐTTCTTTQ

a + b

(cid:132) Một cạnh được gán nhãn là một kí hiệu đơn a được diễn dịch thành cạnh

được gán nhãn là biểu thức a.

(cid:132) Một cạnh được gán nhãn với nhiều kí hiệu a, b, . . . thì được diễn dịch

thành cạnh được gán nhãn là biểu thức a + b + . . .

(cid:132) Mọi NNCQ đều ∃ một ĐTCTTTQ chấp nhận nó. Ngược lại, mỗi NN mà được chấp nhận bởi một ĐTCTTTQ là chính qui.

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

nếu các nhãn cạnh được diễn dịch như sau.

Rút gọn trạng thái của ĐTCTTTQ

(cid:132) Để tìm BTCQ cho một ĐTCTTTQ ta sẽ thực hiện quá trình rút gọn các trạng thái trung gian của nó thành ĐTCTTTQ tương đương đơn giản nhất có thể được.

(cid:132) Trạng thái trung gian

(cid:132) Là trạng thái mà không phải là trạng thái khởi đầu, cũng không

phải là trạng thái kết thúc.

ce*b e ae*d

Rút gọn trạng thái trung gian q. ae*b b a

q qi qj qi qj

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

d c ce*d

Định lý

(cid:132) Rút gọn trạng thái q của ĐTCTT sau

(a+b)a

)

ab q1 q1

+

a a a + b

(

a + b

a a + b

b q q0 q0 a b

b q2 q2

(cid:132) Định lý 3.2

(cid:132) Cho L là một NNCQ, thì tồn tại một BTCQ r sao cho L = L(r).

r4 r1

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

qf r = r1*r2(r4 + r3r1*r2)* r2 r3 q0 Đồ thị chuyển trạng thái

Ví dụ

(cid:132) Xác định BTCQ cho nfa sau

a, b b+ab*a a+b b b

b ab*b

q0 q1 q2 q0 q2

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

r = (b + ab*a)* ab*b(a + b)*

BTCQ dùng để mô tả các mẫu đơn giản

(cid:132) Dùng trong các ngôn ngữ lập trình

(cid:132) BTCQ được dùng để mô tả các token chẳng hạn như

(cid:132) Danh hiệu (cid:132) Số nguyên thực (cid:132) …

(cid:132) Dùng trong các trình soạn thảo văn bản, các ứng dụng xử

lý chuỗi

(cid:132) BTCQ được dùng để mô tả các mẫu tìm kiếm, thay thế …

(cid:132) del tmp*.???

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

Văn phạm chính qui

(cid:132) Văn phạm tuyến tính - phải và – trái. (cid:132) Văn phạm tuyến tính - phải sinh ra NNCQ. (cid:132) Văn phạm tuyến tính - phải cho NNCQ. (cid:132) Sự tương đương giữa VPCQ và NNCQ.

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

Văn phạm tuyến tính - phải và - trái

(cid:132) Định nghĩa 3.3

(cid:132) Một văn phạm G = (V, T, S, P) được gọi là tuyến tính - phải

(TT-P) (right-linear) nếu tất cả luật sinh là có dạng

A → xB A → x

trong đó A, B ∈ V, x ∈ T*. Một văn phạm được gọi là tuyến tính - trái (TT-T) (left-linear) nếu tất cả các luật sinh là có dạng

(cid:132) Một văn phạm chính qui (VPCQ) là hoặc tuyến tính-phải hoặc

A → Bx A → x

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

tuyến tính-trái.

Ví dụ

(cid:132) VP G1 = ({S}, {a, b}, S, P1), với P1 được cho như sau là TT-P S → abS | a (cid:132) VP G2 = ({S, S1, S2}, {a, b}, S, P2), với P2 như sau là TT-T S → S1ab, S1 → S1ab | S2, S2 → a,

(cid:132) Dãy

S => abS => ababS => ababa

là một dẫn xuất trong G1.

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

L(G1) = L((ab)*a) L(G2) = L(a(ab)*ab)

Văn phạm tuyến tính

(cid:132) VP G = ({S, A, B}, {a, b}, S, P), với các luật sinh

S → A, A → aB | λ, B → Ab,

(cid:132) Văn phạm tuyến tính (Linear Grammar)

(cid:132) Một văn phạm được gọi là tuyến tính nếu mọi luật sinh của nó có dạng có tối đa một biến xuất hiện ở vế phải của luật sinh và không có sự giới hạn nào trên vị trí xuất hiện của biến này.

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

không phải là một VPCQ. Đây là một ví dụ của văn phạm tuyến tính (VPTT).

Văn phạm TT-P sinh ra NNCQ

(cid:132) Định lý 3.3

(cid:132) Cho G = (V, T, S, P) là một VPTT-P. Thì L(G) là NNCQ.

(cid:132) Chứng minh (cid:132) Thủ tục: GP to nfa

(cid:132) Input: Văn phạm tuyến tính-phải GP = (V, T, S, P) (cid:132) Output: nfa M = (Q, Σ, δ, q0, F)

B1. Ứng với mỗi biến Vi của văn phạm ta xây dựng một trạng thái

mang nhãn Vi cho nfa tức là: Q ⊃ V.

B2. Ứng với biến khởi đầu V0, trạng thái V0 của nfa sẽ trở thành trạng

thái khởi đầu, tức là: S = V0

B3. Nếu trong văn phạm có một luật sinh nào đó dạng Vi → a1a2…am

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

thì thêm vào nfa một và chỉ một trạng thái kết thúc Vf.

Văn phạm TT-P sinh ra NNCQ (tt)

B4. Ứng với mỗi luật sinh của văn phạm có dạng

Vi → a1a2…amVj

thêm vào nfa các chuyển trạng thái

δ*(Vi, a1a2…am) = Vj

B5. Ứng với mỗi luật sinh dạng

Vi → a1a2…am

thêm vào nfa các chuyển trạng thái

δ*(Vi, a1a2…am) = Vf

a1 a2 an

Vi Vj Biểu diễn Vi → a1a2 … amVj

a1 a2 an

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

Vi Vf Biểu diễn Vi → a1a2 … am

Ví dụ

(cid:132) Xây dựng một nfa chấp nhận ngôn ngữ của văn phạm sau: V0 → aV1 | ba V1 → aV1 | abV0 | b

(cid:132) Nfa kết quả

b a

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

Văn phạm TT-P cho NNCQ

(cid:132) Định lý 3.4

(cid:132) Nếu L là một NNCQ trên bảng chữ cái Σ, thì ∃ một VPTT-P

(cid:132) Chứng minh (cid:132) Thủ tục: nfa to GP

(cid:132) Input: nfa M = (Q, Σ, δ, q0, F) (cid:132) Output: Văn phạm tuyến tính-phải GP = (V, Σ, S, P) (cid:132) Giả thiết Q = {q0, q1, …, qn} và Σ = {a1, a2, …, am}.

G = (V, Σ, S, P) sao cho L = L(G).

B1. V = Q, S = q0 (tức là mỗi trạng thái trong nfa trở thành một biến

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

trong văn phạm)

Thủ tục: nfa to GP

B2. Với mỗi chuyển trạng thái δ(qi, aj) = qk của M ta xây dựng luật

sinh TT-P tương ứng

(cid:132) Xây dựng VPTT-P cho ngôn ngữ L(aab*a).

qi → ajqk. B3. Đối với mỗi trạng thái qf ∈ F chúng ta xây dựng luật sinh qf → λ. (cid:132) Ví dụ

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

GP: q0 → aq1 q1 → aq2 q2 → aqf | bq2 qf → λ

Sự tương đương giữa VPCQ và NNCQ

(cid:132) Nhận xét

(cid:132) Lớp VPTT-P tương đương với lớp NNCQ

(cid:132) Định lý 3.5

(cid:132) Ngôn ngữ L là chính qui nếu và chỉ nếu tồn tại một

VPTT-T G sao cho L = L(G).

(cid:132) Ta chứng minh mối quan hệ tương đương thông qua

VPTT-P.

(cid:132) Bổ đề 1

(cid:132) Từ VPTT-T GT đã cho ta xây dựng VPTT-P GP tương ứng như

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

Sự tương đương giữa VPCQ và NNCQ

1. Ứng với luật sinh TT-T A → Bv ta xây dựng luật sinh TT-P A → vRB. 2. Ứng với luật sinh TT-T A → v ta xây dựng luật sinh TT-P A → vR. (cid:132) GP được xây dựng theo cách trên có quan hệ với GT như sau

(cid:132) Bổ đề 2

(cid:132) Nếu L là chính qui thì LR cũng chính qui.

(cid:132) Nhận xét

(cid:132) Lớp VPTT-T tương đương với lớp NNCQ

(cid:132) Định lý 3.6

(cid:132) Một ngôn ngữ L là chính qui nếu và chỉ nếu tồn tại một VPCQ

L(GT) = L(GP)R

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

G sao cho L = L(G).