Bài giảng Automata và ngôn ngữ hình thức - Chương 2: Ký hiệu, bộ chữ cái, chuỗi

1 
Ngôn ngữ và sự phân cấp Chomsky 
Nội dung: 
• Khái niệm ngôn ngữ 
• Cách biểu diễn ngôn ngữ 
• Văn phạm 
• Sự phân lớp văn phạm 
Chương 2: 
2 
Ký hiệu, bộ chữ cái, chuỗi 
Ký hiệu (symbol): là một thực thể trừu tượng mà ta 
không định nghĩa được một cách hình thức 
• Các chữ cái a, b, c  hoặc các số 1, 2, 3  
Bộ chữ cái (alphabet): Σ 
• Là một tập (không rỗng) các ký hiệu nào đó 
• Bộ chữ cái Latin {A, B, C, , a, b, c, , z} 
Chuỗi (string): một chuỗi (hay một từ - word) trên bộ 
chữ cái Σ 
• Là một dãy hữu hạn các ký hiệu của Σ 
• Một ký hiệu có thể xuất hiện nhiều lần 
3 
Chuỗi 
Độ dài chuỗi: là số các ký hiệu tạo thành chuỗi 
• |abca| = 4 
Chuỗi rỗng: ký hiệu ε, là chuỗi không có ký hiệu nào 
• |ε| = 0 
Chuỗi con: chuỗi v là chuỗi con của w nếu v được tạo 
bởi các ký hiệu liền kề nhau trong chuỗi w. 
• Chuỗi 10 là chuỗi con của chuỗi 010001 
Chuỗi tiền tố: là chuỗi con bất kỳ nằm ở đầu chuỗi 
Chuỗi hậu tố: là chuỗi con bất kỳ nằm ở cuối chuỗi 
• Chuỗi abc có các tiền tố a, ab, abc 
• Chuỗi 0246 có các hậu tố 6, 46, 246, 0246 
4 
Chuỗi 
Chuỗi nối kết (ghép): là chuỗi được tạo thành bằng 
cách viết chuỗi thứ nhất, sau đó viết chuỗi thứ hai, ... 
• Nối ghép của chuỗi Long và Int là LongInt 
• Nối kết của chuỗi rỗng: εw = wε = w (với mọi w) 
→ ε là đơn vị của phép nối kết 
Chuỗi đảo ngược: của chuỗi w, ký hiệu wR, là chuỗi 
w được viết theo thứ tự ngược lại. 
 w = abcd → wR = dcba εR = ε 
5 
Ngôn ngữ (Languages) 
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++,  
• 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 
6 
Ngôn ngữ (Languages) 
Một ngôn ngữ (hình thức) L là một tập hợp các chuỗi 
của các ký hiệu từ một bộ chữ cái  nào đó. 
* và +: 
● * : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng 
ε, sinh ra từ bộ chữ cái . 
● + : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi 
rỗng ε, sinh ra từ bộ chữ cái . 
 * = + + {ε} + = * - {ε} 
●  = {0,1} thì: 
✔ * = {ε, 0, 1, 00, 01, 10, 11, 000, } 
✔ + = {0, 1, 00, 01, 10, 11, 000, } 
✔ Chuỗi 010210  * vì có số 2   
7 
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 
• LLLLL = Li (kết nối i lần trên cùng ngôn ngữ L) 
• L0 = {ε} 
Các phép toán trên ngôn ngữ 
L 
8 
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 Kleene: L* =  Li 
Bao đóng dương (positive): L+ =  Li 
Chú ý: L+ = L*L = LL* L* = L+  {ε} 
Ví dụ: cho L = {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, } 
Các phép toán trên ngôn ngữ 
i = 0 
 
i = 1 
 
9 
Biểu diễn ngôn ngữ 
Liệt kê chuỗi: L = {aa, aba, baa, baba} 
Mô tả đặc điểm chủ yếu: L = {ai | i là số nguyên tố} 
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ữ 
• 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 
10 
Định nghĩa văn phạm 
Theo từ điển, văn phạm 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 
Định nghĩa: văn phạm cấu trúc G là một hệ thống gồm 4 
thành phần G(V, T, P, S) 
• V (variables): tập các biến (VD: A, B, C, ) 
• T (terminal): tập các ký hiệu kết thúc (V  T = Ø) 
(VD: a, b, c, , w, x, y, ...) 
• P (production): tập luật sinh, dạng α→β với α, β  
(V  T)* 
• S (start): ký hiệu bắt đầu (S  V) 
11 
Định nghĩa văn phạm 
Dẫn xuất trực tiếp: nếu α→β là một luật sinh thì 
      
