1
Chương 2
Ngôn ngữ, văn phạm và
ôtômát
2
Nội dung
Ba khái niệm cơ bản
1. Ngôn ngữ (languages)
Khái niệm ngôn ngữ
Biểu diễn ngôn ngữ
Hệ viết lại và vấn đề biểu diễn ngôn ngữ.
2. Văn phạm (grammar)
Định nghĩa văn phạm
Sự phân cấp văn phạm
3. Ôtômat (automata)
3
Tổng quan về ngôn ngữ:
Ngôn ngữ tự nhiên:tiếng Việt,tiếng Anh, …
Ngôn ngữ lập trình: Pascal, C/C++, …
ĐN ngôn ngữ trong các từ điển:
Là tập hợp các câu theo cấu trúc quy định nào đó
Biểu thị các ý nghĩ, các sự kiện hay các khái niệm
Bao gồm một tập các ký hiệu và các quy tắc để vận dụng chúng
Định nghĩa trên chưa đủ chính xác để nghiên cứu về ngôn
ngữ hình thức (ngôn ngữ dùng chung cho cả ngôn ngữ tự
nhiên lẫn ngôn ngữ lập trình). Chúng ta cần xây dựng một
định nghĩa toán học cho khái niệm về ngôn ngữ.
4
Ký hiệu, bộ chữ cái, chuỗi
•Ký hiệu (symbol):
Ví dụ: các chữ cái a,b,c,…; các chữ số 1,2,3,…
•Bộ chữ cái (alphabet hay bảng chữ cái) Σ :là một tập hợp không rỗng
các ký hiệu
Bảng chữ cái La Mã : {I, V, X, L, C, D, M}
Bảng chữ số nhị phân: {0, 1}
Bảng chữ số thập phân: {0,1,2,…,9}
Bảng chữ cái Latinh :{A, B, C, ... , Z, a, b, c, ... , z}
Bảng chữ cái Hi Lạp: {, β, γ, …,}
Qui ước:
Bộ chữ cái thường dùng Σ = {a,b,c} , Σ = {0,1}
Các kí hiệu u,v,w,x,y,z,t dùng gọi cho tên chuỗi.
2
5
Ký hiệu, bộ chữ cái, chuỗi
Chuỗi (Xâu, string) là một dãy hữu hạn các ký hiệu xếp liên tục
nhau gồm:
Các ký hiệu thuộc Σ
Mỗi ký hiệu có thể xuất hiện nhiều lần
Ví dụ: 010001 là một chuỗi trên bộ chữ cái Σ = {0, 1}
w = abbcab là một chuỗi trên bộ chữ cái Σ = {a,b,c}
Độ dài chuỗi w, ký hiệu bởi |w|, là số những ký hiệu hợp thành w.
Chẳng hạn |010001| = 6.
Chuỗi rỗng, ký hiệu (hay ), là chuỗi có độ dài 0, tức là chuỗi
không có ký hiệu nào.
Chuỗi con: Chuỗi v được gọi là chuỗi con của chuỗi w nếu v được
tạo bởi một dãy các ký hiệu kề nhau trong w.
Chẳng hạn ab, abb, bc, cb là các chuỗi con của chuỗi abbcb.
6
Ký hiệu, bộ chữ cái, chuỗi
Chuỗi tiền tố: là một chuỗi con bất kỳ nằm ở đầu chuỗi đó.
Chuỗi hậu tố:là một chuỗi con bất kỳ nằm ở cuối chuỗi đó.
Ví dụ: chuỗi abc có các tiền tố là , a, ab, abc và có các hậu tố
là , c, bc, abc.
Chuỗi nối kết (ghép): ký hiệu bởi vw, là một chuỗi được tạo
bằng cách viết v rồi viết w tiếp theo sau, không có khoảng cách.
Ví dụ: ghép Long và Int là LongInt.
Nối kết với chuỗi rỗng: εw = wε = w (w)
khi đó ε là đơn vị của phép nối kết
|uv| = |u| + |v|
|εw| = |wε| = |w|
7
Ký hiệu, bộ chữ cái, chuỗi
Đảo ngược của một chuỗi u, ký hiệu uR : là chuỗi u viết theo
thứ tự ngược lại, nghĩa là nếu:
u = a1a2…an thì uR = anan-1…a1.
Đương nhiên R = .
Phép lũy thừa: Cho w là một chuỗi
w0 =
w1 = w
w2 = ww
w3 = ww2
wn = wwn-1
8
Khái niệm về bao đóng sao và bao đóng dương
* và +: (bao đóng sao và bao đóng dương)
●* : tập hợp tất cả các chuỗi con được sinh ra từ bộ chữ cái ,
kể cả chuỗi rỗng ε.
●+ : tập hợp tất cả các chuỗi con, được sinh ra từ bộ chữ cái ,
ngoại trừ chuỗi rỗng ε.
* = + + {ε} + = * - {ε}
● = {0,1} thì:
* = {ε, 0, 1, 00, 01, 10, 11, 000, …}
+ = {0, 1, 00, 01, 10, 11, 000, …}
Chuỗi 010210 * vì có số 2
Rõ ràng Σ thì hữu hạn còn Σ* và Σ+ thì vô hạn đếm được
3
9
Ngôn ngữ (Languages)
•Một ngôn ngữ (hình thức) L là một tập con của Σ* hay nói cách khác
là một tập hợp các chuỗi của các ký hiệu được sinh ra từ bộ chữ cái
Σ.
•Ví dụ: Cho Σ = {a, b}
Σ* = {, a, b, aa, ab, ba, bb, aaa, aab, … }
•Ta có:
•L = là ngôn ngữ trên bộ chữ cái Σ tùy ý
•L = {} là ngôn ngữ trên bộ chữ cái Σ tùy ý
•L = {a, aa, aab} là một ngôn ngữ hữu hạn trên Σ = {a,b}
•L = {(ab)n | n 0 } là một ngôn ngữ vô hạn trên Σ ={a,b}
•L = {an bn | n ≥ 0 } là một ngôn ngữ vô hạn trên Σ = {a,b}
•L = {0n 1n | n ≥ 0 } là một ngôn ngữ vô hạn trên Σ = {0,1}
10
Từ các ngôn ngữ có trước, ta có thể thu được các ngôn ngữ mới nhờ áp
dụng các phép toán lên ngôn ngữ. Các phép toán trên tập hợp đều có thể
áp dụng lên các ngôn ngữ.
Phép phần bù (complement):
= * - L
Phép nối kết (concatenation):
L1L2 = {w1w2 | w1 L1 và w2 L2} trên bộ chữ cái Σ1 Σ2
L0 = {ε}
L1 = L
L2 = LL
L3=LL2
Ln = L Ln-1
Các phép toán trên ngôn ngữ
L
11
Phép bao đóng (closure): Thành lập một ngôn ngữ bằng cách kết nối
các chuỗi (với số lượng bất kỳ) các chuỗi của một ngôn ngữ L cho
trước:
Bao đóng sao của một ngôn ngữ L, ký hiệu L*
L* = L0 L1 L2 …
Trong đó Li cho bởi định nghĩa đệ quy sau:
L0 = {}
Li = LLi-1 với i 1.
Bao đóng Kleene: L* =
𝐿𝑖
∞
𝑖=0
Bao đóng dương (positive): L+ =
𝐿𝑖
∞
𝑖=1 = L1 L2 L3 … Ln
Chú ý: L* = L0 + L+
Các phép toán trên ngôn ngữ
Ví dụ: cho L = {a, ba} trên bộ chữ cái = {a,ba}
•L2 = {aa, aba, baa, baba}
•L3 = {aaa, aaba, abaa, ababa, baaa,baaba, babaa,
bababa}
•L* = {ε, a, ba, aa, aba, baa, baba, aaa, aaba, …}
•L+ = { a, ba, aa, aba, baa, baba, aaa, aaba, …}
Đôưu tiên ca php ton : (1)bao đóng, (2)ghp,
(3)hợp
12
4
13
Biểu diễn ngôn ngữ
1. Cách 1: Liệt kê chuỗi: L = {aa, aba, baa, baba}
2. Cách 2: Mô tả đặc điểm ch yếu: L = {ai | i là số nguyên tố}
3. Cách 3: Biểu diễn thông qua văn phạm và automata:
•Cho phép biểu diễn ngôn ngữ một cách tổng quát
•Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữ
VD văn phạm có tập qui tắc: P={Câu đơn Chủ ngữ Vị ngữ;
….} là cơ chế sản sinh ra mọi câu đơn của Tiếng Việt.
•Automata: cơ chế cho phép đoán nhận một chuỗi bất kỳ có
thuộc một ngôn ngữ L hay không?
14
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Ta thường biểu diễn ngôn ngữ bằng một văn phạm hay một Ôtômát. Văn
phạm hay Ôtômát gọi là hệ viết lại (written rule).
Ví dụ 1: Cho L là một ngôn ngữ trên bộ chữ ={a, b}, L định nghĩa như sau:
(1) L
(2) Nếu X L, thì aXb L.
(3) Không còn chuỗi nào khác thuộc L
Ban đầu, do (1), ta có chuỗi L. Xem là X thì do (2) ta sẽ có chuỗi ab L
tức là chuỗi ab L. Bây giờ xem ab như là X thì do (2) ta sẽ có aabb L.
Tương tự ta có aaabbb L, …cứ thế tiếp tục ta có các chuỗi aibi L (i≥0).
Trên đây cho ta một quy tắc viết lại chuỗi.
Dễ nhận thấy rằng ngôn ngữ cần tìm là L = {aibi| i = 0, 1, 2, …}
15
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Ví dụ 2: Ngôn ngữ L được định nghĩa là tập tất cả các chuỗi
có thể thu về chuỗi rỗng bằng một dãy phép thay thế các
chuỗi con ab bởi . Định nghĩa này cho ta một cách đoán
nhận một chuỗi bất kỳ có thuộc ngôn ngữ hay không.
Đoán nhận cũng là một quy tắc viết lại chuỗi. Chẳng hạn sau
đây là một quá trình đoán nhận trong đó chuỗi con ab thay
thế được gạch dưới.
aabbab
abab
ab
Như thế chuỗi aabbab là thuộc ngôn ngữ L
16
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Định nghĩa: Một hệ viết lại là một bộ đôi W = (Σ, P) trong
đó Σ là bộ chữ cái và P là tập hợp hữu hạn các cặp chuỗi
trên Σ. Một phần tử (Σ, w) của P được gọi là một quy tắc
viết lại hay một sản xuất và thường viết Σ w.
ĐN suy dẫn trực tiếp: Ta nói chuỗi x trên Σ suy dẫn trực
tiếp chuỗi y, và viết x Wy hoặc viết gọn x y khi hệ W
đã rõ, khi và chỉ khi tồn tại các chuỗi x1, Σ, x2 và w sao cho
x = x1 Σ x2, y = x1wx2, và Σ w là một sản xuất trong P.
5
17
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
ĐN suy dẫn gián tiếp: Ta nói chuỗi x suy dẫn chuỗi
y, và viết x * y,
hoặc viết gọn là x *y khi hệ W đã rõ, khi và chỉ khi
tồn tại một dãy các chuỗi trên Σ dạng x0, x1, …, xk
với k 0 sao cho x0 = x, xk = y, và xi suy dẫn trực
tiếp xi+1 đối với 0 i k-1 .
w
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Qui tắc viết gộp: Nếu trong P, ta có một loạt
các sản xuất có cùng một vế trái dạng
Σ w1
Σ w2
…
Σ wn
thì các sản xuất đó thường được viết gộp vế trái là:
Σ w1| w2| …| wn
18
19
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Các ngôn ngữ cho ở các ví dụ 1 và ví dụ 2 ở trên có
thể biểu diễn bởi hệ viết lại như sau:
Ngôn ngữ Hệ viết lại
Ví dụ 1: Cho L là một ngôn ngữ trên bộ chữ {a, b}, định
nghĩa như sau:
L
Nếu X L, thì aXb L.
Vậy L = {ai bi | i ≥ 0}
Ls(W, {X}) {a, b}*,
trong đó:
W = ({a, b, X}, {X ,
X aXb}).
Ví dụ 2: Ngôn ngữ L được định nghĩa là tập tất cả các
chuỗi có thể thu về chuỗi rỗng bằng một dãy phép thay
thế các chuỗi con ab bởi . Định nghĩa này cho ta một
cách đoán nhận một chuỗi có thuộc ngôn ngữ hay không?
Trường hợp này L không thể biểu diễn!
Lđ = (W, {}),
trong đó:
W = ({a, b}, {ab }).
20
Văn phạm là gì?
Các từ điển định nghĩa văn phạm một cách không chính xác
là một tập các qui tắc về cấu tạo từ và các qui tắc về cách
liên kết các từ lại thành câu.
Ví dụ:
Cho đoạn văn phạm tiếng Anh sau
<sentence> → <noun phrase><predicate>,
<noun phrase> → <article><noun>,
<predicate> → <verb>,
<article> → a | the,
<noun> → boy | dog,
<verb> → runs | walks,