Giáo trình Tin học lý thuyết - Chương 2: Ngôn ngữ và biểu diễn ngôn ngữ

. Bằng cách ấn định các dạng khác 
nhau vào các quy tắc phát sinh, người ta cũng định nghĩa nhiều loại văn phạm và ôtômát 
khác nhau, từ đơn giản đến phức tạp, nghiên cứu các ngôn ngữ sản sinh hay đoán nhận bởi 
chúng và mối liên quan giữa chúng với nhau. 
III. VĂN PHẠM VÀ SỰ PHÂN LỚP VĂN PHẠM 
Với mục đích sản sinh (hay đoán nhận) ngôn ngữ, văn phạm được dùng như một cách 
thức hiệu quả để biểu diễn ngôn ngữ. 
3.1. Định nghĩa văn phạm cấu trúc (Grammar) 
Theo từ điển, văn phạm, một cách không chính xác, là một tập các quy tắc về cấu tạo 
từ và các quy tắc về cách thức liên kết từ lại thành câu. 
Để hiểu rõ hơn khái niệm này, ta xét ví dụ cây minh họa cấu trúc cú pháp của một câu 
đơn trong ngôn ngữ tiếng Việt "An là sinh viên giỏi" ở thí dụ 1.5 của chương 1. Xuất 
phát từ nút gốc theo dần đến nút lá, ta nhận thấy các từ ở những nút lá của cây như 
“An”, “sinh viên”, “giỏi”, … là những từ tạo thành câu được sản sinh. Ta gọi đó là các 
ký hiệu kết thúc bởi vì chúng không còn phát sinh thêm nút nào trên cây và câu 
được hoàn thành. Trái lại, các nút trong của cây như “câu đơn”, “chủ ngữ”, “danh 
từ”, … sẽ không có mặt trong dạng câu sản sinh, chúng chỉ giữ vai trò trung gian 
trong việc sinh chuỗi, dùng diễn tả cấu trúc câu. Ta gọi đó là các ký hiệu chưa kết 
thúc. 
Quá trình sản sinh câu như trên thực chất là sự diễn tả thông qua cấu trúc cây cho một 
quá trình phát sinh chuỗi. Các chuỗi được phát sinh bắt đầu từ một ký hiệu chưa kết 
thúc đặc biệt, sau mỗi bước thay thế một ký hiệu chưa kết thúc nào đó trong chuỗi 
thành một chuỗi lẫn lộn gồm các ký hiệu kết thúc và chưa, cho đến khi không còn 
một ký hiệu chưa kết thúc nào nữa thì hoàn thành. Quá trình này chính là phương 
thức phát sinh chuỗi của một văn phạm, được định nghĩa hình thức như sau: 
 14 
Chương II : Ngôn ngữ và biểu diễn ngôn ngữ 
Định nghĩa : Văn phạm cấu trúc G là một hệ thống gồm bốn thành phần xác định 
như sau G (V, T, P, S), trong đó: 
. V : tập hợp các biến (variables) hay các ký hiệu chưa kết thúc (non terminal) 
. T : tập hợp các ký hiệu kết thúc (terminal) (với V ∩ T = ∅) 
. P : tập hữu hạn các quy tắc ngữ pháp được gọi là các luật sinh (production), 
mỗi luật sinh được biểu diễn dưới dạng α → β, với α, β là các chuỗi ∈ (V ∪ T)*. 
. S ⊂ V: ký hiệu chưa kết thúc dùng làm ký hiệu bắt đầu (start) 
Người ta thường dùng các chữ cái Latinh viết hoa (A, B, C, ...) để chỉ các ký hiệu 
trong tập biến V; các chữ cái Latinh đầu bảng viết thường (a, b, c, ...) dùng chỉ các ký 
hiệu kết thúc thuộc tập T. Chuỗi các ký hiệu kết thúc thường được biểu diễn bằng các 
chữ cái Latinh cuối bảng viết thường (x, y, z, ...). 
Nhận xét : Bằng quy ước này chúng ta có thể suy ra các biến, các ký hiệu kết thúc và 
ký hiệu bắt đầu của văn phạm một cách xác định và duy nhất bằng cách xem xét các 
luật sinh. Vì vậy, để biểu diễn văn phạm, một cách đơn giản người ta chỉ cần liệt kê 
tập luật sinh của chúng. 
Từ văn phạm, để sinh ra được các câu (từ), ta định nghĩa khái niệm “dẫn xuất” như 
sau : 
Nếu α → β là một luật sinh thì γ α δ ⇒ γ β δ gọi là một dẫn xuất trực tiếp, có nghĩa 
là áp dụng luật sinh α → β vào chuỗi γ α δ để sinh ra chuỗi γ β δ. 
Nếu các chuỗi α1, α2, ...., αm ∈ Σ* và α1 ⇒ α2, α2 ⇒ α3, ..., αm-1 ⇒ αm thì ta nói αm có 
thể được dẫn ra từ α1 thông qua chuỗi dẫn xuất α1 ⇒ α2, α2 ⇒ α3, ..., αm-1 ⇒ αm hay 
α1 dẫn xuất (gián tiếp) ra αm, viết tắt là α1 ⇒* αm. 
Ngôn ngữ của văn phạm G (V, T, P, S) là tập hợp các chuỗi ký hiệu kết thúc w ∈ T* 
được sinh ra từ ký hiệu bắt đầu S của văn phạm bởi các luật sinh thuộc tập P, ký hiệu 
là L(G) : 
L (G) = {w | w ∈ T * và S ⇒* w} 
Một ngôn ngữ có thể có nhiều cách đặc tả, do đó cũng có thể có nhiều văn phạm khác 
nhau sinh ra cùng một ngôn ngữ. Hai văn phạm sinh ra cùng một ngôn ngữ thì gọi là 
tương đương. 
G1 tương đương G2 ⇔ L (G1) = L (G2) 
3.2. Sự phân cấp Chomsky trên văn phạm 
Bằng cách áp đặt một số quy tắc hạn chế trên các luật sinh, Noam Chomsky đề nghị 
một hệ thống phân loại các văn phạm dựa vào tính chất của các luật sinh. Hệ thống 
này cho phép xây dựng các bộ nhận dạng hiệu quả và tương thích với từng lớp văn 
phạm. Ta có 4 lớp văn phạm như sau : 
 15
