Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 2: Ngôn ngữ, văn phạm và ôtômát - Nguyễn Thị Thùy Linh

n ngữ trên bộ chữ cái Σ tùy ý 0
 L = {ε}  
 • L = {} là ngôn ngữ trên bộ chữ cái Σ tùy ý 
 L1 = L 
 • L = {a, aa, aab} là một ngôn ngữ hữu hạn trên Σ = {a,b} 
 L2 = LL 
 • L = {(ab)n | n 0 } là một ngôn ngữ vô hạn trên Σ ={a,b} 
 3 2 
 • L = {an bn | n ≥ 0 } là một ngôn ngữ vô hạn trên Σ = {a,b} L =LL
 n n-1 
 • L = {0n 1n | n ≥ 0 } là một ngôn ngữ vô hạn trên Σ = {0,1} L = L L
 9 10 
 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} 
 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 2
 trước: • L = {aa, aba, baa, baba} 
  Bao đóng sao của một ngôn ngữ L, ký hiệu L* • L3 = {aaa, aaba, abaa, ababa, baaa,baaba, babaa, 
 L* = L0  L1  L2   bababa} 
 Trong đó Li cho bởi định nghĩa đệ quy sau: • L* = {ε, a, ba, aa, aba, baa, baba, aaa, aaba, } 
 L0 = {} • L+ = { a, ba, aa, aba, baa, baba, aaa, aaba, } 
 Li = LLi-1 với i 1. Độ ưu tiên của phép toán : (1)bao đóng, (2)ghép, 
 ∞ 푖 
  Bao đóng Kleene: L* = 푖=0 퐿 (3)hợp 
 + ∞ 푖 1 2 3 n 
  Bao đóng dương (positive): L = 푖=1 퐿 = L  L  L   L 
 Chú ý: L* = L0 + L+ 
 11 12 
 3 
Biểu diễn ngôn ngữ Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt) 
 1. Cách 1: Liệt kê chuỗi: L = {aa, aba, baa, baba} 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). 
 2. Cách 2: Mô tả đặc điểm chủ yếu: L = {ai | i là số nguyên tố} 
 Ví dụ 1: Cho L là một ngôn ngữ trên bộ chữ ={a, b}, L định nghĩa như sau: 
 3. Cách 3: Biểu diễn thông qua văn phạm và automata: (1)  L 
 (2) Nếu X L, thì aXb L. 
 • Cho phép biểu diễn ngôn ngữ một cách tổng quát 
 (3) Không còn chuỗi nào khác thuộc L 
 • Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữ Ban đầu, do (1), ta có chuỗi  L. Xem  là X thì do (2) ta sẽ có chuỗi ab L 
 tức là chuỗi ab L. Bây giờ xem ab như là X thì do (2) ta sẽ có aabb L. 
 VD văn phạm có tập qui tắc: P={Câu đơn Chủ ngữ Vị ngữ; 
 i i
 .} là cơ chế sản sinh ra mọi câu đơn của Tiếng Việt. Tương tự ta có aaabbb L, cứ thế tiếp tục ta có các chuỗi a b L (i≥0). 
 Trên đây cho ta một quy tắc viết lại chuỗi. 
 • 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? Dễ nhận thấy rằng ngôn ngữ cần tìm là L = {aibi| i = 0, 1, 2, } 
 13 14 
 Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt) 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 
 Định nghĩa: Một hệ viết lại là một bộ đôi W = (Σ, P) trong 
 chuỗi con ab bởi . Định nghĩa này cho ta một cách đoán 
 đó Σ là bộ chữ cái và P là tập hợp hữu hạn các cặp chuỗi 
 nhận một chuỗi bất kỳ có thuộc ngôn ngữ hay không. 
 trên Σ. Một phần tử (Σ, w) của P được gọi là một quy tắc 
 Đoán nhận cũng là một quy tắc viết lại chuỗi. Chẳng hạn sau 
 viết lại hay một sản xuất và thường viết Σ w. 
 đây là một quá trình đoán nhận trong đó chuỗi con ab thay 
 ĐN suy dẫn trực tiếp: Ta nói chuỗi x trên Σ suy dẫn trực 
 thế  được gạch dưới. 
 tiếp chuỗi y, và viết x Wy hoặc viết gọn x y khi hệ W 
 aabbab 
 đã rõ, khi và chỉ khi tồn tại các chuỗi x1, Σ, x2 và w sao cho 
 abab 
 x = x1 Σ x2, y = x1wx2, và Σ w là một sản xuất trong P. 
 ab 
  
 Như thế chuỗi aabbab là thuộc ngôn ngữ L 
 15 16 
 4 
 Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt) 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 Qui tắc viết gộp: Nếu trong P, ta có một loạt 
 y, và viết x * y, 
 w các sản xuất có cùng một vế trái dạng 
 Σ w1 
