Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 3: Văn phạm chính quy và ôtômát hữu hạn

Nội dung text: Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 3: Văn phạm chính quy và ôtômát hữu hạn

1. Nội dung Chương 3: 1. Ôtômát hữu hạn đơn định - DFA. 2. Ôtômát hữu hạn không đơn định - NFA. VĂN PHẠM CHÍNH QUY 3. Sự tương đương của NFA và DFA VÀ 4. Mối liên quan giữa VPCQ và OH 5. OHD không xuất phát lại ÔTÔMÁT HỮU HẠN 6. Các tính chất đóng của ngôn ngữ chính quy. 7. Định lý KLEENE. 8. Biểu thức chính quy. 9. Thuật toán Thampson 2 Ôtômát hữu hạn đơn định – DFA (Deterministic Finite Automata) Input : w *  Mô tả phi hình thức: 0 1 1 0 0 1 1 1 1  Ôtômát hữu hạn như một “máy” đoán nhận chuỗi, nó Băng từ sức chứa vô hạn làm việc như sau: Output : Yes, w L Băng từ chia thành nhiều ô. Mỗi ô có khả năng lưu q Bộ điều khiển trữ một ký hiệu của chuỗi nhập (chuỗi cần được No, w L đoán nhận w є *).  Tùy theo cấu hình hiện tại gồm (trạng thái hiện thời của bộ điều khiển và ký hiệu trên ô mà đầu đọc quan sát được), mà Ôtômát Có một đầu đọc, ở mỗi thời điểm quan sát một ô trên chuyển sang trạng thái mới, đồng thời đầu đọc dịch chuyển băng từ. sang phải một ô. Có một bộ điều khiển Q gồm tập hợp hữu hạn trạng thái; ở mỗi thời điểm có một trạng thái hiện hành gọi  Quy luật chuyển sang trạng thái mới, được cho bởi một hàm, gọi là hàm chuyển trạng thái : Q x  Q. là trạng thái nội. 3 4 1
2.  Trong Q có phân biệt q0 Q, gọi là trạng thái đầu và một tập hợp F chứa các trạng thái kết thúc.  Định nghĩa hình thức: Một ôtômát hữu hạn đơn định (viết tắt là  Ta nói ôtômát đoán nhận (hay thừa nhận) một chuỗi vào w * ÔHĐ) là một hệ thống M = (, Q, , q0, F) trong đó:  , nếu xuất phát từ q0, đầu đọc nhìn vào ký hiệu bên trái nhất của w, sau một số bước hữu hạn làm việc, nó đọc xong  là một bộ chữ cái hữu hạn, gọi là bộ chữ vào. chuỗi w và rơi vào một trong các trạng thái kết thúc. Q là một tập hữu hạn các trạng thái,   Q = .  Tập hợp mọi chuỗi (được đoán nhận bởi Ôtômát) hợp thành : Q x  Q, được gọi là hàm chuyển. ngôn ngữ được đoán nhận bởi ôtômát đó.  Do Q là hữu hạn và hàm chuyển  là hàm toàn phần và đơn q0 Q là trạng thái đầu. trị, cho nên bước chuyển của Ôtômát được xác định một F  Q là tập các trạng thái cuối. cách duy nhất. Chính vì vậy mà Ôtômát mô tả như trên được gọi là ôtômát hữu hạn đơn định. 5 6 Biểu diễn hàm chuyển trạng  Ví dụ 3.1: Xét Ôtômát hữu hạn đơn định M(,Q, ,q0,F). trong đó:  = {0, 1}  Có 3 cách biểu diễn hàm chuyển (hàm chuyển trạng thái): Theo định nghĩa  (q ,a)=q Q = {q0, q1, q2, q3} i j F = {q0} Theo bảng truyền Hàm  cho bởi ma trận sau: Ký hiệu vào Trạng thái 0 1 q0 q2 q1 q q q 1 3 0 q2 q0 q3 Theo đồ thị q3 q1 q2 7 8 2
3.  Biểu đồ chuyển cho Ôtômát hữu hạn nói ở trên (Ví dụ 3.1) sẽ  Để cho dễ hình dung hơn, ta thường biểu diễn hàm chuyển dưới như sau: dạng một đồ thị định hướng, gọi là biểu đồ chuyển như sau: Mỗi nút tương ứng với một trạng thái. q1 1 q Nút đầu trỏ bởi mũi tên có chữ “Bắt đầu”. Bắt đầu 1 Đầu q q0 1 Nút cuối được khoanh bởi hai vòng tròn. q0 1 Nếu (q, a) = p thì có một cung đi từ nút q tới nút p, và cung 0 0 0 1 0 đó mang nhãn a. q3 q2 a 1 q p 9 10 Tính chất của hàm chuyển trạng Định nghĩa tập đoán nhận bởi (M)  Ký hiệu T(M) 1.  (q,)=q  T(M) = { w | w * , (q ,w) = q F } 2.  (q,wa)=  ((q,w),a) 0 f  Ví dụ: 3.  (q,aw)=  ((q,a),w), w * và a  w = 1010 4.  (q,xy)=  ((q,x),y), x,y * 1 w2 = 11001001 W3 = 110101 11 12 3
4. Quá trình đoán nhận chuỗi vào  Cho chuỗi w= 110101. Quá trình đoán nhận chuỗi vào đó  Ta gọi một hình trạng của ÔHĐ là một chuỗi có dạng qx diễn tả bằng các bước chuyển sau: với q Q và x *. 110101 110101 110101 110101 110101 110101  VD: q0w3 = q0 110101 là một hình trạng của (M) q q q F 0 1 q0 q2 q3 q1 0  Quá trình đoán nhận một chuỗi của ÔHĐ là quá trình biến đổi các hình trạng, thực chất là quá trình “viết lại”  Vì q0 F, vậy chuỗi vào w=110101 được thừa nhận bởi Ôtômat. chuỗi.  Nhận xét rằng mỗi trạng thái của M ghi nhớ một tình trạng nhất  VD: Viết quá trình đoán nhận chuỗi x = 110101 định của phần chuỗi vào đã đọc như sau:  q0: phần đã đọc chứa một số chẵn con số 0 và một số chẵn con số 1.  q1: phần đã đọc chứa một số chẵn con số 0 và một số lẻ con số 1. 13 14 Tập các chuỗi được ôtômát thừa nhận Ngôn ngữ đoán nhận (thừa nhận) bởi M q : phần đã đọc chứa một số lẻ con số 0 và một  Ngôn ngữ đoán nhận (hay thừa nhận) bởi M là: 2 * số chẵn con số 1. L(M) = {w| w * và q0w p với p F} q : phần đã đọc chứa một số lẻ con số 0 và một  Trở lại ví dụ 3.1, hệ viết lại ngầm định của nó gồm các sản 3 xuất sau: số lẻ con số 1.  Mỗi lần đọc thêm một ký hiệu 0 hay 1, hàm  luôn q00 q2 q10 q3 q20 q0 q30 q1 luôn chuyển trạng thái của ôtômát về đúng tình trạng q01 q1 q11 q0 q21 q3 q31 q2 trên. Vì F = {q }, cho nên các chuỗi được M thừa 0  Quá trình đoán nhận chuỗi w = 110101 là: nhận là các chuỗi có chứa một số chẵn con số 0 q 110101 q 10101 q 0101 q 101 q 01 q 1 q F và một số chẵn con số 1. 0 1 0 2 3 1 0  Có một cách viết khác (thường thấy ở các sách khác): (q0,110101)=(q1,10101)=(q0,0101)=(q2,101)=(q3,01)= (q1, 1) = q0 F 15 16 4
5. Ôtômát hữu hạn không đơn định – NFA Ôtômát hữu hạn không đơn định (tt) (Nondeterministic Finite Automata)  Dễ dàng mở rộng mô hình ÔHĐ trên để cho hệ viết lại ngầm  Tập đoán nhận bởi Ôtômat * * định của Ôtômát là một hệ viết lại không đơn định, tức là có thể T(M) = {w | w  và q0w qf với qf F}. chứa các sản xuất có cùng vế trái.  Ngôn ngữ đoán nhận bởi M là:  Định nghĩa: Ta gọi Ôtômát hữu hạn không đơn định (hay không * * tiền định) viết tắt là ÔHK, là một hệ thống: L(M) = {w | w  và q0w qf với qf F}.  Chuỗi vào w được (M) thừa nhận nếu tồn tại ít M = {, Q, , q0, F} nhất một quá trình dẫn xuất q w * q với q Trong đó: , Q, q0, F vẫn như tương tự OHĐ. Chỉ duy 0 f f nhất hàm  là đổi lại: : Q x  2Q. F.  Hệ viết lại W = (V, P) ngầm định của M cũng có V =   Q.  Ví dụ 3.2: Xét ÔHK M = ({0,1}, {q0, q1, q2, q3, q4}, , q0, {q2, q4}) với hàm chuyển  cho như sau: 17 18 Ôtômát hữu hạn không đơn định (tt) Ôtômát hữu hạn không đơn định (tt) 0, 1  0 1 0, 1  Nếu xét tất cả các quá trình, ta có một “cây” như sau: q0 {q0, q3} {q0, q1} Đầu q0 q3 q q  {q } 0 0 4 q001001 q01001 q0001 q001 q01 q0 1 2 1 q2 {q2} {q2} q31001 q1001 q301 q31 q1 q1 q3 {q4}  1 q41 q4 F 0, 1 q4 {q4} {q4}  Như vậy chuỗi 01001 đã thừa nhận bởi M. q2  Dễ thấy rằng ÔHK này thừa nhận các chuỗi trên {0, 1} có  Sau đây là quá trình đoán nhận chuỗi vào 01001, dẫn tới trạng thái cuối q : chứa hai con 0 liên tiếp hoặc có chứa hai con 1 liên 4 tiếp. q 01001 q 1001 q 001 q 01 q 1 q F 0 0 0 3 4 4  L (M) = { w00w, w11w | w * ={0,1}*}  Đây chỉ là một quá trình đoán nhận trong nhiều quá trình. 19 20 5
6. Sự tương đương giữa ÔHĐ và ÔHK Sự tương đương giữa ÔHĐ và ÔHK (tt)  Theo định nghĩa mỗi ÔHĐ cũng là một ÔHK, cho nên: • Mỗi phần tử trong Q’ được ký hiệu bởi tập hợp {q1, q2, , q }, với q , q , , q Q. L(ÔHĐ)  L(ÔHK) (1) k 1 2 0 • Trạng thái đầu q0’ = {q0}.  Định lý 3.1: Nếu L một ngôn ngữ được đoán nhận bởi một  B2 : Hàm chuyển ’ của M’ được thành lập theo công thức: ÔHK, thì cũng có một ÔHĐ đoán nhận L. Nói cách khác L(ÔHK)  L(ÔHĐ) (2) (q , a) ’({q1, q2, , qk}, a) = i  Giải thuật: Input: M = (, Q, , q0, F) là ÔHK đoán nhận L. Output: M’ = ( , Q’, ’, q ’, F’) là OHĐ sao cho L(M’)=L(M)   0  B3: Vẽ đồ thị chuyển trạng thái  B1: Đặt M’ = (, Q’, ’, q ’, F’), trong đó: 0  B4: Kết luận M’ và chú thích rõ 5 phần của Ôtômát • Q’ = 2Q  Với cách thành lập M’ trên ta hoàn toàn CM được L(M) = L(M’) (Tham khảo • F’ là tập mọi trạng thái trong Q’ có chứa một trạng thái cuối sách “Ngôn ngữ hình thức” – Nguyễn Văn Ba, trang 32). nào đó của M. 21 22 Sự tương đương giữa ÔHĐ và ÔHK (tt)  Ví dụ 3.3: Cho M = ({0, 1}, {q0, q1, q2}, , q0, {q2}), là một ÔHK trong đó hàm chuyển • Kết luận : trạng thái như sau: M’ =( , Q’, ’, {q0}, F’) là OHĐ cần tìm. (q0, 0) = {q0, q1} (q0, 1) = {q1} Trong đó:  (q1, 0) = {q2} = Q’ = (q1, 1) =  ’ (vẽ đồ thị Chú ý: cắt bỏ các nhánh không xuất phát từ q hoặc (q2, 0) = {q2} 0 xuất phát từ q0 nhưng không kết thúc được) (q2, 1) = {q2} q là trạng thái bắt đầu Tìm OHĐ tương đương? 0 F’ = 23 24 6
7. Sự tương đương giữa ÔHĐ và ÔHK (tt)  Thực ra trong 2Q thường có nhiều phần tử Bổ đề 3.1:  Lớp các ngôn ngữ đoán nhận bởi Ôtômát hữu không thể truy đạt từ {q0}, nên chẳng cần đưa chúng vào Q’. Vậy để lập Q’, ta nên truy xuất hạn đơn định (hay không đơn định) là một, và gọi là lớp các ngôn ngữ chính quy (viết tắt là từ {q0}, rồi từng bước thêm dần các trạng thái mới, nếu các trạng thái này là kết quả của hàm NNCQ). chuyển thái áp dụng lên các trạng thái đã có  NNCQ được sinh ra bởi VPCQ nên VPCQ có trước đó. mối quan hệ mật thiết với OH. Nghĩa là L(G)=L(M)=L là NNCQ 25 26 Cho ôtômát hữu hạn đơn định xây dựng VPCQ Văn phạm chính quy  Định lý 3.2: Nếu L là một NNCQ trên bộ chữ cái , thì tồn tại một VPCQ phải G sao cho L – {} = L(G).  Định nghĩa VPCQ (nhắc lại): Giải thuật: (xây xựng một VPCQ phải từ một ôtômát hữu hạn đơn định) • Một văn phạm chính quy phải nếu tập luật sinh của nó dạng: Input: L = L(M) với M = (, Q, , q0, F) là ÔHĐ. A wB | w, với w * và A, B . Output:Ta thành lập văn phạm G = (T, V, P, S) sao cho L(G)=L \ {} • Một văn phạm chính quy trái nếu tập luật sinh của nó dạng: Input Output M = (, Q, , q0, F) G = (T, V, P, S) A Bw |w, với w * và A, B .  T =  • Các văn phạm chính quy phải và trái được gọi chung là văn Q = {q q q } V = {V ,V ,V , } phạm chính quy (viết tắt là VPCQ). 0, 1, 2, . 0 1 2  P= • Ngôn ngữ được sinh ra bởi VPCQ gọi là NNCQ. (q0, a) = q1 V0 aV1 (q1, a) = qf F V1 aVf | a a  và q0,q1 Q a T q0 S là kí hiệu bắt đầu trong P F  Q 27 28 7
8. GIẢI a b c Ví dụ 3.4: Tìm văn phạm chính qui sinh ra ngôn ngữ L. Biết rằng Start q L là ngôn ngữ được đoán nhận bởi OH sau đây: q1 q2 3 a b  Văn phạm sinh ra ngôn ngữ L có dạng M=(, Q,,q ,F) 1 G=(T,V,P,S)  xác định như đồ thị: a b c T={a,b,c} ={a,b,c} V={S,A,B,} Start Q={q1,q2,q3} q3 q1 q2 P={S aS | aA F={q } a b 3 A bA | bB | b q là trạng thái bắt đầu 1 B cB | c} S là kí hiệu bắt đầu trong tập luật sinh 29 30  Ví dụ 3.5: Cho ÔHĐ M với  = {a, b}, Q = {q0, q1, q2, q3}, F =  Tìm một số quá trình đoán nhận của OH: {q2}. Hàm chuyển  cho như sau: Xét w1 = aabbb q0aabbb q1abbb q1bbb q2bb q2b q2 F w1 L(M) a  a b Xét w2 = aaa q q aaa q aa q a q F w L(M) q q q a 1 b 0 1 1 1 2 0 1 3 b Đầu Xét w = ba, thật vậy: q ba q a q F w L(M) q q2 3 0 3 3 3 q q q 0 1 1 2 Xét w = aba,thật vậy:q aba q ba q a q F w L(M) b a 4 0 1 2 3 4 q q q 2 3 2 q3 w2, w3, w4 L(G) (theo bổ đề 3.1) q3 q3 q3 a,b T(M)={ab,aab,aabbb,abb,aaab,abbbb, } Biểu đồ chuyển của ÔHĐ  Dễ thấy rằng ngôn ngữ do Ôtômát M đoán nhận là: Tìm văn phạm G sinh ra ngôn ngữ L, sao cho L=L(M) L(M) = {ambn | m, n > 0} Tìm L? (Có chứng minh) • Tìm văn phạm G sinh ra ngôn ngữ L, sao cho L(G)=L(M) Ngôn ngữ tìm được là ngôn ngữ gì? • SV tự làm! 31 32 8
9. Cho VPCQ xây dựng ôtômát hữu hạn không đơn định Cho VPCQ xây dựng ôtômát hữu hạn không đơn định  Cách xây dựng hàm chuyển trạng thái  Input Output  Định lý 3.3: Nếu G là một VPCQ G = (T, V, P, S) M = (, Q, , q , F)  Mỗi sản xuất dạng Vi a1a2 anVj thuộc P phải, thì L(G) là một ngôn ngữ chính 0 Ta có hàm chuyển trạng (q , a a a a ) = q quy. T  =T i 1 2 3 n j Đồ thị vẽ như sau: Giải thuật xây dựng một V = {V0,V1,V2 } Q = {q0, q1, q2, } ôtômát hữu hạn không đơn P=  Start định từ một VPCQ phải: a1 a2 an {V0 aV1 (q ,a) = q . q Input: G = (T, V, P, S). V a a a V 0 1 qi j 1 1 2 3 2 (q , a a a ) = q V2 a} 1 1 2 3 2 Output:Ta thành lập một (q ,a) = q ÔHK M đoán nhận L(G) như 2 3  Mỗi sản xuất dạng Vi a1a2 an thuộc P sau: V0 là kí hiệu bắt q0 là trạng thái bắt đầu đầu trong P Ta có hàm chuyển trạng (qi, a1a2a3 an) = qf F M = (, Q, , q0, F) F = {q3 }  Q Đồ thị vẽ như sau: Vẽ đồ thị Start a a a Kết luận M? 1 2 . n qi qf 33 34  Ví dụ 3.6: Xây dựng một Ôtômát hữu hạn chấp nhận ngôn  (q0,a)=q1 ngữ được sinh bởi văn phạm có tập luật sinh như sau:  (q1,ab)=q0 S aA  (q1,b)=q2 F A abS| b  F = {q2} Giải  q0 là trạng thái bắt đầu Đặt M=(,Q, , q0,F) là OH cần tìm  Vẽ đồ thị chuyển trạng thái như sau: Trong đó: ={a,b} Start a b q2 Q={q0,q1} q0 q1  Xác định như sau: b a 35 36 9
10. Kết luận M=(,Q, , q0,F) là OH cần tìm ÔHĐ không xuất phát lại • Trong đó: • ={a,b} •Định nghĩa: Một ÔHĐ là không xuất phát lại nếu không tồn tại cặp (q, a) để cho (q, a) = q0 với q0 là • Q={q0,q1,q2,q3} trạng thái đầu •  Xác định như sau: •Bổ đề 3.2: Có giải thuật cho phép biến đổi một ÔHĐ • F = {q } 2 M đã cho thành một ÔHĐ không xuất phát lại M’ sao • q0 là trạng thái bắt đầu cho L(M’) = L(M). Giải thuật: Start a b q q0 q1 2 –Giả sử M = (, {q0, q1, , qn}, , q0, F). b a –Lập ÔHĐ M’ = (, Q  {qn+1}, ’, q0, F’) trong đó: q3 37 38 ÔHĐ không xuất phát lại  Ví dụ 3.7: Tìm OHĐ không xuất phát lại M’ tương đương với OHĐ có xuất phát lại M sao cho L(M’)=L(M) (q,a) Nếu q Q và (q, a) q0 '(q,a) q n 1 Nếu q Q và (q, a) = q 0 (M) ’(qn+1, a) = ’(q0, a) Gợi ý F Nếu q0 không thuộc F F' OHĐ không xuất phát lại cần tìm sẽ có đồ thị chuyển trạng Nếu q F F {qn 1} 0 thái sau: Kết luận M' (, Q  {qn+1}, ’, q0, F’) , chú thích 5 phần? Dễ thấy M’ thực hiện cùng các bước chuyển như M, trừ khi (M’) M chuyển về q0 thì M’ chuyển sang qn+1, nhưng sau đó lại tiếp tục bắt chước như M thường. 39 40 10
11. Các tính chất đóng của lớp các NNCQ (tt)  Gọi M’=(, Q  {qn+1}, ’, q0, F’) là OHĐ cần tìm  Trong đó:  Định lý 3.4: Nếu L và L’ là các NNCQ thì L  L’ cũng là NNCQ. ’ a b   = {a,b}  Định lý 3.5: Nếu L  * là một NNCQ, thì * - L cũng là NNCQ. q0 q3 q1  Q = {q0, q1,q2,q3 }  Định lý 3.6: Nếu L và L’ là các NNCQ thì L  L’ cũng là NNCQ. q q   F’ = {q ,q ,q } 1 2 Bổ đề 3.3: Cho L  * và   ’. Có một ÔH với bộ chữ vào  0 2 3 q q 2  3 đoán nhận L khi và chỉ khi có một ÔH với bộ chữ vào ’  q0 là trạng thái bắt đầu q3 q3 q1 đoán nhận L. (Nói cách khác khái niệm NNCQ không tùy  ’ như đồ thị thuộc vào bộ chữ).  Định lý 3.7: Nếu L và L’ đều là các NNCQ thì LL’ cũng là NNCQ.  Định lý 3.8: Nếu L là NNCQ thì L* cũng là NNCQ. 41 42 BIỂU THỨC CHÍNH QUI Định lý KLEENE  Cách khác để mô tả ngôn ngữ chính qui là dùng biểu thức chính qui (BTCQ).  Định lý:  và {} là các NNCQ.  Một BTCQ là sự kết hợp:  Định lý: Với mọi w *, thì {w} là NNCQ. Các ký tự trong , mỗi ký tự có thể xuất hiện nhiều  Hệ quả: Mọi tập con hữu hạn của * đều là NNCQ. lần,  Hệ quả: Mọi ngôn ngữ tạo nên từ các ngôn ngữ hữu Các toán tử: bao đóng (+,*), ghép, hợp hạn bằng cách áp dụng một số hữu hạn lần các phép Các dấu ngoặc: () hợp, ghép tiếp và * đều là NNCQ.  VD:  Định lý KLEENE: Mọi NNCQ đều có thể nhận được từ  Với ngôn ngữ L= {a}, ta có BTCQ là a các ngôn ngữ hữu hạn bằng cách áp dụng một số hữu  L={a,b}, ta có BTCQ là a+b hạn lần các phép hợp, ghép tiếp và *.  L={ab}  {a}, ta có BTCQ là ab+a  L={a,b} . {a} , ta có BTCQ là (a+b)a 43 44 11
12. Biểu thức chính qui Biểu thức chính qui (tt)  Định nghĩa 1: Cho  là một bộ chữ. Một biểu thức chính quy (viết tắt là BTCQ) trên  và tập hợp do nó định nghĩa được chỉ  Các toán tử ưu tiên trong BTCQ từ cao tới thấp: định được định nghĩa một cách đệ quy như sau: (1) Bao đóng : 1. Các biểu thức chính qui nguyên tố gồm: 0+ : số 0 được lặp lại ít nhất 1 lần, nhiều nhất n lần.  là một biểu thức chính quy biểu thị tập rỗng. 0* : số 0 được lặp lại ít nhất 0 lần, nhiều nhất n lần  là một biểu thức chính quy biểu thị tập {}.  a  thì a là một biểu thức chính quy biểu thị tập {a}. (2) Ghép : . 2. Nếu r và s là các biểu thức chính quy, lần lượt chỉ định các (3) Hợp : + tập R và S, thì (r+s), (rs), và (r*) là các biểu thức chính quy, và Khi viết một BTCQ, ta có thể bỏ qua một số ngoặc lần lượt biểu thị các tập R  S, RS, và R*. đơn, chẳng hạn, ((0(1*))+0) có thể viết thành 01* + 0 3. Một BTCQ nếu và chỉ nếu nó có thể được xây dựng từ các vẫn dễ hiểu. biểu thức chính qui nguyên tố bởi áp dụng một số hữu hạn lần * + các qui tắc trong mục 2.  Ta cũng có thể viết tắt biểu thức rr bởi r . 45 46 Biểu thức chính qui (tt) Biểu thức chính qui (tt)  Liên kết giữa ngôn ngữ với BTCQ  00 là một biểu thức chính quy chỉ định tập L={00} Tập hợp các chuỗi được chỉ định bởi một BTCQ r được ký hiệu bởi L(r). Để cho *  (0+1) chỉ định tập mọi chuỗi 0 và 1 tiện ta dùng r vừa để chỉ biểu thức chính quy, vừa để chỉ tập hợp do nó chỉ  (1+10)* chỉ định tập mọi chuỗi 0 và 1, có con 1 ở đầu và không định. có hai con 0 liên tiếp.  Định nghĩa 2:  (0+)(1+10)* chỉ định tập mọi chuỗi 0 và 1 không chứa hai con 0 Ngôn ngữ L(r) được biểu thị bởi bất kỳ một BTCQ r nào, thì được định nghĩa bởi các qui tắc sau: liên tiếp. Cách khác (1+01)*(0+ ) 1.  là một biểu thức chính qui biểu thị tập rỗng. *  (0+1) 011 chỉ định tập mọi chuỗi 0, 1 kết thúc bởi 011. 2.  là một biểu thức chính qui biểu thị tập {}.  0*1*2* chỉ định tập mọi chuỗi gồm một số con 0, tiếp đến một số 3.  a  thì r = a là một biểu thức chính qui biểu thị tập con 1, rồi đến một số con 2. L(r) = {a}.  00*11*22* chỉ định tập các chuỗi trong đó 0, 1, 2 đều có mặt.  Nếu r và s là các BTCQ thì: Biểu thức đó thường được viết tắt là 0+1+2+. 4. L(r+s) = L (r)  L(s)  Ví dụ 3.8: Hãy xây dựng BTCQ xác định các chuỗi có chứa số 0 5. L(r.s) = L(r) L(s) và 1 xen kẻ nhau. 6. L((r)) = L(r) 7. L(r*) = (L(r))* 47 48 12
13. Biểu thức chính qui (tt) Biểu thức chính qui (tt)  Các tính chất đại số của biểu thức chính qui: Dễ dàng Giải thuật rằng, cho r, s, t là các biểu thức chính quy, thì ta có các đẳng thức sau, trong đó r = s có nghĩa là L(r) = L(s).  Ví dụ 3.8: cho BTCQ r = a* . (a+b)  Tìm ngôn ngữ L(r) gồm tất cả các chuỗi được chỉ định 1. r + s = s + r 8. r = r =  bởi r. 2. r + r = r 9. r +  = r Giải 3. r + (s + t) = (r + s) + t 10. * =   Ta có L(r) = L(a*. (a+b)) = L(a*) L(a+b)  = (L(a))* (L(a)  L(b)) 4. r(st) = (rs)t 11.(+r)* = r*  = {an | n 0} {a,b} 5. r(s + t) = rs + rt 12. r + r* = r*  = {an+1, anb | n 0 } 6. (r + s)t = rt + st 13.(r*)* = r* 7. r = r =r 14.(r*s*)* = (r + s)*. 49 50 Biểu thức chính qui (tt) Liên quan giữa BTCQ và OH  Ví dụ 3.9: Cho BTCQ r = (aa)* (bb)*b Biểu thị cho tập hợp tất cả các chuỗi sao cho có chẳn con chữ a theo sau là lẻ con chữ b. Đó là  Bổ đề 3.4: Với mọi tập hữu hạn L  *, đều tồn tại một một L(r) = {a2n b2m+1 | n,m 0 } BTCQ mà tập nó chỉ định là L.  Ví dụ 3.10: Cho  = {0,1}. Hãy xác định BTCQ r sao cho L(r) = {w * | w có ít nhất một cặp số 0 liên tiếp }  Định lý 3.9: Một ngôn ngữ L được chỉ định bởi một BTCQ khi và Phân tích: mỗi chuỗi w chứa tổi thiểu 00, trước và sau nó là tùy ý 0, 1 chỉ khi nó được đoán nhận bởi một Ôtômát hữu hạn. điều được. Ta đã biết một chuỗi tùy ý trên  = {0,1} được biểu thị bởi BTCQ là (0+1)* hoặc (1+0)* điều đúng. Vậy BTCQ cần tìm là r = (0+1)*00(1+0)* Ghi chú: Thông thường có vô số các BTCQ cho bất lỳ một ngôn ngữ nào. Nên kết quả tìm BTCQ không phải là duy nhất. 51 52 13
14. Thuật toán Thompson Thuật toán Thompson (tt)  Bài toán: Cho một biểu thức chính quy. Hãy xây dựng ôtômát  Sau đó áp dụng luật 1, luật 2 để xây dựng các ôtômát hữu hạn không đơn định đoán nhận ngôn ngữ chính quy từ không đơn định M , M , , M tương đương đoán nhận các biểu thức chính quy đã cho. 1 2 k ngôn ngữ L(r1), L(r2), , L(rk). Thuật toán:  Cuối cùng áp dụng luật 3 để xây dựng ôtômát không đơn  Vào: Một biểu thức chính quy r trên tập . định M đoán nhận ngôn ngữ L(r).  Ra: Một ôtômát hữu hạn không đơn định đoán nhận ngôn ngữ L(r). • Luật 1: BTCQ r=, ngôn ngữ biểu thị cho nó là L(r) = {}. Xây dựng OH đoán nhận L(r) như sau: Sau đây là thuật toán Thompson:  Trước hết tách biểu thức chính quy r thành các biểu thức Đầu  q q chính quy thành phần r1, r2, rk. 0 f 53 54 Thuật toán Thompson (tt) Thuật toán Thompson (tt) M(r)   • Luật 2: BTCQ r=a trên  ={a}, ngôn ngữ do nó sinh Đầu ra là L(r)= {a}. Xây dựng OH đoán nhận L(r) như sau: i f   M(s) Đầu a q q 0 f b. Đối với BTCQ (r).(s) thì OHK đoán nhận ngôn ngữ L(r).L(s) như sau: • Luật 3: Giả sử M(r), M(s) là các ôtômát thành phần tương ứng với các BTCQ s và r: Đầu M(r) M(s) a. Với BTCQ (r)  (s) ta xây dựng OH đoán nhận i f ngôn ngữ L(r)  L(s) như sau: 55 55 56 14
15. Thuật toán Thompson (tt) Bài tập: cho NNCQ xây dựng Ôtômát  Ví dụ 3.12: Xây dựng Ôtômát đoán nhận tất cả các chuỗi c. Đối với BTCQ (r)* thì OHK đoán nhận ngôn ngữ (L(r))* trên  = {a,b,0,1} sao cho kết thúc bởi ab như sau:   Ví dụ 3.13: Xây dựng Ôtômát đoán nhận tất cả các chuỗi thuộc {0, 1}* sao cho có chứa chuỗi con 01 đâu đó. Đầu  M(r)  i f  Ví dụ 3.14: Xây dựng Ôtômát đoán nhận ngôn ngữ  L={aabna | n 0}  Ví dụ 3.11: Xây dựng NFA từ biểu thức chính quy: 01*+1 57 58 15