LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA)
Bài 03. Ngôn ngữ và Văn phạm Chính quy
Sử dụng slides của các tác giả: Hồ Văn Quân + Nick Hopper
TIN331
GV: Nguyễn Ngọc Tú Tu.NguyenNgoc@hoasen.edu.vn
Nội dung
Biểu thức chính qui (Regular Expression) Mối quan hệ giữa Biểu thức và ngôn ngữ chính qui Văn phạm chính qui (Regular Grammar)
Biểu thức chính quy
Biểu thức chính qui (BTCQ) là gì?
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.
Ví dụ
Ngôn ngữ {a} được biểu thị bởi BTCQ a. Ngôn ngữ {a, b, c} được biểu thị bởi BTCQ a + b + c. Ngược lại BTCQ (a + b.c)* biểu thị cho ngôn ngữ {λ,
a, bc, aa, abc, bca, bcbc, aaa, aabc, ...}.
Định nghĩa
Định nghĩa 3.1
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. 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).
Ví dụ
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.
Ngôn ngữ tương ứng BTCQ
Định nghĩa 3.2
Ngôn ngữ L(r) được biểu thị bởi BTCQ bất kỳ là được định
1. ∅ là BTCQ biểu thị tập trống, λ là BTCQ biểu thị {λ},
2. 3. Đối với mọi a ∈ ∑, a là BTCQ biểu thị {a}, Nếu r1 và r2 là những BTCQ, thì 1. L(r1 + r2) = L(r1) ∪ L(r2), 2. L(r1.r2) = L(r1).L(r2), 3. L((r1)) = L(r1), 4. L(r1*) = (L(r1))*.
nghĩa bởi các qui tắc sau.
Ngôn ngữ tương ứng BTCQ
Bao đóng sao > Kết nối
> Hợp
L(a* . a + b)
= L(a* . a)L(b)
= (L(a* ) L(a))L(b)
= ((L(a))* L(a))L(b)
= ({, a, aa, aaa, ...}{a}){b}
= {a, aa, aaa, ..., b} = {an n1}{b}
Ex.
Tìm ngôn ngữ của các BTCQ sau
r1 = (aa)*(bb)*b r2 = (ab*a + b)* r3 = a(a + b)* Kết quả
L(r1) = {a2nb2m+1: n ≥ 0, m ≥ 0} L(r2) = {w ∈ {a, b}*: na(w) chẵn} L(r3) = {w ∈ {a, b}*: w được bắt đầu bằng a}
Ex 02.
Tìm BTCQ cho các ngôn ngữ sau
L1 = {tập tất cả các số thực của Pascal} L2 = {w ∈ {0, 1}*: w không có một cặp số 0 liên tiếp
nào}
L3 = {w ∈ {0, 1}*: n0(w) = n1(w)}
Phép toán mở rộng
Phép chọn lựa r? hoặc [r]
r ? = [r] = (r + λ)
Phép bao đóng dương +
r+ = r.r*
Chú ý
(r*)* = r* (r1* + r2)* = (r1 + r2)* (r1r2* + r2)* = (r1 + r2)* 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
BTCQ Biểu thị Ngôn ngữ Chính quy
Định lý 3.1
Cho r là một BTCQ, thì tồn tại một NFA mà chấp nhận
L(r). Vì vậy, L(r) là NNCQ.
Bổ đề
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ó một NFA tương đương với chỉ một trạng thái kết thúc.
tương đương với
qf
qf1 qfn
λ λ
qf1 qfn
Thủ tục: re-to-nfa
Mọi nfa có thể được biểu diễn bằng sơ đồ
M
q0
q0
q1
q0
q1
a
q0
q1
qf
Thủ tục: re-to-nfa
L(r1 + r2)
hoặc
qf1 qf2
q01 q02
M(r1) M(r2) M(r1) M(r2)
Thủ tục: re-to-nfa
L(r1.r2)
M(r1)
M(r2)
qf1 qf2 q01 q02
M(r1)
M(r2)
hoặc
Thủ tục: re-to-nfa
L(r1
*)
M(r)
hoặc q0 qf q0 qf
Thủ tục: re-to-nfa
Ví dụ
L((a + bb)*(ba* + ))
a
M1
L(a + bb)
b
b
a
M2
b
L(ba* + )
Ex.
r9 = (a + -)(n)*(bv + hbv + v)(a + -)(n)* r10 = (p + -)(p + -)(n + -)(n + -)n(p + -)(p + -)s* r11 = (mc*d(c+t)*mc*d)* r12 = ((c(p + h)*)d*)*
r1 = aa* + aba*b* r2 = ab(a + ab)* (b + aa) r3 = ab*aa + bba*ab r4 = a*b(ab + b)*a* r5 = (ab* + a*b)(a + b*a)* b r6 = (b + a*)(ba* + ab)*(b*a + ab) r7 = (abb*bba + baab*a)*(bbaa + abab)*(aaa+bbb) r8 = (aabb* + bb*aa)(aa*bb* + baab)*
BTCQ cho NNCQ
Đồ thị chuyển trạng thái tổng quát (generallized
transition graphs): Là một ĐTCTT ngoại trừ các cạnh của nó được gán
nhãn bằng
các BTCQ.
Ngôn ngữ được chấp nhận bởi nó là tập tất cả các chuỗi được 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
Hình bên biểu diễn một ĐTCTTTQ.
a + b
NN được chấp nhận bởi nó là L(a*(a + b)c*) Nhận xét
ĐTCTT của một nfa bất kỳ có thể được xem là ĐTCTTTQ nếu
các nhãn cạnh được diễn dịch như sau.
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.
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 + . . .
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.
a* c*
Rút gọn trạng thái của ĐTCTTTQ
Rút gọn trạng thái trung gian q.
ae*d qi
ce*b qj
e q qi qj
a d b c ae*b ce*d
Rút gọn trạng thái của ĐTCTTTQ
Định lý 3.2
Cho L là một NNCQ, thì tồn tại một BTCQ r sao cho L
= L(r).
(a+b)a
a
a + b
b q q0 ab q0 a b
a+ b
aa (a ab
b q1 a+b a q2 q1 b +b) a a + b q2
a
Rút gọn trạng thái của ĐTCTTTQ
r1 q0
r4 qf r2 r3 r = r1*r2(r4 + r3r1*r2)* Đồ thị chuyển trạng thái
Ex.
a, b
b+ab*a a+b b b
b ab*b
a a
r = (b + ab*a)* ab*b(a + b)*
q0 q1 q2 q0 q2
BTCQ - mô tả các mẫu đơn giản
BTCQ dùng để mô tả các mẫu đơn giản
Dùng trong các ngôn ngữ lập trình
BTCQ được dùng để mô tả các token chẳng hạn như Danh hiệu Số nguyên thực …
Dùng trong các trình soạn thảo văn bản, các ứng dụng
xử lý chuỗi BTCQ được dùng để mô tả các mẫu tìm kiếm, thay thế … del tmp*.???
Văn phạm chính quy
Văn phạm tuyến tính - phải và – trái. Văn phạm tuyến tính - phải sinh ra NNCQ. Văn phạm tuyến tính - phải cho NNCQ. Sự tương đương giữa VPCQ và NNCQ.
Văn phạm tuyến tính - phải và - trái
Định nghĩa 3.3
Một văn phạm G = (V, T, S, P) được gọi là tuyến tính - phải
Một văn phạm được gọi là tuyến tính - trái (TT-T) (left-
(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 chính qui (VPCQ) là hoặc tuyến tính-phải
linear) nếu tất cả các luật sinh là có dạng A → Bx A → x
hoặc tuyến tính-trái.
Ex.
VP G1 = ({S}, {a, b}, S, P1), với P1 được cho như sau là
TT-P S → abS | a
VP G2 = ({S, S1, S2}, {a, b}, S, P2), với P2 như sau là TT-
T S → S1ab, S1 → S1ab | S2, S2 → a,
Dãy
S => abS => ababS => ababa là một dẫn xuất trong G1.
L(G1) = L((ab)*a) L(G2) = L(a(ab)*ab)
Văn phạm tuyến tính
VP G = ({S, A, B}, {a, b}, S, P), với các luật sinh
S → A, A → aB | λ, B → Ab, không phải là một VPCQ. Đây là một ví dụ của văn phạm
Văn phạm tuyến tính (Linear Grammar)
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.
tuyến tính (VPTT).
Văn phạm TT-P sinh ra NNCQ
Định lý 3.3
Cho G = (V, T, S, P) là một VPTT-P. Thì L(G) là
NNCQ.
Thủ tục: GP to nfa
Input: Văn phạm tuyến tính-phải GP = (V, T, S, P) Output: nfa M = (Q, Σ, δ, q0, F)
Văn phạm TT-P sinh ra NNCQ
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 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
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
Văn phạm TT-P sinh ra NNCQ
a1
a2
Biểu diễn Vi → a1a2 … amVj
an Vi Vj
a1 a2 an
Biểu diễn Vi → a1a2 … am
Trang 123
Vi Vf
Ex.
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
Nfa kết quả
a
b a
b
V0
V1
Vf
b
a
a
Văn phạm TT-P cho NNCQ
Định lý 3.4
Nếu L là một NNCQ trên bảng chữ cái Σ, thì ∃ một
VPTT-P
G = (V, Σ, S, P) sao cho L = L(G).
Giả thiết Q = {q0, q1, …, qn} và Σ = {a1, a2, …,
am}.
Văn phạm TT-P cho NNCQ
B1. V = Q, S = q0 (tức là mỗi trạng thái trong nfa
trở thành một biến trong văn phạm)
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 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 → λ.
Ex.
Xây dựng VPTT-P cho ngôn ngữ L(aab*a).
a
a
a
b q2
q1
q0
qf
GP: q0 → aq1 q1 → aq2 q2 → aqf | bq2 qf → λ
Sự tương đương giữa VPCQ và NNCQ
Nhận xét
Lớp VPTT-P tương đương với lớp NNCQ
Định lý 3.5
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).
Ta chứng minh mối quan hệ tương đương thông qua
VPTT-P.
Bổ đề 1
Từ VPTT-T GT đã cho ta xây dựng VPTT-P GP tương
ứng như sau
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.
Bổ đề 2
Nếu L là chính qui thì LR cũng chính qui.
Nhận xét
Lớp VPTT-T tương đương với lớp NNCQ
Định lý 3.6
Một ngôn ngữ L là chính qui nếu và chỉ nếu tồn tại một
VPCQ G sao cho L = L(G).
Ex.
Xây dựng nfa M, VPTT-T GT tương đương với
a
a
b
b
M
Y b
A b
X
a S
b
b
a
a
VPTT-P GP sau S → aS | bA A → bB | a B → aS | b
Z
B
MR
GT X → Ya | Zb Y → Ub Z → Yb U→ Ua | Za | λ GPR X → aY | bZ Y → bU Z → bY U→ aU | aZ | λ
Ngôn ngữ & Văn phạm chính quy
(Reqular Languages & Grammars) L là chính qui nếu và chỉ nếu có một DFA M sao
cho L = L(M)
Phương pháp biểu diễn phương pháp suy nghĩ
Biểu thức chính quy (Regular Expressions)
L = giá trị của E
Bảng chữ cái
, , a là các biểu thức chính qui. Nếu r1 và r2 là các biểu thức chính qui, thì r1 + r2, r1 .
r2, r1
* và (r1) cũng là các biểu thức chính qui.
Ngôn ngữ và Biểu thức chính quy
L() = {} L() = {} L(a) = {a} L(r1 + r2) = L(r1) L(r2) L(r1 . r2) = L(r1)L(r2) *) = (L(r1))* L(r1 L((r1)) = L(r1)
Ví dụ
L(a* . (a + b))
= L(a*) L(a + b)
= (L(a))* (L(a)L(b))
= {, a, aa, aaa, ...}{a, b}
= {a, aa, aaa, ..., b, ab, aab, ...}
= {an n1}{amb m0}
Độ ưu tiên toán tử (Precedence Rules)
Bao đóng sao >
Kết nối
>
Hợp
L(a* . a + b)
= L(a* . a)L(b)
= (L(a* ) L(a))L(b) = ((L(a))* L(a))L(b)
= ({, a, aa, aaa, ...}{a}){b}
= {a, aa, aaa, ..., b} = {an n1}{b}
Ví dụ
r1 = (a + b)* (a + bb)
L(r1) = ?
r2 = (aa)* (bb)* b
L(r2) = ?
Ví dụ
L(r) = {w {0, 1}* | w có ít nhất một cặp số không
liên tiếp}
r = (0 + 1)* 00 (0 + 1)*
Ví dụ
L(r) = {w {0, 1}* | w không có cặp số không liên
tiếp}
r = (1 + 01)* (0 + )
Biểu thức chính quy tương đương (≡)
r1r2 + r1r3 *)*
*r2
r1 và r2 là tương đương nếu và chỉ nếu L(r1) = L(r2) Ký hiệu: r1 r2 Một số hệ thức tương đương
r1 + r2 r2 + r1 r1(r2 + r3) (r1 + r2)* (r1 ...
Ví dụ
r1 = a . (b + c)
r2 = a . b + a . c
L(r1) = L(r2) = {ab, ac}
![Bài tập Lập trình C++: Tổng hợp [kinh nghiệm/mới nhất/chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250826/signuptrendienthoai@gmail.com/135x160/45781756259145.jpg)