hoặc viết gọn là x *y khi hệ W đã rõ, khi và chỉ khi 
 Σ w2 
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 
 Σ wn 
tiếp xi+1 đối với 0 i k-1 . 
 thì các sản xuất đó thường được viết gộp vế trái là: 
 Σ w1| w2| | wn 
 17 18 
 Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt) 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 
 Các ngôn ngữ cho ở các ví dụ 1 và ví dụ 2 ở trên 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 
 thể biểu diễn bởi hệ viết lại như sau: liên kết các từ lại thành câu. 
 Ví dụ: 
 Ngôn ngữ Hệ viết lại 
 Cho đoạn văn phạm tiếng Anh sau 
 *
 Ví dụ 1: Cho L là một ngôn ngữ trên bộ chữ {a, b}, định Ls(W, {X})  {a, b} , 
 nghĩa như sau: trong đó: → , 
  L W = ({a, b, X}, {X , → , 
 X aXb}). 
 Nếu X L, thì aXb L. → , 
 Vậy L = {ai bi | i ≥ 0} 
 → a | the, 
 Ví dụ 2: Ngôn ngữ L được định nghĩa là tập tất cả các Lđ = (W, {}), 
 chuỗi có thể thu về chuỗi rỗng  bằng một dãy phép thay trong đó: → boy | dog, 
 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? W = ({a, b}, {ab }). → runs | walks, 
 Trường hợp này L không thể biểu diễn! 
 19 20 
 5 
