Bài giảng Lí thuyết ngôn ngữ hình thức và ôtômát - Chương 2: Ngôn ngữ chính quy và ôtômát hữu hạn - Nguyễn Thị Minh Huyền

Lí thuyết ngôn ngữ hình thức và ôtômát Chương 2. Ngôn ngữ chính quy và ôtômát hữu hạn Nguyễn Thị Minh Huyền Khoa Toán - Cơ - Tin học Trường Đại học Khoa học Tự nhiên Hà Nội Ngôn ngữ chính quy Văn phạm chính quy Ôtômat hữu hạn Nguồn (đồ thị chuyển) Ch2. NN chính quy& ôtômát hữu hạn 1 / 37 Ôtômát hữu hạn Nội dung 1. Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Ôtômát hữu hạn, không đơn định Đơn định hoá ôtômát Bài tập 2. Tính đóng của lớp ngôn ngữ chính quy 3. Biểu thức chính quy 4. Điều kiện cần của ngôn ngữ chính quy 5. Điều kiện cần và đủ của ngôn ngữ chính quy Ch2. NN chính quy& ôtômát hữu hạn 2 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Ví dụ Dàn máy phát thanh: P (nút Power): 2 chế độ ON/OFF S (nút chọn nguồn phát): chuyển đổi giữa 3 chế độ CD/Tape/Radio. Chỉ thay đổi được trạng thái của S khi máy bật (P = ON). Khi tắt máy (P = OFF ), S không thay đổi giá trị Ban đầu, máy tắt và ở chế độ CD. Bài toán: Cho 1 dãy thao tác bấm nút P hoặc S. Dãy thao tác này có cho phép đưa máy về trạng thái bật và ở chế độ Radio không? Ch2. NN chính quy& ôtômát hữu hạn 3 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Định nghĩa hình thức Ôtômat hữu hạn, đơn định Bộ năm A = (S,Σ, s0, δ,F ) S: tập hữu hạn các trạng thái, S 6= ∅ Σ 6= ∅ : bảng chữ cái vào s0 ∈ S trạng thái khởi đầu F ⊆ S : tập trạng thái kết δ : S × Σ→ S : hàm chuyển trạng thái δ(p, a) = q : máy đang ở trạng thái p, nếu đọc được chữ cái vào a thì chuyển sang trạng thái q biểu diễn dạng bảng Ch2. NN chính quy& ôtômát hữu hạn 4 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Biểu diễn ôtômat Biểu diễn bằng đồ thị chuyển (nguồn) Đỉnh vào, đỉnh ra/kết, cung s1 s2 0 1 0 1 Ch2. NN chính quy& ôtômát hữu hạn 5 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Ngôn ngữ đoán nhận bởi ôtômat hữu hạn, đơn định Hàm chuyển mở rộng δˆ : S × Σ∗ → S δˆ(p, ) = p ∀p ∈ S,a ∈ Σ, y ∈ Σ∗ : δˆ(p,ay) = δˆ(δ(p,a), y) Ngôn ngữ đoán nhận bởi ôtômat A: L(A) = {x ∈ Σ∗|δˆ(s0, x) ∈ F} Ch2. NN chính quy& ôtômát hữu hạn 6 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Tương đương giữa ôtômat và văn phạm chính quy Ôtômat hữu hạn, đơn định A tương đương văn phạm chính quy G: L(A) = L(G) Chuyển từ ôtômat sang văn phạm chính quy Chuyển từ văn phạm chính quy sang ôtômat G = ({a,b, c}, {S,A,B},S,P), P gồm các quy tắc: S → aA|bA|cB A→ cA|aB B → bB|a|c Ch2. NN chính quy& ôtômát hữu hạn 7 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Bài tập Cho bảng chữ cái Σ = {a,b, c}, xây dựng ôtômat đoán nhận các ngôn ngữ sau: 1. L1 = {an|n ≥ 2} 2. L2 = {x ∈ Σ∗||x | ≥ 1} 3. L3 = {ambnck |m ≥ 1,n ≥ 0, k ≥ 2} 4. L4 = {x ∈ Σ∗||x | lẻ} Ch2. NN chính quy& ôtômát hữu hạn 8 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, không đơn định Ôtômát hữu hạn, không đơn định Khác với ôtômat đơn định ở hàm chuyển: δ : S × (Σ ∪ {})→ 2S δ(p,a) ⊆ S Biểu diễn bằng đồ thị (nguồn): Đỉnh vào, đỉnh ra/kết, cung rỗng, cung cốt yếu, đỉnh cốt yếu (có cung cốt yếu đi vào) Ngôn ngữ đoán nhận bởi ôtômat không đơn định: Mở rộng hàm chuyển như ôtômat đơn định L(A) = {x ∈ Σ∗|δ(s0, x) ∩ F 6= ∅} Ch2. NN chính quy& ôtômát hữu hạn 9 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, không đơn định Một số khái niệm, tính chất Đơn định: hàm chuyển đơn trị Đầy đủ: hàm chuyển xác định khắp nơi Đơn định và đầy đủ: Trong bảng hàm chuyển mọi ô đều có 1 trạng thái 2 ôtômat/nguồn tương đương: đoán nhận/sinh cùng một ngôn ngữ Ôtômat đơn định tương đương với ôtômat không đơn định? Ch2. NN chính quy& ôtômát hữu hạn 10 / 37 Ôtômát hữu hạn Đơn định hoá ôtômát Đơn định hoá nguồn Cho nguồn không đơn định A. Xây dựng nguồn đơn định, đầy đủ A′ tương đương với A Kí hiệu: S(A) – tập tất cả các đỉnh, F (A) - tập đỉnh ra, D(A) – tập đỉnh cốt yếu N(p,q) : tập các từ đi từ đỉnh p đến đỉnh q Cho a ∈ Σ, δ(p,a) = {q ∈ D(A)|a ∈ N(p,q)} δ(M ,a) = {∪δ(p,a),p ∈ M}, M ⊂ D(A) s′0 = {s0} Tập đỉnh của A′: ∀M ∈ S(A′) đã xác định, a ∈ Σ, bổ sung cung ghi chữ cái a tới đỉnh δ(M ,a) Tập đỉnh kết: F (A′) = {M ∈ S(A′)|M ∩ F (A) 6= ∅} Ch2. NN chính quy& ôtômát hữu hạn 11 / 37 Ôtômát hữu hạn Đơn định hoá ôtômát Đơn định hóa ôtômat Cho ôtômat không đơn định A. Xây dựng ôtômat đơn định, đầy đủ A′ tương đương với A A = (S,Σ, s0, δ,F ). Giả sử ∀s ∈ S, δ(s, ) = ∅ Xây dựng T : 2S × Σ→ 2S ∀s ∈ S,∀a ∈ Σ,T (s,a) = {s′ ∈ S|s′ ∈ δ(s,a)} ∀B ⊆ S,∀a ∈ Σ,T (B,a) = {∪T (s,a)|s ∈ B} A′ = (S′,Σ, {s0}, δ′,F ′) S′ ⊆ 2S, xây dựng trong quá trình xây dựng hàm T ∀p ∈ S′: δ′(p,a) = T (p,a) F ′ = {p ∈ S′|p ∩ F 6= ∅} Ch2. NN chính quy& ôtômát hữu hạn 12 / 37 Ôtômát hữu hạn Đơn định hoá ôtômát Tóm tắt lại Ngôn ngữ chính quy có thể sinh/đoán nhận bởi: văn phạm chính quy ôtômat hữu hạn (luôn đưa về được dạng đơn định, đầy đủ) nguồn/đồ thị chuyển (luôn đưa về được dạng đơn định, đầy đủ) Ch2. NN chính quy& ôtômát hữu hạn 13 / 37 Ôtômát hữu hạn Bài tập Bài tập Xây dựng ôtômat đoán nhận một ngôn ngữ đã cho 1. Xây dựng 3 ôtômat đoán nhận các tập các số tự nhiên chia hết cho 2, cho 3 và cho 5. 2. Xây dựng ôtômat mô phỏng máy bán nước tự động dùng tiền xu (1000, 2000, 5000). Giá 1 lon nước ngọt là 5000, 1 chai nước suối là 3000. Ch2. NN chính quy& ôtômát hữu hạn 14 / 37 Tính đóng của lớp ngôn ngữ chính quy Nội dung 1. Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Ôtômát hữu hạn, không đơn định Đơn định hoá ôtômát Bài tập 2. Tính đóng của lớp ngôn ngữ chính quy 3. Biểu thức chính quy 4. Điều kiện cần của ngôn ngữ chính quy 5. Điều kiện cần và đủ của ngôn ngữ chính quy Ch2. NN chính quy& ôtômát hữu hạn 15 / 37 Tính đóng của lớp ngôn ngữ chính quy Các phép toán trên nguồn Trang 53 -> 66 (giáo trình) Phép lấy phần bù Phép hợp Phép giao Phép lấy tích ghép Phép soi gương Phép lặp, lặp cắt Phép chia trái, chia phải Ch2. NN chính quy& ôtômát hữu hạn 16 / 37 Tính đóng của lớp ngôn ngữ chính quy Tính đóng của lớp ngôn ngữ chính quy Lớp ngôn ngữ chính quy đóng với các tất cả phép toán trên ngôn ngữ: hợp, giao, lấy phần bù, tích ghép, lặp, lặp cắt, soi gương, chia trái, chia phải. Ch2. NN chính quy& ôtômát hữu hạn 17 / 37 Biểu thức chính quy Nội dung 1. Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Ôtômát hữu hạn, không đơn định Đơn định hoá ôtômát Bài tập 2. Tính đóng của lớp ngôn ngữ chính quy 3. Biểu thức chính quy 4. Điều kiện cần của ngôn ngữ chính quy 5. Điều kiện cần và đủ của ngôn ngữ chính quy Ch2. NN chính quy& ôtômát hữu hạn 18 / 37 Biểu thức chính quy Biểu thức chính quy (Regular expression) Định nghĩa (quy nạp) Cho Σ = {a1,a2, . . . ,an} Cơ sở quy nạp: B = ai , B = , B = ∅ là các biểu thức chính quy, biểu diễn các ngôn ngữ {ai}, {}, ∅ Quy nạp: Cho B1,B2 là các biểu thức chính quy Khi đó B1.B2,B1 ∪ B2,B∗1 , (B1) cũng là các biểu thức chính quy Chỉ có các biểu thức được xác định như trên mới là các biểu thức chính quy trên bảng chữ cái Σ Ch2. NN chính quy& ôtômát hữu hạn 19 / 37 Biểu thức chính quy Biểu thức chính quy – nguồn Xây dựng nguồn tương đương với biểu thức chính quy Cơ sở quy nạp: Nguồn sinh {a}, {}, ∅ Các phép toán: hợp, tích ghép, lặp: phép toán trên nguồn Xây dựng biểu thức chính quy tương đương với nguồn Đường đi thông thường: tích ghép, hợp Chu trình: lặp Ch2. NN chính quy& ôtômát hữu hạn 20 / 37 Biểu thức chính quy Biểu thức chính quy Ngôn ngữ chính quy⇔ Biểu thức chính quy Biểu thức chính quy trong lập trình Tìm kiếm xâu theo mẫu (pattern) nào đó VD: Xử lí gộp tên tệp Tìm kiếm trong Unix/Linux Tìm kiếm, thay thế xâu trong emacs Công cụ xử lí xâu trong các ngôn ngữ lập trình Ch2. NN chính quy& ôtômát hữu hạn 21 / 37 Biểu thức chính quy Bài tập ứng dụng biểu thức chính quy Cú pháp phổ biến của biểu thức chính quy Mỗi kí tự biểu diễn chính nó, trừ các kí tự điều khiển (metacharacter): ? + - * . { } [ ] ( ) \ | ˆ $ Để biểu diễn các kí tự điều khiển, thêm dấu \ vào trước [03a−c] ≡ {0,3,a,b, c}, [ˆ15] ≡ tập các kí tự khác 1 và 5 . biểu diễn kí tự bất kì, ˆ và $ đánh dấu đầu và cuối dòng \ đánh dấu đầu và cuối từ, \b đánh dấu biên từ, \B đánh dấu xâu rỗng không ở biên từ Phép lặp: ?, *, +, {n}, {n, }, {n,m} Phép lấy tích ghép, phép hợp | \n biểu diễn xâu con nằm giữa cặp () thứ n trước đó. Ch2. NN chính quy& ôtômát hữu hạn 22 / 37 Biểu thức chính quy Bài tập ví dụ về RE Viết biểu thức chính quy theo cú pháp trên để tìm các xâu sau trong các tệp : (a) Từ language (b) Các dòng trong đó từ language xuất hiện ít nhất 2 lần (c) Các số thập phân Ch2. NN chính quy& ôtômát hữu hạn 23 / 37 Biểu thức chính quy Bài tập ví dụ về RE và FSA (Finite State Automata) Xác định biểu thức chính quy và ôtômat đơn định hữu hạn đoán nhận các ngôn ngữ : (i) Tập số thực dấu phẩy động (ii) Tập các xâu gồm các chữ số 0-9 có chứa xâu con 11 (iii) Tập ngày tháng theo định dạng ngày(2 chữ số)/tháng(2 chữ số). Chú ý ràng buộc số ngày trong tháng. Ch2. NN chính quy& ôtômát hữu hạn 24 / 37 Điều kiện cần của ngôn ngữ chính quy Nội dung 1. Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Ôtômát hữu hạn, không đơn định Đơn định hoá ôtômát Bài tập 2. Tính đóng của lớp ngôn ngữ chính quy 3. Biểu thức chính quy 4. Điều kiện cần của ngôn ngữ chính quy 5. Điều kiện cần và đủ của ngôn ngữ chính quy Ch2. NN chính quy& ôtômát hữu hạn 25 / 37 Điều kiện cần của ngôn ngữ chính quy Điều kiện cần của ngôn ngữ chính quy: Bổ đề bơm Ứng dụng: Khẳng định một ngôn ngữ không phải là chính quy Ôtômat tối tiểu: Trong các ôtômat đơn định, đầy đủ đoán nhận một ngôn ngữ chính quy, gọi các ôtômat có số trạng thái ít nhất là các ôtômat tối tiểu Điều kiện cần: Giả sử L là ngôn ngữ chính quy Luôn tồn tại l ∈ N+: ∀z ∈ L, |z| > l thì tìm được 3 từ u, x , v (|x | ≥ 1) để z = uxv ∀n = 0, 1, 2 · · · : zn = uxnv ∈ L Ch2. NN chính quy& ôtômát hữu hạn 26 / 37 Điều kiện cần của ngôn ngữ chính quy Chứng minh L - ngôn ngữ chính quy, đoán nhận được bởi một otomat tối tiểu có n trạng thái Chọn l = n, xét từ z ∈ L, với |z| = m > l Đặt δ(s0,a1) = st,1, δ(st,1,a2) = st,2, · · · δ(st,m−1,am) = st,m Vì m > l nên ∃i < j : st,i = st,j Đặt u = a1 · · · ai , x = ai+1 · · · aj , v = aj+1 · · · am Khi đó δ(s0,u) = δ(s0,ux) = δ(s0,uxn) ∀n ≥ 0 ⇔ δ(s0,uv) = δ(s0,uxv) = δ(s0,uxnv) ∀n ≥ 0 ⇔ ∀n ≥ 0: zn = uxnv ∈ L. Ch2. NN chính quy& ôtômát hữu hạn 27 / 37 Điều kiện cần của ngôn ngữ chính quy Ứng dụng Áp dụng chứng minh một ngôn ngữ không phải là chính quy L1 = {ap|p nguyên tố} Giả sử L1 chính quy⇒ ∀p nguyên tố đủ lớn, ∃m, k ≥ 0,n ≥ 1: p = m + n + k , thoả mãn ∀i ≥ 0, aman∗iak ∈ L1. Chọn i = p + 1 = m + n + k + 1, có aman∗iak = aman∗(m+n+k+1)ak = ap(n+1) ∈ L1 ⇒ mâu thuẫn L2 = {anbn|n ≥ 1} Giả sử L2 chính quy, ∀n đủ lớn, ∃u, x , v ∈ {a,b}∗, |x | > 0: uxv = anbn và ∀i ≥ 0, ux iv ∈ L2 Xét 3 trường hợp x là từ con của an, x là từ con của bn, x chứa cả a và b để đưa đến kết luận mâu thuẫn. Ch2. NN chính quy& ôtômát hữu hạn 28 / 37 Điều kiện cần của ngôn ngữ chính quy Ứng dụng Áp dụng chứng minh một ngôn ngữ không phải là chính quy L1 = {ap|p nguyên tố} Giả sử L1 chính quy⇒ ∀p nguyên tố đủ lớn, ∃m, k ≥ 0,n ≥ 1: p = m + n + k , thoả mãn ∀i ≥ 0, aman∗iak ∈ L1. Chọn i = p + 1 = m + n + k + 1, có aman∗iak = aman∗(m+n+k+1)ak = ap(n+1) ∈ L1 ⇒ mâu thuẫn L2 = {anbn|n ≥ 1} Giả sử L2 chính quy, ∀n đủ lớn, ∃u, x , v ∈ {a,b}∗, |x | > 0: uxv = anbn và ∀i ≥ 0, ux iv ∈ L2 Xét 3 trường hợp x là từ con của an, x là từ con của bn, x chứa cả a và b để đưa đến kết luận mâu thuẫn. Ch2. NN chính quy& ôtômát hữu hạn 28 / 37 Điều kiện cần của ngôn ngữ chính quy Ứng dụng Áp dụng chứng minh một ngôn ngữ không phải là chính quy L1 = {ap|p nguyên tố} Giả sử L1 chính quy⇒ ∀p nguyên tố đủ lớn, ∃m, k ≥ 0,n ≥ 1: p = m + n + k , thoả mãn ∀i ≥ 0, aman∗iak ∈ L1. Chọn i = p + 1 = m + n + k + 1, có aman∗iak = aman∗(m+n+k+1)ak = ap(n+1) ∈ L1 ⇒ mâu thuẫn L2 = {anbn|n ≥ 1} Giả sử L2 chính quy, ∀n đủ lớn, ∃u, x , v ∈ {a,b}∗, |x | > 0: uxv = anbn và ∀i ≥ 0, ux iv ∈ L2 Xét 3 trường hợp x là từ con của an, x là từ con của bn, x chứa cả a và b để đưa đến kết luận mâu thuẫn. Ch2. NN chính quy& ôtômát hữu hạn 28 / 37 Điều kiện cần của ngôn ngữ chính quy Ứng dụng Áp dụng chứng minh một ngôn ngữ không phải là chính quy L1 = {ap|p nguyên tố} Giả sử L1 chính quy⇒ ∀p nguyên tố đủ lớn, ∃m, k ≥ 0,n ≥ 1: p = m + n + k , thoả mãn ∀i ≥ 0, aman∗iak ∈ L1. Chọn i = p + 1 = m + n + k + 1, có aman∗iak = aman∗(m+n+k+1)ak = ap(n+1) ∈ L1 ⇒ mâu thuẫn L2 = {anbn|n ≥ 1} Giả sử L2 chính quy, ∀n đủ lớn, ∃u, x , v ∈ {a,b}∗, |x | > 0: uxv = anbn và ∀i ≥ 0, ux iv ∈ L2 Xét 3 trường hợp x là từ con của an, x là từ con của bn, x chứa cả a và b để đưa đến kết luận mâu thuẫn. Ch2. NN chính quy& ôtômát hữu hạn 28 / 37 Điều kiện cần của ngôn ngữ chính quy Ứng dụng Áp dụng chứng minh một ngôn ngữ không phải là chính quy L1 = {ap|p nguyên tố} Giả sử L1 chính quy⇒ ∀p nguyên tố đủ lớn, ∃m, k ≥ 0,n ≥ 1: p = m + n + k , thoả mãn ∀i ≥ 0, aman∗iak ∈ L1. Chọn i = p + 1 = m + n + k + 1, có aman∗iak = aman∗(m+n+k+1)ak = ap(n+1) ∈ L1 ⇒ mâu thuẫn L2 = {anbn|n ≥ 1} Giả sử L2 chính quy, ∀n đủ lớn, ∃u, x , v ∈ {a,b}∗, |x | > 0: uxv = anbn và ∀i ≥ 0, ux iv ∈ L2 Xét 3 trường hợp x là từ con của an, x là từ con của bn, x chứa cả a và b để đưa đến kết luận mâu thuẫn. Ch2. NN chính quy& ôtômát hữu hạn 28 / 37 Điều kiện cần và đủ của ngôn ngữ chính quy Nội dung 1. Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy Ôtômát hữu hạn, không đơn định Đơn định hoá ôtômát Bài tập 2. Tính đóng của lớp ngôn ngữ chính quy 3. Biểu thức chính quy 4. Điều kiện cần của ngôn ngữ chính quy 5. Điều kiện cần và đủ của ngôn ngữ chính quy Ch2. NN chính quy& ôtômát hữu hạn 29 / 37 Điều kiện cần và đủ của ngôn ngữ chính quy Quan hệ tương đương bất biến phải Cho tập X 6= ∅ và quan hệ hai ngôi T (x , y) trên X . T là quan hệ tương đương: phản xạ, đối xứng, bắc cầu ⇒ T chia X thành các lớp tương đương X1,X2, · · · ,Xm, lập thành phân hoạch của X theo quan hệ T (các tập Xi khác rỗng, rời nhau, hợp với nhau bằng tập X ). Khi đó m (có thể hữu hạn hoặc vô hạn) gọi là chỉ số của quan hệ tương đương T . Ví dụ m hữu hạn: Quan hệ đồng dư cho n > 0 trên tập số tự nhiên. Ví dụ m vô hạn: Quan hệ có cùng số chữ số trên tập số tự nhiên. Quan hệ tương đương bất biến phải: ∀z ∈ X , nếu T (x , y)⇒ T (xz, yz). Ch2. NN chính quy& ôtômát hữu hạn 30 / 37 Điều kiện cần và đủ của ngôn ngữ chính quy Quan hệ tương đương bất biến phải RL Cho ngôn ngữ L ⊆ Σ∗, x , y ∈ Σ∗ được gọi là có quan hệ RL (x RL y)nếu x và y không có hậu tố phân biệt z nào: ∀z ∈ Σ∗ : xz ∈ L⇔ yz ∈ L Ví dụ: Cho L = (00)+ 00RL0000 01RL001 RL là một quan hệ tương đương bất biến phải Cho một ôtômat đơn định, đầy đủ đoán nhận ngôn ngữ L chính quy, 2 từ x , y ∈ Σ∗ thoả mãn δ(s0, x) = δ(s0, y) có quan hệ RL. Ch2. NN chính quy& ôtômát hữu hạn 31 / 37 Điều kiện cần và đủ của ngôn ngữ chính quy Quan hệ RL: Ví dụ Kí hiệu [x]: lớp từ tương đương bất biến phải theo quan hệ RL với x trên Σ∗ Ví dụ, cho L = (00)+ [] = {} [0] = 0(00)∗ [1] = 0∗1(0|1)∗ [00] = (00)+ Ch2. NN chính quy& ôtômát hữu hạn 32 / 37 Điều kiện cần và đủ của ngôn ngữ chính quy Định lí Myhill-Nerode (điều kiện cần và đủ của ngôn ngữ chính quy) L là ngôn ngữ chính quy⇔ L là hợp của một số lớp tương đương theo quan hệ tương đương bất biến phải với chỉ số hữu hạn trên tập Σ∗. Chứng minh điều kiện cần: L chính quy⇒ L đoán nhận được bởi ôtômat đơn định, đầy đủ A = (S,Σ, s0, δ,F ) Xây dựng quan hệ tương đương bất biến phải T : T (x , y)⇔ δ(s0, x) = δ(s0, y) Chỉ số của T : T chia Σ∗ thành phân hoạch X1, · · · ,Xm Giả sử x ∈ Xi và δ(s0, x) = sti : Xi gắn với trạng thái sti A hữu hạn trạng thái nên m hữu hạn (không vượt quá |S|) Xét tất cả các lớp tương đương Xi1 , · · · ,Xin : Xij ∩ L 6= ∅ Chứng minh được L = ∪Xij (j = 1, · · · ,n) Ch2. NN chính quy& ôtômát hữu hạn 33 / 37 Điều kiện cần và đủ của ngôn ngữ chính quy Định lí Myhill-Nerode (tiếp) Chứng minh điều kiện đủ Có quan hệ T chia Σ∗ thành phân hoạch X1, · · · ,Xm. L là hợp của một số lớp Xi . Xây dựng ôtômat A = (S,Σ, s0, δ,F ) : Kí hiệu lớp có chứa từ p là [p], lớp chứa từ rỗng [] Xây dựng S = {X1, · · · ,Xm} s0 = [], F = {[p] | p ∈ L} δ([p], a) = [pa] A đoán nhận L Nhận xét: Số trạng thái của S bằng chỉ số của T ⇒ A là ôtômat tối tiểu sinh L. Ch2. NN chính quy& ôtômát hữu hạn 34 / 37 Điều kiện cần và đủ của ngôn ngữ chính quy Ứng dụng định lí Myhill-Nerode Xét tính chính quy của một ngôn ngữ Xây dựng ôtômat tối tiểu Ch2. NN chính quy& ôtômát hữu hạn 35 / 37 Điều kiện cần và đủ của ngôn ngữ chính quy Xét tính chính quy của ngôn ngữ Các ví dụ sau đều xét Σ = {0,1} L1 = {0n1n|n ≥ 1} L2 = {x |x = xR}, xR : từ ngược của x L3 = {xwx |x ∈ {0,1},w ∈ (0|1)+} Ch2. NN chính quy& ôtômát hữu hạn 36 / 37