Chương II : Ngôn ngữ và biểu diễn ngôn ngữ 
1) Văn phạm loại 0: Một văn phạm không cần thỏa ràng buộc nào trên tập các luật 
sinh được gọi là văn phạm loại 0 hay còn được gọi là văn phạm không hạn chế 
(Unrestricted Grammar) 
2) Văn phạm loại 1: Nếu văn phạm G có các luật sinh dạng α → β và thỏa 
⏐β⏐≥⏐α⏐ thì G là văn phạm loại 1 hoặc còn được gọi là văn phạm cảm ngữ cảnh 
CSG (Context-Sensitive Grammar) 
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ cảm ngữ cảnh (CSL) 
3) Văn phạm loại 2: Nếu văn phạm G có các luật sinh dạng A → α với A là một biến 
đơn và α là một chuỗi các ký hiệu ∈ (V ∪T)* thì G là văn phạm loại 2 hoặc còn được 
gọi là văn phạm phi ngữ cảnh CFG (Context-Free Grammar) 
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ phi ngữ cảnh (CFL) 
4) Văn phạm loại 3: Nếu văn phạm G có mọi luật sinh dạng tuyến tính phải (right-
linear): A → wB hoặc A → w với A, B là các biến đơn và w là chuỗi ký hiệu kết thúc 
(có thể rỗng); hoặc có dạng tuyến tính trái (left-linear): A → Bw hoặc A → w thì G 
là văn phạm loại 3 hay còn được gọi là văn phạm chính quy RG (Regular Grammar) 
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ chính quy (RL) 
Ký hiệu : L0, L1, L2, L3 là các lớp ngôn ngữ sinh ra bởi các văn phạm loại 0, 1, 2, 3 
tương ứng. Ta có : L3 ⊂ L2 ⊂ L1 ⊂ L0 và các bao hàm thức này là nghiêm ngặt. 
Thí dụ 2.5 : 
1. Xét văn phạm G : 
V = {S, A}, T = {a, b} và tập P = { S → aS 
 S → aA 
 A → bA 
 A → b } 
 Đây là văn phạm loại 3 (vì tập luật sinh có dạng tuyến tính phải). 
 Chẳng hạn, một dẫn xuất từ S có dạng : 
S ⇒ aS ⇒ aaS ⇒ aaaA ⇒ aaabA ⇒ aaabbA ⇒ aaabbbA ⇒ aaabbbb = a3 b4
Hay văn phạm sinh ra ngôn ngữ L(G3) = {a+b+} = {anbm ⎪n, m ≥ 1 } 
2. Xét văn phạm G : 
 V = {S}, T = {a, b} và tập P = { S → aSb 
 S → ab } 
 Đây là văn phạm loại 2. 
 Chẳng hạn, một dẫn xuất từ S có dạng : 
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaabbbb = a4b4
Hay văn phạm sinh ra ngôn ngữ L(G2) = {anbn ⎪n ≥ 1} 
3. Xét văn phạm G : 
V = {S, B, C}, T = {a, b, c} và tập P = { S → aSBC 
 16 
Chương II : Ngôn ngữ và biểu diễn ngôn ngữ 
S → aBC 
CB → BC 
aB →ab 
bB → bb 
bC → bc 
cC → cc } 
 Đây là văn phạm loại 1. 
 Chẳng hạn, một dẫn xuất từ S có dạng : 