Định nghĩa văn phạm 
 Các luật sinh (production) đôi khi còn được gọi là các qui tắc 
 (rule) hay luật viết lại (written rule) 
 Định nghĩa 1: 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í dụ 3: Cho văn phạm sau 
 • V (variables): tập các biến (VD: A, B, C, ) G = (V={S, A, B}, T={a, b}, P,S), với P: 
 S → aAS | bBS | λ, 
 • T (terminal): tập các ký hiệu kết thúc (V  T = Ø) (VD: 
 a, b, c, , w, x, y, ...) A → aaA | b, 
 → 
 • P (production): tập luật sinh, dạng α→β với α, β (V B bbB | a, 
  T)* Văn phạm là cơ chế sinh ra mọi chuỗi con của ngôn ngữ: 
 • S (start): ký hiệu bắt đầu (S  V) Thật vậy, mọi dẫn xuất bắt đầu từ S có dạng: 
 S →* ab 
 S →* ba 
 21 22 
 Một số qui ước Định nghĩa ngôn ngữ L sinh bởi văn phạm G 
 Các kí tự chữ hoa A, B, C, D, E và S biểu thị các biến; S là kí 
 hiệu khởi đầu trừ Khi được phát biểu khác đi. 
 Các kí tự chữ thường a, b, c, d, e, các kí số, các chuỗi in đậm Định nghĩa 2: Ngôn ngữ L được sinh bởi văn phạm G: 
 biểu thị các kí hiệu kết thúc (terminal). 
 L (G) = {w  w T * và S * w} 
 Các kí tự chữ hoa X, Y, Z biểu thị các kí hiệu có thể hiểu là kí 
 hiệu kết thúc hoặc biến. Ví dụ:Tìm ngôn ngữ được sinh ra bởi văn phạm trong ví dụ 3 
 trên. 
 Các kí tự chữ thường u, v, w, x, y, z biểu thị chuỗi các kí hiệu 
 kết thúc. Văn phạm tương đương: là 2 văn phạm sinh ra cùng một 
 Các kí tự chữ thường Hi Lạp ,β,γ biểu thị chuỗi các biến và ngôn ngữ (G1 tương đương G2 L(G1)=L(G2) ) 
 các kí hiệu kết thúc. 
 23 24 
 6 
 Ví dụ: Hai văn phạm tương đương Dẫn xuất câu (derivation) 
 G1(V,T,P,S) G2(V,T,P,S) 
 ∈
 V = {A,B,C} V = {S,A,B} Nếu w L(G) thì phải tồn tại dãy dẫn xuất (quá 
 T = {a,b} T = {0,1} 
 P = {A BC P = {S 0A trình dẫn xuất): 
 B aB | a A 0A | 1B |1 
 C bC | b } B 1B | 1 } S w1 w2 w3  wn w 
 S = A là kí hiệu bắt đầu S là kí hiệu bắt đầu 
 Tìm ngôn ngữ được sinh ra bởi văn phạm? Hệ viết lại là S * w 
 Có nhận xét gì về G1 và G2? 
 Hướng dẫn: Dãy này được gọi là một sự dẫn xuất câu của w 
 L1= {anbm | n,m 1} trên ={a,b} L2 = {0n1m | n,m > 0} trên 
 ={0,1} Dạng câu (sentential forms) 
 Nhận xét : Rõ ràng L1= L2 nên G1 G2  Dãy S,w1,w2,wn được gọi là các dạng câu của sự 
 SV tự chứng minh! dẫn xuất. 
 Mở rộng: Cho G1 tìm G2 sao cho G2 G1. 
 G2 tìm được không nhất thiết phải giống như trên  Câu w cũng được xem là một dạng câu đặc biệt 
 25 26 
 Phân cấp văn phạm 
 Ví dụ: cho 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, 
 G = ({S},{a,b},P,S} với dẫn xuất P sau: Noam Chomsky đề nghị một hệ thống phân loại các văn 
 P = { S aSb | λ } phạm dựa vào tính chất của các luật sinh. 
 (tham khảo  
 Một dẫn xuất từ S có dạng: 
 S aSb aaSbb aabb 
Gọi là một dãy dẫn xuất (quá trình dẫn xuất câu) 
Vì vậy có thể viết S * aabb 
 Chuỗi aabb là một câu của ngôn ngữ được sinh ra 
 bởi G, còn aaSbb là một dạng câu 
 Ngôn ngữ tương ứng với văn phạm này là: 
 L(G) = {anbn | n ≥ 0 } 
 27 28 
 7 
Phân cấp văn phạm Phân cấp văn phạm 
 Loại 0 – Văn phạm không hạn chế 
 (Unrestricted Grammar): không cần thỏa điều 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. 
 kiện ràng buộc nào trên tập các luật sinh 
 • VPCQ Tuyến tính phải (gọi tắt VPCQ phải): 
 Loại 1 – Văn phạm cảm ngữ cảnh (CSG – A → wB | w 
 Context Sensitive Grammar): nếu văn phạm G 
 • VPCQ Tuyến tính trái (gọi tắt VPCQ trái): 
 có các luật sinh dạng →β và |β| ≥ | | 
 A → Bw | w 
 Loại 2 – Văn phạm phi ngữ cảnh (CFG – 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) 
 Context-Free Grammar): có luật sinh dạng A→ 
 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, 
 với A là một biến đơn và là chuỗi các ký hiệu 3, ta có: 
 thuộc (V  T)* 
 L3  L2  L1  L0 
 29 30 
Các ví dụ về văn phạm Các ví dụ về văn phạm 
 Ví dụ 1: văn phạm G( {S, A}, {a, b}, P, S ) Ví dụ 2: văn phạm G( {S}, {a, b}, P, S ) 
 P = S aS 
 S aA P = S aSb 
 A bA S ab  
 A b  
 1. G là văn phạm gì? 1. G là văn phạm gì? 
 2. Tìm ngôn ngữ L(G) được sinh bởi văn phạm. Ngôn ngữ 2. Tìm ngôn ngữ L(G) được sinh bởi văn phạm. Ngôn ngữ 
 tìm được là ngôn ngữ gì? tìm được là ngôn ngữ gì? 
 31 32 
 8 
