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

Chia sẻ: Chuheodethuong 09 | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

40
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 cung cấp cho người học những kiến thức như: Ngôn ngữ (languages); Văn phạm (grammar); Ôtômat (automata). Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 2 - ThS. Nguyễn Thị Thùy Linh

Nội dung  Ba khái niệm cơ bản Chương 2 1. Ngôn ngữ (languages)  Khái niệm ngôn ngữ  Biểu diễn ngôn ngữ Ngôn ngữ, văn phạm và  Hệ viết lại và vấn đề biểu diễn ngôn ngữ. Văn phạm (grammar) ôtômát 2.  Định nghĩa văn phạm  Sự phân cấp văn phạm 3. Ôtômat (automata) 2 Tổng quan về ngôn ngữ: Ký hiệu, bộ chữ cái, chuỗi  Ngôn ngữ tự nhiên:tiếng Việt,tiếng Anh, … • Ký hiệu (symbol):  Ngôn ngữ lập trình: Pascal, C/C++, …  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  ĐN ngôn ngữ trong các từ điển: các ký hiệu  Là tập hợp các câu theo cấu trúc quy định nào đó  Bảng chữ cái La Mã : {I, V, X, L, C, D, M}  Biểu thị các ý nghĩ, các sự kiện hay các khái niệm  Bảng chữ số nhị phân: {0, 1}  Bao gồm một tập các ký hiệu và các quy tắc để vận dụng chúng  Bảng chữ số thập phân: {0,1,2,…,9}  Định nghĩa trên chưa đủ chính xác để nghiên cứu về ngôn  Bảng chữ cái Latinh :{A, B, C, ... , Z, a, b, c, ... , z} ngữ hình thức (ngôn ngữ dùng chung cho cả ngôn ngữ tự  Bảng chữ cái Hi Lạp: {, β, γ, …,} nhiên lẫn ngôn ngữ lập trình). Chúng ta cần xây dựng một  Qui ước: định nghĩa toán học cho khái niệm về ngôn ngữ.  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. 3 4 1
Ký hiệu, bộ chữ cái, chuỗi 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  Chuỗi tiền tố: là một chuỗi con bất kỳ nằm ở đầu chuỗi đó. nhau gồm:  Chuỗi hậu tố:là một chuỗi con bất kỳ nằm ở cuối chuỗi đó.  Các ký hiệu thuộc Σ  Ví dụ: chuỗi abc có các tiền tố là , a, ab, abc và có các hậu tố  Mỗi ký hiệu có thể xuất hiện nhiều lần là , c, bc, abc.  Ví dụ: 010001 là một chuỗi trên bộ chữ cái Σ = {0, 1}  Chuỗi nối kết (ghép): ký hiệu bởi vw, là một chuỗi được tạo  w = abbcab là một chuỗi trên bộ chữ cái Σ = {a,b,c} bằng cách viết v rồi viết w tiếp theo sau, không có khoảng cách.  Độ dài chuỗi w, ký hiệu bởi |w|, là số những ký hiệu hợp thành w.  Ví dụ: ghép Long và Int là LongInt. Chẳng hạn |010001| = 6.  Nối kết với chuỗi rỗng: εw = wε = w (w)  Chuỗi rỗng, ký hiệu  (hay ), là chuỗi có độ dài 0, tức là chuỗi khi đó ε là đơn vị của phép nối kết không có ký hiệu nào.  |uv| = |u| + |v|  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.  |εw| = |wε| = |w| 5 6  Chẳng hạn ab, abb, bc, cb là các chuỗi con của chuỗi abbcb. Ký hiệu, bộ chữ cái, chuỗi Khái niệm về bao đóng sao và bao đóng dương  Đả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: * và +: (bao đóng sao và bao đóng dương) u = a1a2…an thì uR = anan-1…a1. ● * : tập hợp tất cả các chuỗi con được sinh ra từ bộ chữ cái , Đương nhiên R = . kể cả chuỗi rỗng ε.  Phép lũy thừa: Cho w là một chuỗi ● + : tập hợp tất cả các chuỗi con, được sinh ra từ bộ chữ cái , w0 = ngoại trừ chuỗi rỗng ε. w1 = w * = + + {ε} + = * - {ε} w2 = ww ●  = {0,1} thì: w3 = ww2 * = {ε, 0, 1, 00, 01, 10, 11, 000, …} wn = wwn-1 + = {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 7 8 2
Ngôn ngữ (Languages) Các phép toán trên ngôn ngữ Từ các ngôn ngữ có trước, ta có thể thu được các ngôn ngữ mới nhờ áp • 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 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ữ. 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 Σ. Phép phần bù (complement): • Ví dụ: Cho Σ = {a, b} = * - L Σ* = {, a, b, aa, ab, ba, bb, aaa, aab, … } Phép nối kết (concatenation): L • Ta có: L1L2 = {w1w2 | w1  L1 và w2  L2} trên bộ chữ cái Σ1  Σ2 • L =  là ngôn ngữ trên bộ chữ cái Σ tùy ý L0 = {ε}   • 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} • L = {an bn | n ≥ 0 } là một ngôn ngữ vô hạn trên Σ = {a,b} L3=LL2 • L = {0n 1n | n ≥ 0 } là một ngôn ngữ vô hạn trên Σ = {0,1} Ln = L Ln-1 9 10 Các phép toán trên ngôn ngữ Phép bao đóng (closure): Thành lập một ngôn ngữ bằng cách kết nối Ví dụ: cho L = {a, ba} trên bộ chữ cái  = {a,ba} 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: • L2 = {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 của phép toán : (1)bao đóng, (2)ghép, ∞ 𝑖  Bao đóng Kleene: L* = 𝑖=0 𝐿 (3)hợp ∞ 𝑖  Bao đóng dương (positive): L+ = 𝑖=1 𝐿 = L1  L2  L3 …  Ln 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 chủ 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ữ; Tương tự ta có aaabbb  L, …cứ thế tiếp tục ta có các chuỗi aibi  L (i≥0). ….} là cơ chế sản sinh ra mọi câu đơn của Tiếng Việt.  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  , → , Nếu X  L, thì aXb  L. X  aXb}). → , 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 G = (V={S, A, B}, T={a, b}, P,S), với P: • V (variables): tập các biến (VD: A, B, C, …) 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, B → bbB | a, • P (production): tập luật sinh, dạng α→β với α, β  (V  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  Các kí tự chữ thường u, v, w, x, y, z biểu thị chuỗi các kí hiệu trên. 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} P = {A  BC T = {0,1} 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 25  Câu w cũng được xem là một dạng câu đặc biệt 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 http://vi.wikipedia.org/wiki/Noam_Chomsky)  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ế Loại 3 – Văn phạm chính quy (RG – Regular Grammar): có mọi luật sinh dạng (Unrestricted Grammar): không cần thỏa điều 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 → aBC S  aA P= A  bA CB → BC 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 S → aBC P= 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   L(G) = {anbn | 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 4. Phân loại một ‘lộ trình’ để thực hiện • 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 cá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 mà nó có thể ở vào. gian rời rạc (discrete time frame).  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.  Trạng thái nội của đơn vị điều khiển tại thời điểm kế tiếp được  Cấu hình (configuration): được sử dụng để tham khảo đến bộ ba thông 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 sang cấu hình kế tiếp. này đến khoảng thời gian kế, kết quả (output) có thể được 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. Tì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. Tì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