S ⇒ aSBC ⇒ aaBCBC ⇒ aabCBC ⇒ aabBCC ⇒ aabbCC ⇒ aabbcC ⇒ aabbcc = 
a2b2c2
Hay văn phạm sinh ra ngôn ngữ L(G1) = {anbncn ⏐n > 0}. 
IV. CƠ CHẾ ÔTÔMÁT 
4.1. Định nghĩa ôtômát 
Ngoài các văn phạm, người ta còn sử dụng một phương tiện khác để xác định ngôn 
ngữ là ôtômát. Ôtômát, dịch nghĩa là máy tự động, được hiểu là các “máy” trừu tượng 
có cơ cấu và hoạt động rất đơn giản nhưng có khả năng đoán nhận ngôn ngữ. Với một 
chuỗi bất kỳ, sau một số bước làm việc, ôtômát sẽ cho câu trả lời chuỗi đó có thuộc 
ngôn ngữ hay không. Để có được quá trình tự động như vậy, con người thường phải 
lập trình sẵn cho nó một “lộ trình” thực hiện, và các máy chỉ cần hoạt động theo đúng 
lộ trình này. Một trong số những máy tự động này điển hình mạnh nhất có thể nói 
chính là máy tính số ngày nay. Tuy hoạt động theo kiểu “máy”, song thực chất mỗi 
bước làm việc của ôtômát là một sự thay thế ký hiệu, nghĩa là một bước dẫn xuất như 
đã nói ở trên. 
Nói chung, một mô hình ôtômát thường bao gồm những thành phần chủ yếu như sau : 
Bộ điều khiển
INP 
 17
Chương II : Ngôn ngữ và biểu diễn ngôn ngữ 
Hình 2.1 - Mô hình chung cho một ôtômát 
OUTPU
BỘ
Chuỗi nhập cần xác định sẽ được lưu trữ trên băng input. Tại mỗi thời điểm, ứng với 
trạng thái hiện thời, đọc vào một ký tự nhập trên băng input, có thể kết hợp với việc 
xem xét ký hiệu tương ứng trong Bộ nhớ, Bộ điều khiển của ôtômát sẽ quyết định 
bước chuyển đến trạng thái kế tiếp. 
Các loại ôtômát tương ứng với từng lớp văn phạm sẽ được giới thiệu lần lượt trong 
những chương tiếp theo. 
4.2. Phân loại các ôtômát 
Dựa theo hoạt động của ôtômát, thông thường người ta chia ôtômát thành hai dạng 
sau: 
Ôtômát đơn định (Deterministic Automata) : Là một ôtômát mà tại mỗi bước di 
chuyển chỉ được xác định duy nhất bởi cấu hình hiện tại. Sự duy nhất này thể hiện 
tính đơn định, nghĩa là hàm chuyển của ôtômát dạng này luôn là đơn trị. 
Ôtômát không đơn định (Non - deterministic Automata) : Là một ôtômát mà tại 
mỗi bước di chuyển, nó có một vài khả năng để chọn lựa. Sự chọn lựa này thể hiện 
tính không đơn định, nghĩa là hàm chuyển của ôtômát dạng này là đa trị. 
 18 
Chương II : Ngôn ngữ và biểu diễn ngôn ngữ 
BÀI TẬP CHƯƠNG II 
Bộ 
điều 
ể
2.1. Chứng minh hoặc bác bỏ : L+ = L* - {ε}. 
2.2. L+ hay L* có thể bằng ∅ không ? Khi nào thì L+ hay L* là hữu hạn ? 
2.3. Hãy cho biết các thứ tự cho phép liệt kê các phần tử của các ngôn ngữ sau : 
 a) {a, b}*
 b) {a}*{b}*{c}*
 c) {w⏐w ∈{a, b}+ và số a bằng số b trong w} 
2.4. Một chuỗi hình tháp có thể định nghĩa là một chuỗi đọc xuôi hay ngược đều như 
nhau, hoặc cũng có thể định nghĩa như sau : 
 1) ε là chuỗi hình tháp. 
 2) Nếu a là một ký hiệu bất kỳ thì a là một chuỗi hình tháp. 
 3) Nếu a là một ký hiệu bất kỳ và X là một chuỗi hình tháp thì aXa là một 
chuỗi hình tháp. 
 4) Không còn chuỗi hình tháp nào ngoài các chuỗi cho từ (1) đến (3). 
Hãy chứng minh quy nạp rằng 2 định nghĩa trên là tương đương. 
2.5. Các chuỗi ngoặc đơn cân bằng được định nghĩa theo 2 cách : 
Cách 1 : Một chuỗi w trên bộ chữ cái { ( , ) } là cân bằng khi và chỉ khi : 
a) w chứa cùng một số ')' và '(' 
b) Mọi tiền tố của w chứa số các '(' ít nhất bằng số các ')'. 
Cách 2 : 
a) ( là chuỗi ngoặc đơn cân bằng 
b) Nếu w là một chuỗi ngoặc đơn cân bằng, thì (w) là chuỗi ngoặc đơn cân 
bằng. 
c) Nếu w và x là các chuỗi ngoặc đơn cân bằng, thì wx là chuỗi ngoặc đơn cân 
bằng. 
d) Không còn chuỗi ngoặc đơn cân bằng nào khác với trên. 
Hãy chứng minh bằng quy nạp theo độ dài chuỗi rằng 2 định nghĩa trên là tương 
đương. 
 19