Các ví dụ về văn phạm Gợi ý đáp án 
 Ví dụ 3: văn phạm G( {S, B, C}, {a, b, c}, P, S ) Ví dụ 1: văn phạm G( {S, A}, {a, b}, P, S ) 
 P = S → aSBC S aS 
 S aA 
 S → aBC P = 
 CB → BC A bA 
 A b 
 aB → ab 
 bB → bb Đây là văn phạm chính qui (dạng tuyến tính phải) 
 bC → bc 
 cC → cc  Một dẫn xuất từ S có dạng: 
 1. G là văn phạm gì? 
 S aS aaS aaaA aaabA aaabbA aaabbbA 
 2. Tìm ngôn ngữ L(G) được sinh bởi văn phạm. Ngôn ngữ aaabbbb = a3 b4 
 tìm được là ngôn ngữ gì? 
 L(G) = {anbm | n,m ≥ 1} 
 33 34 
Gợi ý đáp án Gợi ý đáp án 
 Ví dụ 3: văn phạm G( {S, B, C}, {a, b, c}, P, S ) 
 Ví dụ 2: văn phạm G( {S}, {a, b}, P, S ) 
 S → aSBC 
 S aSb 
 P = S → aBC 
 S ab CB → BC 
 P = aB → ab 
 bB → bb 
 Đây là văn phạm phi ngữ cảnh bC → bc 
 cC → cc 
 Một dẫn xuất từ S có dạng: 
 Đây là văn phạm cảm ngữ cảnh 
 S aSb aaSbb aaaSbbb aaaabbbb = a4b4 
 Một dẫn xuất từ S: S aSBC aaBCBC aabCBC 
 n n
 L(G) = {a b | n ≥ 1} aabBCC aabbCC aabbcC aabbcc=a2b2c2 
 L(G) = {anbncn | n ≥ 1} 
 35 36 
 9 
 Ôtômát (Automata) Định nghĩa Ôtômát (Automata) 
 Nội dung: Định nghĩa: là máy trừu tượng, là thiết bị có thể tự động 
 thực hiện công việc mà không cần sự can thiệp của 
 1. Định nghĩa Ôtômát con người. 
 2. Cấu tạo • Cơ cấu và hoạt động đơn giản nhưng có khả năng 
 đoán nhận ngôn ngữ 
 3. Hoạt động 
 • Con người dựa trên tập quy tắc lập trình sẵn cho máy 
 một ‘lộ trình’ để thực hiện 
 4. Phân loại 
 • Máy trừu tượng này là mô hình điển hình của máy tính 
 5. Ứng dụng số ngày nay 
 37 38 