Dẫn xuất gián tiếp: nếu các chuỗi 1, 2, ...., m  * và 
1  2, 2  3, ..., m-1  m thì m có thể được 
dẫn xuất từ 1 
1 * m 
Ngôn ngữ L sinh bởi văn phạm G: 
L (G) = {w  w  T * và S * w} 
Văn phạm tương đương: là 2 văn phạm sinh ra cùng 
một ngôn ngữ (G1 tương đương G2  L(G1)=L(G2) ) 
12 
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. 
Loại 0 – Văn phạm không hạn chế (Unrestricted 
Grammar): không cần thỏa điều kiện ràng buộc nào 
trên tập các luật sinh 
Loại 1 – Văn phạm cảm ngữ cảnh (CSG – Context 
Sensitive Grammar): nếu văn phạm G có các luật 
sinh dạng α→β và |β| ≥ |α| 
Loại 2 – Văn phạm phi ngữ cảnh (CFG – Context-Free 
Grammar): có luật sinh dạng A→α với A là một biến 
đơn và α là chuỗi các ký hiệu thuộc (V  T)* 
13 
Phân cấp Chomsky trên văn phạm 
Loại 3 – Văn phạm chính quy (RG – Regular 
Grammar): có mọi luật sinh dạng tuyến tính phải hoặc 
tuyến tính trái. 
• Tuyến tính phải: A → wB hoặc A → w 
• Tuyến tính trái: A → Bw hoặc A → w 
 Với A, B là các biến đơn, w là chuỗi ký hiệu kết 
thúc (có thể là rỗng) 
Nếu ký hiệu L0, L1, L2, L3 là các ngôn ngữ được sinh ra 
bởi văn phạm loại 0, 1, 2, 3, ta có: 
L3  L2  L1  L0 
14 
Ví dụ 1: văn phạm G( {S, A}, {a, b}, P, S ) 
Đây là văn phạm loại 3 (dạng tuyến tính phải) 
Một dẫn xuất từ S có dạng: 
S  aS  aaS  aaaA  aaabA  aaabbA  aaabbbA 
 aaabbbb = a3 b4 
  L(G) = a+b+ = {anbm | n,m ≥ 1} 
Các ví dụ về văn phạm 
S  aS 
S  aA 
A  bA 
A  b 
P = 
15 
Ví dụ 2: văn phạm G( {S}, {a, b}, P, S ) 
Đây là văn phạm loại 2 (dạng A→α ) 
Một dẫn xuất từ S có dạng: 
S  aSb  aaSbb  aaaSbbb  aaaabbbb = a4b4 
  L(G) = {anbn | n ≥ 1} 
Các ví dụ về văn phạm 
S  aSb 
S  ab 
P = 
16 
Ví dụ 3: văn phạm G( {S, B, C}, {a, b, c}, P, S ) 
Đây là văn phạm loại 1 
Một dẫn xuất từ S: S  aSBC  aaBCBC  aabCBC  
aabBCC  aabbCC  aabbcC  aabbcc=a2b2c2 
  L(G) = {anbncn | n ≥ 1} 
Các ví dụ về văn phạm 
S → aSBC 
S → aBC 
CB → BC 
aB → ab 
bB → bb 
bC → bc 
cC → cc 
P = 
17 
Định nghĩa ôtômát (automata) 
Định nghĩa: là máy trừu tượng có cơ cấu và hoạt động 
đơn giản nhưng có khả năng đoán nhận ngôn ngữ 
• Con người phải lập trình sẵn cho máy một ‘lộ trình’ 
để thực hiện 
Bộ điều khiển 
INPUT 
OUTPUT 
BỘ NHỚ 
18 
Phân loại automata 
Automata đơn định (Deterministic Automata): 
• 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 (hàm chuyển của automata là 
đơn trị) 
Automata không đơn định (Non-deterministic Automata): 
• Tại mỗi bước di chuyển, nó có vài khả năng để lựa 
chọn (hàm chuyển của automata là đa trị)