Cấu tạo Ôtômát Chức năng các bộ phận 
 Thiết bị đầu vào (input file): là nơi mà các chuỗi nhập (input string) được 
 ghi lên, và được ôtômát đọc nhưng không thay đổi được nội dung của nó. 
 Máy này gồm các thành phần chủ yếu như sau: Nó được chia thành các ô (cells, squares), mỗi ô giữ được một kí hiệu. 
 Cơ cấu nhập (input mechanism): là bộ phận có thể đọc input file từ trái 
 sang phải, một kí tự tại một thời điểm. Nó cũng có thể dò tìm được điểm kết 
 INPUT thúc của chuỗi nhập (eof, #). 
 Bộ nhớ tạm (temporary storage): là thiết bị bao gồm một số không giới 
 hạn các ô nhớ (cell), mỗi ô có thể giữ một kí hiệu từ một bảng chữ cái 
 (không nhất thiết giống với bảng chữ cái ngõ nhập). Ôtômát có thể đọc và 
 thay đổi được nội dung của các ô nhớ lưu trữ (storage cell). 
 Đơn vị điều khiển (control unit): mỗi ôtômát có một đơn vị điều khiển, cái 
 Bộ điều khiển mà có thể ở trong một trạng thái bất kỳ trong một số hữu hạn các trạng 
 thái nội, và có thể chuyển đổi trạng thái trong một kiểu được định nghĩa 
 sẵn nào đó. 
 OUTPUT 
 BỘ NHỚ 
 39 40 
 10 
 Hoạt động Ôtômát Các khái niệm 
 Một Ôtômát được giả thiết là hoạt động trong một khung thời Trạng thái nội (internal state): là một trạng thái của đơn vị điều khiển 
 gian rời rạc (discrete time frame). mà nó có thể ở vào. 
 Trạng thái kế (next state): là một trạng thái nội của đơn vị điểu khiển mà 
 Tại một thời điểm bất kỳ đã cho, đơn vị điều khiển đang ở nó sẽ ở vào tại thời điểm kế tiếp. 
 trong một trạng thái nội (internal state) nào đó, và cơ cấu 
 Hàm chuyển trạng thái (transition function): là hàm gởi ra trạng thái 
 nhập là đang quét (scanning) một kí hiệu cụ thể nào đó trên kế của ôtômát dựa trên trạng thái hiện hành, kí hiệu nhập hiện hành được 
 input file. quét, và thông tin hiện hành trong bộ nhớ tạm. 
 Cấu hình (configuration): được sử dụng để tham khảo đến bộ ba thông 
 Trạng thái nội của đơn vị điều khiển tại thời điểm kế tiếp được 
 tin: trạng thái cụ thể mà đơn vị điều khiển đang ở vào, vị trí của cơ cấu 
 xác định bởi trạng thái kế (next state) hay bởi hàm chuyển nhập trên thiết bị nhập (hay nói cách khác ôtômát đang đọc đến kí hiệu nào 
 trạng thái (transition function). của thiết bị nhập), và nội dung hiện hành của bộ nhớ tạm. 
 Trong suốt quá trình chuyển trạng thái từ khoảng thời gian Di chuyển (move): là sự chuyển trạng thái của ôtômát từ một cấu hình 
 này đến khoảng thời gian kế, kết quả (output) có thể được này sang cấu hình kế tiếp. 
 sinh ra và thông tin trong bộ nhớ lưu trữ có thể được thay 
 đổi. 
 41 42 
Phân loại dựa vào hoạt động Ôtômát Phân loại dựa vào kết quả xuất ra của Ôtômát 
 Accepter: là Ôtômát mà đáp ứng ở ngõ ra của nó 
 Ôtômát đơn định (Deterministic Automata): được giới hạn trong hai trạng thái đơn giản “yes” 
 • Mỗi bước di chuyển chỉ được xác định duy nhất bởi hay “no”. “yes" tương ứng với việc chấp nhận chuỗi 
 cấu hình hiện tại (hàm chuyển của Ôtômát là đơn trị) nhập, "no" tương ứng với việc từ chối, không chấp 
 Ôtômát không đơn định (Non-deterministic Automata): nhận, chuỗi nhập. 
 • Tại mỗi bước di chuyển, nó có vài khả năng lựa chọn Transducer: là Ôtômát tổng quát hơn, có khả năng 
 để di chuyển (hàm chuyển của Ôtômát là đa trị). Việc sinh ra các chuỗi kí tự ở ngõ xuất. Máy tính số là 
 có vài khả năng lựa chọ thể hiện tính không đơn định 
 một Transducer điển hình. 
 43 44 
 11 
Một vài ứng dụng Bài tập 
 Cung cấp kiến thức nền tảng cho việc xây 1. Tìm Ngôn ngữ L1 bao gồm các chuỗi từ 
 dựng các ngôn ngữ lập trình (NNLT), các khóa begin, end của ngôn ngữ Pascal. Các 
 trình dịch. chuỗi biểu diễn cấu trúc lồng nhau của các 
 Dùng văn phạm để định nghĩa các NNLT. cặp từ khóa này trong các chương trình 
 Dùng Accepter để định nghĩa một vài thành trên ngôn ngữ Pascal 
 phần của NNLT. 2. Tìm Ngôn ngữ L2 bao gồm tập các danh 
 Xây dựng các bộ phân tích từ vựng, phân hiệu của Pascal 
 tích cú pháp cho các NNLT. 
 45 46 
 Xây dựng văn phạm cho ngôn ngữ 
Xác định ngôn ngữ của văn phạm Ngôn ngữ L1, và L2 ở trên 
1. G1 có tập luật sinh là S → aSbS | bSaS | λ L3 = {wwR | w ∈ {a,b}*} 
2. G2 có tập luật sinh: L4 = {anbmc n+m | n,m ≥ 0} 
 E → E + T | T L5 = {anbn+mcm | n,m ≥ 0} 
 T → T * F | F 
 F → (E) | a | b 
 47 48 
 12