›
›

Bài giảng Lý thuyết Ôtômát và ngôn ngữ hình thức - Hồ Văn Quân

pdf 316 trang hapham 2870
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết Ôtômát và ngôn ngữ hình thức - Hồ Văn Quân", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ly_thuyet_otomat_va_ngon_ngu_hinh_thuc_ho_van_quan.pdf

Nội dung text: Bài giảng Lý thuyết Ôtômát và ngôn ngữ hình thức - Hồ Văn Quân

  1. Trường Đại học Bách khoa Khoa Công Nghệ Thông Tin BÀI GIẢNG MÔN HỌC LÝ THUYẾT ÔTÔMÁT & NNHT Giảng Viên: Hồ Văn Quân E-mail: hcquan@dit.hcmut.edu.vn Web site:
  2. NỘI DUNG MÔN HỌC „ Chương 1 Giới thiệu về lý thuyết tính toán „ Chương 2 Ôtômát hữu hạn „ Chương 3 Ngôn ngữ chính qui và văn phạm chính qui „ Chương 4 Các tính chất của ngôn ngữ chính qui „ Chương 5 Ngôn ngữ phi ngữ cảnh „ Chương 6 Đơn giản hóa văn phạm phi ngữ cảnh và các dạng chuẩn „ Chương 7 Ôtômát đẩy xuống „ Chương 8 Các tính chất của ngôn ngữ phi ngữ cảnh „ Chương 9 Máy Turing Trang 2 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  3. TÀI LIỆU THAM KHẢO 1. Bài giảng lý thuyết Ngôn ngữ Hình thức và Automat - Hồ Văn Quân [2002]. 2. An Introduction to Formal Languages and Automata - Peter Linz [1990]. Trang 3 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  4. HÌNH THỨC ĐÁNH GIÁ „ Sẽ có thông báo cụ thể cho từng khóa học. Tuy nhiên, thường là như được cho bên dưới. „ Thi trắc nghiệm „ Thời gian: 120 phút „ Số lượng: 50 câu „ Được phép xem tài liệu trong 4 tờ giấy A4 „ Làm bài tập lớn cộng điểm (không bắt buộc) „ Nộp bài tập lớn và báo cáo vào cuối học kỳ „ Cộng tối đa 2 điểm Trang 4 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  5. CÁC MÔN LIÊN QUAN „ Ngôn ngữ lập trình „ Trình biên dịch (*) „ Toán tin học Trang 5 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  6. Chương 1 Giới thiệu về lý thuyết tính toán 1.1 Giới thiệu 1.2 Yêu cầu về kiến thức nền 1.3 Ba khái niệm cơ bản „ Ngôn ngữ (languages) „ Văn phạm (grammar) „ Ôtômát (máy tự động) 1.4 Một vài ứng dụng Trang 6 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  7. Giới thiệu „ Ôtômát „ Các mô hình tính toán tự động „ Ngôn ngữ hình thức (formal languages): „ Định nghĩa „ Phân loại ngôn ngữ „ Quan hệ với ôtômát „ Ứng dụng vào việc xây dựng các ngôn ngữ lập trình „ Trang 7 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  8. Yêu cầu về kiến thức nền „ Lý thuyết „ Tập hợp „ Đồ thị „ Kỹ thuật chứng minh „ Qui nạp „ Phản chứng „ Kỹ thuật mô phỏng Trang 8 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  9. Ba khái niệm cơ bản „ Ngôn ngữ (languages) „ Văn phạm (grammar) „ Ôtômát (automata) Trang 9 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  10. Ngôn ngữ „ Ngôn ngữ là gì? „ Các từ điển định nghĩa ngôn ngữ một cách không chính xác là một hệ thống thích hợp cho việc 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 qui tắc để vận dụng chúng. „ Định nghĩa trên chưa đủ chính xác để nghiên cứu về NNHT „ Chúng ta cần xây dựng một định nghĩa toán học cho khái niệm ngôn ngữ Trang 10 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  11. Các khái niệm „ Bảng chữ cái (alphabet), Σ „ Là tập hợp Σ hữu hạn không trống các kí hiệu (symbol). „ Ví dụ „ {A, B, C, , Z}: Bảng chữ cái La tinh. „ {α, β, γ, , ϕ}: Bảng chữ cái Hi Lạp. „ {0, 1, 2, , 9}: Bảng chữ số thập phân. „ {I, V, X, L, C, D, M}: Bảng chữ số La Mã. Trang 11 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  12. Các khái niệm (tt) „ Chuỗi (string), w „ Là một dãy hữu hạn các kí hiệu từ bảng chữ cái. „ Ví dụ „ Với Σ = {a, b}, thì abab và aaabbba là các chuỗi trên Σ. „ Qui ước „ Với một vài ngoại lệ, chúng ta sẽ sử dụng các chữ cái thường a, b, c, . . . cho các phần tử của Σ còn các chữ cái u, v, w, . . . cho các tên chuỗi. Trang 12 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  13. Các phép toán trên chuỗi „ Kết nối (concatenation), wv „ w = a1a2 an và v = b1b2 bm là chuỗi: wv = a1a2 anb1b2 bm „ Ðảo (reverse), wR „ Ðảo của chuỗi w = a1a2 an là chuỗi: R w = an a2a1 Trang 13 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  14. Các khái niệm (tt) Cho chuỗi w = uv „ Tiếp đầu ngữ (prefix) „ u được gọi là tiếp đầu ngữ của w „ Tiếp vĩ ngữ (suffix) „ v được gọi lá tiếp vĩ ngữ của w „ Chiều dài của chuỗi w „ Là số kí hiệu trong chuỗi, và được kí hiệu là |w| „ Chuỗi trống (empty string) „ Là chuỗi không có kí hiệu nào, thường được kí hiệu là λ Trang 14 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  15. Các khái niệm (tt) „ Nhận xét 1 . Các quan hệ sau đây đúng với mọi w: |λ| = 0; λw = wλ = w 2 . Nếu u, v là các chuỗi thì : |uv| = |u| + |v| „ Lũy thừa (power), wn n „ w là một chuỗi thì w là một chuỗi nhận được bằng cách kết nối chuỗi w với chính nó n lần. n 0 w = w w „ w = λ 12L3 n laàn Trang 15 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  16. Các khái niệm (tt) „ Σ*, Σ+ (bao đóng sao và bao đóng dương) „ Σ* là tập tất cả các chuỗi trên Σ kể cả chuỗi trống. + „ Σ là tập tất cả các chuỗi trên Σ ngoại trừ chuỗi trống. + + „ Σ* = Σ ∪ {λ} ; Σ = Σ* - {λ} „ Σ thì hữu hạn còn Σ+ và Σ* là vô hạn đếm được Trang 16 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  17. Định nghĩa ngôn ngữ „ Ngôn ngữ „ Là một tập con của Σ*, hay nói cách khác là một tập bất kỳ các câu trên bộ chữ cái. „ Ví dụ „ Cho Σ = {a, b} Σ* = {λ, a, b, aa, ab, ba, bb, aaa, aab, } „ Tập {a, aa, aab} là một ngôn ngữ trên Σ. Nó là một ngôn ngữ hữu hạn. n n „ Tập L = {a b : n ≥ 0} cũng là một ngôn ngữ trên Σ. Nó là một ngôn ngữ vô hạn. Trang 17 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  18. Các phép toán trên ngôn ngữ „ Bù (complement), L „ Bù của ngôn ngữ L trên bảng chữ cái Σ, được kí hiệu là: L = Σ* - L „ Kết nối, L1L2 „ Cho 2 ngôn ngữ L1, L2. Kết nối của 2 ngôn ngữ L1, L2 là: L1L2 = { xy : x ∈ L1 , y ∈ L2 } „ Lũy thừa, Ln n „ Lũy thừa bậc n của L, kí hiệu là L , là việc kết nối L với chính nó n lần 0 „ L = {λ} Ln = L L 12L3 n laàn Trang 18 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  19. Các phép toán trên ngôn ngữ (tt) „ Ví dụ n n „ Cho L = {a b : n ≥ 0}, thì L2 = {anbnambm : n ≥ 0 , m ≥ 0} „ Bao đóng-sao (star-closure) của L „ Kí hiệu là L* và được định nghĩa là L* = L0 ∪ L1 ∪ L2 ∪ „ Bao đóng dương (positive closure) của L + „ Kí hiệu là L L+ = L1 ∪ L2 ∪ L3 ∪ Trang 19 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  20. Văn phạm „ 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 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 liên kết các từ lại thành câu. „ Ví dụ „ Cho đoạn văn phạm tiếng Anh sau → , → , → , → a | the, → boy | dog, → runs | walks, Trang 20 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  21. Định nghĩa văn phạm „ Các câu “a boy runs”và“the dog walks”làcó"dạng đúng“, tức là được sinh ra từ các luật của văn phạm. „ Định nghĩa 1.1 „ Văn phạm G được định nghĩa như là một bộ bốn G = (V, T, S, P) „ V: tập các kí hiệu không kết thúc (nonterminal symbol), còn được gọi là các biến (variable), „ T: tập các kí hiệu kết thúc (terminal symbol), „ S ∈ V: được gọi là biến khởi đầu (start variable), đôi khi còn được gọi là kí hiệu mục tiêu, „ P: tập hữu hạn các luật sinh (production), Trang 21 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  22. Định nghĩa văn phạm (tt) + „ Các luật sinh có dạng x → y trong đó x ∈ (V ∪ T) và có chứa ít nhất một biến, y ∈ (V ∪ T)*. „ 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) . „ Ví dụ „ Cho văn phạm sau: G = ({S, A, B}, {a, b}, S, P), với P: S → aAS | bBS | λ, A → aaA | b, B → bbB | a, Trang 22 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  23. Văn phạm (tt) „ Qui ước: „ 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ừ phi đượ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 biểu thị các kí hiệu kết thúc (terminal). „ Các kí tự chữ hoa X, Y, Z biểu thị các kí hiệu có thể là terminal hoặc biến. „ Các kí tự chữ thường u, v, w, x, y, z biểu thị chuỗi các terminal. „ Các kí tự chữ thường Hi Lạp α, β, γ biểu thị chuỗi các biến và các terminal. Trang 23 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  24. Các khái niệm „ Dẫn xuất trực tiếp (directly derive), ⇒ „ Cho luật sinh x → y và chuỗi w = uxv . „ Luật sinh trên có thể áp dụng tới chuỗi w. Khi áp dụng ta sẽ nhận được chuỗi mới z = uyv „ w dẫn xuất ra z hay ngược lại z được dẫn xuất ra từ w và kí hiệu là: uxv ⇒ uyv Trang 24 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  25. Ngôn ngữ được sinh ra bởi văn phạm * + „ Dẫn xuất gián tiếp ⇒ , ⇒ „ Nếu w1 ⇒ w2 ⇒ ⇒ wn thì ta nói w1 dẫn xuất ra wn và viết * w1 ⇒ wn „ Nếu có ít nhất một luật sinh phải được áp dụng chúng ta viết: + w1 ⇒ wn „ Định nghĩa 1.2 „ Cho G = (V, T, S, P) là một văn phạm, thì tập: L(G) = {w ∈ T* : Sw⇒* } được gọi là ngôn ngữ được sinh ra bởi G. Trang 25 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  26. Các khái niệm (tt) „ Sự dẫn xuất câu (derivation) „ Nếu w ∈ L(G) thì phải tồn tại dãy dẫn xuất: S ⇒ w1 ⇒ w2 ⇒ ⇒ wn ⇒ w Dãy này được gọi là một sự dẫn xuất câu của w. „ Dạng câu (sentential forms) „ Dãy S, w1, w2, , wn được gọi là các dạng câu của sự dẫn xuất. Câu w cũng được xem là một dạng câu đặc biệt. „ Ví dụ „ Cho văn phạm G = ({S}, { a, b}, S, P), với P S → aSb | λ. Trang 26 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  27. Các khái niệm (tt) „ Thì S ⇒ aSb ⇒ aaSbb ⇒ aabb là một dãy dẫn xuất.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} . Trang 27 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  28. Bài tập văn phạm „ Mô tả toán học cho ngôn ngữ „ Ngôn ngữ L1 bao gồm các chuỗi từ khóa begin, end của ngôn ngữ Pascal. Các chuỗi biểu diễn cấu trúc lồng nhau của các cặp từ khóa này trong các chương trình trên ngôn ngữ Pascal. „ Ngôn ngữ L2 bao gồm tập các danh hiệu của Pascal. „ Xác định ngôn ngữ của văn phạm „ G1 S → aSbS | bSaS | λ „ G2 E → E + T | T T → T * F | F F → (E) | a | b Trang 28 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  29. Bài tập văn phạm (tt) „ Xây dựng văn phạm cho ngôn ngữ „ Ngôn ngữ L1 và L2 ở trang trên R * „ L3 = {ww : w ∈ {a, b} } n m n+m „ L4 = {a b c : n, m ≥ 0} n n+m m „ L5 = {a b c : n, m ≥ 0} Trang 29 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  30. Ôtômát „ Ôtômát là gì? „ Ôtômát, dịch nghĩa là máy tự động, là thiết bị có thể tự thực hiện công việc mà không cần sự can thiệp của con người. „ Nó hoạt động dựa trên một số quy tắc và dựa vào các quy tắc này con người lập trình cho nó hoạt động theo ý muốn của mình. „ Máy tính số ngày nay chính là một máy tự động điển hình và mạnh nhất hiện nay. Trang 30 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  31. Định nghĩa ôtômát „ Ôtômát „ Là một mô hình trừu tượng của máy tính số bao gồm các thành phần chủ yếu sau Input file Control unit Storage Output Trang 31 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  32. Định nghĩa ôtômát (tt) „ 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ó. 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 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). Trang 32 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  33. Hoạt động của ôtômát „ Đơn vị điều khiển (control unit): mỗi ôtômát có một đơn vị điều khiển, cái 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 đó. „ Hoạt động của ôtômát „ Một ôtômát được giả thiết là hoạt động trong một khung thời gian rời rạc (discrete time frame). „ Tại một thời điểm bất kỳ đã cho, đơn vị điều khiển đang ở trong một trạng thái nội (internal state) nào đó, và cơ cấu nhập là đang quét (scanning) một kí hiệu cụ thể nào đó trên input file. Trang 33 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  34. Hoạt động của ôtômát (tt) „ Trạng thái nội của đơn vị điều khiển tại thời điểm kế tiếp được xác định bởi trạng thái kế (next state) hay bởi hàm chuyển trạng thái (transition function). „ Trong suốt quá trình chuyển trạng thái từ khoảng thời gian 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. Trang 34 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  35. Các khái niệm „ 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. „ 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à nó sẽởvào tại thời điểm kế tiếp. „ Hàm chuyển trạng thái (transition function): là hàm gởi ra trạng thái 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 quét, và thông tin hiện hành trong bộ nhớ tạm. Trang 35 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  36. Các khái niệm (tt) „ 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 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 của thiết bị nhập), và nội dung hiện hành của bộ nhớ tạm. „ 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. Trang 36 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  37. Phân loại ôtômát „ Dựa vào hoạt động của ôtômát, có đơn định hay không: có hai loại ôtômát. „ Ôtômát đơn định (deterministic automata): là ôtômát trong đómỗi di chuyển (move) được xác định duy nhất bởi cấu hình hiện tại. Sự duy nhất này thể hiện tính đơn định. „ Ôtômát không đơn định (non-deterministic automata): là ôtômát mà tại mỗi thời điểm nó có một vài khả năng lựa chọn để di chuyển. Việc có một vài khả năng lựa chọn thể hiện tính không đơn định. Trang 37 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  38. Phân loại ôtômát (tt) „ Dựa vào kết quả xuất ra của ôtômát: có hai loại ôtômát. „ Accepter: là ôtômát mà đáp ứng ở ngõ ra của nó được giới hạn trong hai trạng thái đơn giản “yes”hay “no”. "Yes" tương ứng với việc chấp nhận chuỗi nhập, "no" tương ứng với việc từ chối, không chấp nhận, chuỗi nhập. „ Transducer: là ôtômát tổng quát hơn, có khả năng sinh ra các chuỗi kí tựởngõ xuất. Máy tính số là một transducer điển hình. Trang 38 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  39. Một vài ứng dụng „ Cung cấp kiến thức nền tảng cho việc xây dựng các ngôn ngữ lập trình (NNLT), các trình dịch. „ Dùng văn phạm để định nghĩa các NNLT. „ Dùng accepter để định nghĩa một vài thành phần của NNLT. „ Xây dựng các bộ phân tích từ vựng, phân tích cú pháp cho các NNLT. Trang 39 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  40. Ví dụ „ Dùng văn phạm mô tả danh hiệu của Pascal. → , → | | λ, → a z | A Z → 0 9 Trang 40 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  41. Ví dụ (tt) „ Dùng accepter mô tả danh hiệu của Pascal. Letter 1 2 Digit Letter or digit 3 Letter or digit Trang 41 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  42. Ví dụ - Văn phạm Pascal đơn giản „ Một văn phạm đơn giản của ngôn ngữ Pascal [prog] ::= [prog header] [var part] [stat part] [prog header] ::= program [id] ( input , output ) ; [var part] ::= var [var dec list] [stat part] ::= begin [stat list] end . [var dec list] ::= [var dec] | [var dec list] [var dec] [var dec] ::= [id list] : [type] ; [stat list] ::= [stat] | [stat list] ; [stat] [stat] ::= [assign stat] [assign stat] ::= [id] := [expr] Trang 42 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  43. Văn phạm Pascal đơn giản (tt) [assign stat] ::= [id] := [expr] [expr] ::= [operand] | [expr] [operator] [operand] [type] ::= integer [id list] ::= [id] | [id list] , [id] [operand] ::= [id] | [number] [id] ::= [letter] | [id] [letter] | [id] [digit] [number] ::= [digit] [operator] ::= + | * [digit] ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 [letter] ::= a z | A Z Trang 43 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  44. Một vài ứng dụng (tt) „ Ứng dụng vào các lĩnh vực xử lý chuỗi. „ Các chức năng tìm kiếm, thay thế trong các trình soạn thảo văn bản hoặc xử lý chuỗi. „ Xử lý ngôn ngữ tự nhiên: chú thích loại từ cho các từ, sửa lỗi chính tả, „ Ứng dụng vào lĩnh vực thiết kế số. „ Trang 44 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  45. Ví dụ -Mạch cộng „ Xét một bộ cộng nhị phân tuần tự hai số nguyên dương a i Sum bit di bi Serial adder Carry „ Trong đóhai chuỗi cộng x = a0a1 . . . an y = b0b1 . . . bm biểu diễn cho hai số nguyên n m i i v()x = ∑ ai 2 v()y = ∑bi 2 i=0 i=0 Trang 45 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  46. Mạch cộng (tt) „ Sơ đồ khối trên chỉ mô tả những gì mà một bộ cộng phải làm chứ không giải thích chút gì về hoạt động bên trong. „ Sau đây là một ôtômát (cụ thể là một transducer) mô tả hoạt động bên trong của bộ cộng nói trên. (0, 1)/1 (1, 0)/1 (0, 1)/0 (1, 1)/1 (0, 0)/0 (1, 0)/1 (1, 1)/0 No Carr carry (0, 0)/1 y Trang 46 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  47. Chương 2 Ôtômát hữu hạn 2.1 Accepter hữu hạn đơn định 2.2 Accepter hữu hạn không đơn định 2.3 Sự tương đương giữa accepter hữu hạn đơn định và accepter hữu hạn không đơn định 2.4 Rút gọn số trạng thái của một ôtômát hữu hạn Trang 47 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  48. Accepter hữu hạn đơn định „ Định nghĩa 2.1 Một accepter hữu hạn đơn định (deterministic finite state accepter) hay dfa được định nghĩa bởi bộ năm M = (Q, Σ, δ, q0, F), „ Q là một tập hữu hạn các trạng thái nội (internal states), „ Σ là một tập hữu hạn các ký hiệu được gọi là bảng chữ cái ngõ nhập (input alphabet), „ δ: Q ×Σ→Q là hàm chuyển trạng thái (transition function). Để chuyển trạng thái ôtômát dựa vào trạng thái hiện hành q ∈ Q nó đang ở vào và kí hiệu nhập a ∈Σnó đang đọc được, nó sẽ chuyển sang trạng thái kế được định nghĩa sẵn trong δ. Trang 48 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  49. Accepter hữu hạn đơn định (tt) „ q0 ∈ Q là trạng thái khởi đầu (initial state), „ F ⊆ Q là một tập các trạng thái kết thúc (final states) (hay còn được gọi là trạng thái chấp nhận). „ Chú ý „ Ôtômát hữu hạn không có bộ nhớ so với mô hình tổng quát. Trang 49 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  50. Hoạt động của một dfa „ Hoạt động của một dfa „ Tại thời điểm khởi đầu, nó được giả thiết ở trong trạng thái khởi đầu q0, với cơ cấu nhập (đầu đọc) của nó đang ở trên kí hiệu đầu tiên bên trái của chuỗi nhập. „ Trong suốt mỗi lần di chuyển, cơ cấu nhập tiến về phía phải một kí hiệu, như vậy mỗi lần di chuyển sẽ lấy một kí hiệu ngõ nhập. „ Khi gặp kí hiệu kết thúc chuỗi, chuỗi là được chấp nhận (accept) nếu ôtômát đang ở vào một trong các trạng thái kết thúc của nó. Ngược lại thì có nghĩa là chuỗi bị từ chối. Trang 50 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  51. Đồ thị chuyển trạng thái „ Để biểu diễn một cách trực quan cho dfa người ta sử dụng đồ thị chuyển trạng thái. Cách biểu diễn như sau. „ Các đỉnh biểu diễn các trạng thái. „ Các cạnh biểu diễn các chuyển trạng thái. „ Các nhãn trên các đỉnh là tên các trạng thái. „ Các nhãn trên các cạnh là giá trị hiện tại của kí hiệu nhập. „ Trạng thái khởi đầu sẽ được nhận biết bằng một mũi tên đi vào không mang nhãn mà không xuất phát từ bất kỳ đỉnh nào „ Các trạng thái kết thúc được vẽ bằng một vòng tròn đôi. Trang 51 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  52. Ví dụ „ Cho dfa sau M = (Q, Σ, δ, q0, F) Q = {q0, q1, q2}, Σ = {0, 1}, F = {q1}, còn δ được cho bởi δ(q0, 0) = q0, δ(q0, 1) = q1, δ(q1, 0) = q0, δ(q1, 1) = q2, δ(q2, 0) = q2, δ(q2, 1) = q1, „ Đồ thị chuyển trạng thái tương ứng là 0 0 1 1 q q0 q1 2 0 1 Trang 52 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  53. Hàm chuyển trạng thái mở rộng „ Hàm chuyển trạng thái mở rộng δ* được định nghĩa một cách đệ qui như sau „ δ*(q, λ) = q, „ δ*(q, wa) = δ(δ*(q, w), a), ∀ q ∈ Q, w ∈Σ*, a ∈Σ. „ Ví dụ „ Nếu δ(q0, a) = q1, và δ(q1, b) = q2, „ Thì δ*(q0, ab) = q2 „ Chú ý „ δ không có định nghĩa cho chuyển trạng thái rỗng, tức là không định nghĩa cho δ(q, λ). Trang 53 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  54. Ngôn ngữ và dfa „ Định nghĩa 2.2 „ Ngôn ngữ được chấp nhận bởi dfa M = (Q, Σ, δ, q0, F) là tập tất cả các chuỗi trên Σ được chấp nhận bởi M. „ L(M) = {w ∈Σ*: δ*(q0, w) ∈ F}. „ Nhận xét: „ L()M = {w ∈Σ* : δ*(q0, w) ∉ F}. Trang 54 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  55. Ví dụ a a, b „ Ví dụ b „ Xét dfa M sau a, b q0 q1 q2 „ Dfa trên chấp nhận ngôn ngữ sau L(M) = {anb : n ≥ 0} „ Trạng thái bẫy (trap state): là trạng thái mà sau khi ôtômát đi vào sẽ không bao giờ thoát ra được. „ Trạng thái bẫy có thể là trạng thái kết thúc hoặc không. „ Định nghĩa trên cũng có thể mở rộng ra cho nhóm các trạng thái bẫy kết thúc hay không kết thúc. Trang 55 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  56. Định lý, bảng truyền „ Định lý 2.1 „ Cho M = (Q, Σ, δ, q0, F) là một accepter hữu hạn đơn định, và GM là đồ thị chuyển trạng thái tương ứng của nó. Thì ∀ qi, qj ∈ + Q, và w ∈Σ , δ*(qi, w) = qj nếu và chỉ nếu có trong GM một con đường mang nhãn là w đi từ qi đến qj. „ Bảng truyền - (transition table) „ Là bảng trong đó các nhãn của hàng (ô tô đậm trên hàng trong hình bên) biểu diễn cho trạng thái hiện tại, còn nhãn của cột (ô tô đậm trên cột trong hình bên) biểu diễn cho ký hiệu nhập hiện tại. Các điểm nhập (entry) trong bảng định nghĩa cho trạng thái kế tiếp. Trang 56 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  57. Bảng truyền (tt) a b a a, b q q q 0 0 1 b a, b q1 q2 q2 q0 q1 q2 q2 q2 q2 „ Bảng truyền gợi ý cho chúng ta một cấu trúc dữ liệu để mô tả cho ôtômát hữu hạn. „ Đồng thời cũng gợi ý cho chúng ta rằng một dfa có thể dễ dàng được hiện thực thành một chương trình máy tính; chẳng hạn bằng một dãy các phát biểu “if”. Trang 57 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  58. Ví dụ „ Tìm dfa chấp nhận ngôn ngữ „ Tìm dfa M1 chấp nhận tập tất cả các chuỗi trên Σ = {a, b} được bắt đầu bằng chuỗi ab. „ Tìm dfa M2 chấp nhận tập tất cả các chuỗi trên Σ = {0, 1}, ngoại trừ những chuỗi chứa chuỗi con 001. a, b 1 0 0, 1 0 a b 0 1 001 q0 q1 q2 λ 0 00 1 b a q3 a, b Trang 58 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  59. Bài tập dfa „ Tìm dfa chấp nhận ngôn ngữ R „ L1 = {vwv ∈ {a, b}*: |v| = 2} n n „ L2 = {abab : n ≥ 0} ∪ {aba : n ≥ 0} n m „ L3 = {a b : (n+m) mod 2= 0} „ L4 = {w ∈ {a, b}*: na(w) chẵn, nb(w) lẽ} „ L5 = {w ∈ {0, 1}*: giá trị thập phân của w chia hết cho 5} „ L6 = {w ∈ {a, b}*: số kí tự a trong chuỗi là một số lẽ} Trang 59 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  60. Ngôn ngữ chính qui „ Định nghĩa 2.3 „ Một ngôn ngữ L được gọi là chính qui nếu và chỉ nếu tồn tại một accepter hữu hạn đơn định M nào đó sao cho L = L(M) „ Ví dụ „ Chứng minh rằng ngôn ngữ L= {awa : w ∈ {a,b}*} là chính qui. b a a a q0 q2 q3 b b q1 a, b Trang 60 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  61. Accepter hữu hạn không đơn định „ Định nghĩa 2.4 „ Một accepter hữu hạn không đơn định (nondeterministic finite state accepter) hay nfa được định nghĩa bằng bộ năm: M = (Q , Σ, δ, q0, F ) trong đó Q, Σ, q0, F được định nghĩa như đối với accepter hữu hạn đơn định còn δ được định nghĩa là: δ : Q × (Σ∪{ λ}) → 2Q „ Nhận xét „ Có hai khác biệt chính giữa định nghĩa này và định nghĩa của một dfa. Trang 61 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  62. Accepter hữu hạn không đơn định (tt) „ Nhận xét (tt) Q „ Đối với nfa miền trị của δ là tập 2 , vì vậy giá trị của nó không còn là một phần tử đơn của Q, mà là một tập con của nó và đặc biệt có thể là ∅, tức là có thể không có định nghĩa cho một δ(q, a) nào đó. Người ta gọi trường hợp này là một cấu hình chết (dead configuration), và có thể hình dung trong trường hợp này ôtômát dừng lại, không hoạt động nữa. „ Thứ hai định nghĩa này cho phép λ như là một đối số thứ hai của δ. Điều này có nghĩa là nfa có thể thực hiện một sự chuyển trạng thái mà không cần phải lấy vào một kí hiệu nhập nào. „ Tương tự như dfa, một nfa cũng có thể được biểu diễn bằng một ĐTCTT. Trang 62 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  63. Ví dụ a a a q1 q2 q3 1 0, 1 q q q0 a q0 0 1 2 a q4 q5 a λ (a) (b) „ Hàm chuyển trạng thái mở rộng „ Định nghĩa 2.5 „ Cho một nfa, hàm chuyển trạng thái mở rộng được định nghĩa sao cho δ*(qi, w) chứa qj nếu và chỉ nếu có một con đường trong ĐTCTT đi từ qi đến qj mang nhãn w. Điều này đúng với mọi qi, qj ∈ Q và w ∈Σ*. Trang 63 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  64. Hàm chuyển trạng thái mở rộng „ Ví dụ λ „ δ*(q1, λ) = {q1, q2, q0} „ δ*(q , λ) = {q , q } 2 2 0 a b, λ q0 q1 q2 „ δ*(q0, a) = {q1, q2, q0} „ δ*(q1, a) = {q1, q2, q0} „ δ*(q1, b) = {q2, q0} Trang 64 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  65. Ngôn ngữ của nfa „ Định nghĩa 2 .6 „ Ngôn ngữ được chấp nhận bởi nfa M = (Q, Σ, δ, q0, F), được định nghĩa như là một tập tất cả các chuỗi được chấp nhận bởi nfa trên. Một cách hình thức, L(M) = {w ∈Σ*: δ*(q0, w) ∩ F ≠ ∅}. „ Ví dụ „ Ngôn ngữ được chấp nhận bởi ôtômát bên dưới là L = {(10)n: n ≥ 0} 1 0, 1 q0 0 q1 q2 λ Trang 65 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  66. Cách tính δ* „ Với T là một tập con của Q, ta định nghĩa * * δ()T,a = Uδ ()q,a δ (T,λ) = Uδ(q,λ) δ (T,a) = Uδ(q,a) q∈T q∈T q∈T „ Người ta thường hiện thực cách tính các hàm này δ(q, a), δ(T, a), δ*(q, λ), δ*(T, λ) lần lượt bằng các hàm move(q, a), move(T, a), λ-closure(q), λ-closure(T) (λ- closure đọc là bao đóng-λ) „ δ*(q, a) = λ-closure(move(λ-closure(q), a)) „ δ*(T, a) = λ-closure(move(λ-closure(T) Trang 66 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  67. Ví dụ a a λ λ q0 q4 q1 λ q q q3 1 2 q q , q q a 1 0 3 2 q 0 q2 a q λ 4 q5 q3 q q „ Hãy tính δ*(q0, a). 4 5 q „ δ*(q0, a) = λ-closure(move(λ-closure(q0), a)) 5 „ λ-closure(q0) = {q0, q1, q2} „ move({q0, q1, q2}, a) = {q4, q0, q3} „ λ-closure({q4, q0, q3}) = {q4, q0, q3, q5, q1, q2} „ Vậy δ*(q0, a) = {q0, q1, q2, q3, q4, q5} Trang 67 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  68. Một định nghĩa khác về dfa - dfa mở rộng „ Một dfa là một trường hợp đặc biệt của một nfa trong đó „ Không có chuyển trạng thái-rỗng, „ Đối với mỗi trạng thái q và một kí hiệu nhập a, có tối đa một cạnh chuyển trạng thái đi ra khỏi q và có nhãn là a. „ Về bản chất định nghĩa này và định nghĩa trước đây là tương đương nhau (cùng định nghĩa tính đơn định của dfa). Nó chỉ khác định nghĩa thứ nhất ở chỗ cho phép khả năng không có một sự chuyển trạng thái đối với một cặp trạng thái và kí hiệu nhập. Trong trường hợp này thì ta xem như nó rơi vào một trạng thái bẫy không kết thúc mà trạng thái này không được vẽ ra. Trang 68 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  69. Ví dụ 0 0 q q q0 q1 0 1 1 1 0 1 q2 0, 1 (a) (b) „ Dfa trong hình (a) đơn giản hơn dfa trong hình (b) mặc dù chúng cùng chấp nhận một ngôn ngữ như nhau. „ Vậy dfa mở rộng và dfa dfa đầy đủ theo định nghĩa ban đầu thật sự là tương đương nhau và chúng chỉ khác nhau ở một trạng thái bẫy không kết thúc. Trang 69 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  70. Bài tập nfa „ Tìm nfa chấp nhận ngôn ngữ „ L1 = {tập tất cả các số thực của Pascal} „ Một “run” trong một chuỗi là một chuỗi con có chiều dài tối thiểu 2 kí tự, dài nhất có thể và bao gồm toàn các kí tự giống nhau. Chẳng hạn, chuỗi abbbaabba chứa một “run” của b có chiều dài 3, một “run” của a có chiều dài 2 và một “run” của b có chiều dài 2. Tìm các nfa và dfa cho mỗi ngôn ngữ sau trên {a, b}. „ L2 = {w: w không chứa “run” nào có chiều dài nhỏ hơn 3} „ L3 = {w: mỗi “run” của a có chiều dài hoặc 2 hoặc 3} „ L4 = {w ∈ {0, 1}*: mỗi chuỗi con bốn kí hiệu có tối đa hai kí hiệu 0}. Trang 70 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  71. Sự tương đương giữa nfa và dfa „ Sư tương đương giữa hai ôtômát „ Hai accepter được gọi là tương đương nhau nếu chúng cùng chấp nhận một ngôn ngữ như nhau. „ Ví dụ „ Dfa và nfa sau là tương đương nhau vì cùng chấp nhận ngôn ngữ {(10)n: n ≥ 0} 0,1 1 1 0 0, 1 1 q q0 q1 q2 q0 0 q1 2 0 λ Trang 71 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  72. Sự tương đương giữa nfa và dfa (tt) „ Nhận xét „ Dfa về bản chất là một loại giới hạn của nfa, nên lớp các dfa là một lớp con của lớp nfa. Nhưng nó có phải là một lớp con thực sự hay không? Rất hay là người ta đã chứng minh được rằng hai lớp này là tương đương nhau, tức là với một nfa thì sẽ có một dfa tương đương với nó. „ Ví dụ „ Hãy xây dựng dfa b a b λ tương đương với a λ q0 q1 nfa bên. q0 q1 q2 q1 q1 q2 a q2 q0 Trang 72 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  73. Ví dụ a b λ q q „ Xây dựng dfa bằng cách mô phỏng lại quá 0 1 trình chấp nhận một chuỗi bất kỳ của nfa q1 q1 q2 „ δ*(q0, λ) = {q0} q2 q0 „ δ*({q0}, a) = {q1, q2} δ*({q0}, b) = ∅ „ δ*({q1, q2}, a) = {q1, q2} δ*({q1, q2}, b) = {q0} a „ Chú ý a „ Một trạng thái của nfa là {q0} b {q1, q2} một tập trạng thái của dfa b ∅ „ Trạng thái kết thúc của nfa là trạng thái mà có chứa trạng thái a, b kết thúc của dfa. Trang 73 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  74. Định lý về sự tương đương „ Định lý 2.2 „ Cho L là ngôn ngữ được chấp nhận bởi một accepter hữu hạn không đơn định MN = (QN, Σ, δN, q0, FN), thì tồn tại một accepter hữu hạn đơn định MD = (QD, Σ, δD, {q0}, FD) sao cho L = L(MD). „ Thủ tục: nfa_to_dfa „ Input: nfa MN = (QN, Σ, δN, q0, FN) „ Output: ĐTCTT GD của dfa MD Trang 74 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  75. Thủ tục: nfa_to_dfa B1. Tạo một đồ thị GD với đỉnh khởi đầu là tập δN*(q0, λ). B2. Lặp lại các bước B3 đến B6 cho đến khi không còn cạnh nào thiếu. B3. Lấy một đỉnh bất kỳ {qi, qj, , qk} của GD mà có một cạnh còn chưa được định nghĩa đối với một a nào đó ∈Σ. B4. Tính δN*({qi, qj, , qk}, a) = {ql, qm, , qn}. B5. Tạo một đỉnh cho GD có nhãn {ql, qm, , qn} nếu nó chưa tồn tại. B6. Thêm vào GD một cạnh từ {qi, qj, , qk} đến {ql, qm, , qn} và gán nhãn cho nó bằng a. B7. Mỗi trạng thái của GD mà nhãn của nó chứa một qf bất kỳ ∈ FN thì được coi là một đỉnh kết thúc. Trang 75 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  76. Ví dụ „ Hãy biến đổi nfa dưới (có bảng truyền tương ứng bên cạnh) thành dfa tương đương. a b λ a λ q0 q1 q1 q3 b a, q1 q2 q q q a a 1 0 2 b q2 q1, q2 q0 a, λ λ q3 q4 q3 q4 q3 q4 b q4 q3 Trang 76 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  77. Ví dụ (tt) a b λ „ δ*(q0, λ) = {q0, q3, q4} q0 q1 q1 q3 „ δ*({q0, q3, q4}, a) = {q1, q2, q4} q1 q0 q2 „ δ*({q0, q3, q4}, b) = {q1, q2, q3, q4} q2 q1, q2 „ δ*({q1, q2, q4}, a) = {q0, q1, q2, q3, q4} q q q q „ δ*({q1, q2, q4}, b) = {q3, q4} 3 4 3 4 q q „ δ*({q1, q2, q3, q4}, a) = {q0, q1, q2, q3, q4} 4 3 „ δ*({q1, q2, q3, q4}, b) = {q3, q4} „ δ*({q0, q1, q2, q3, q4}, a) = {q0, q1, q2, q3, q4} „ δ*({q0, q1, q2, q3, q4}, b) = {q1, q2, q3, q4} „ δ*({q3, q4}, a) = {q4} δ*({q3, q4}, b) = {q3, q4} „ δ*({q4}, a) = ∅δ*({q4}, b) = {q3, q4} Trang 77 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  78. a b λ Ví dụ (tt) q0 q1 q1 q3 q1 q0 q2 q2 q1, q2 q3 q4 q3 q4 q4 q3 {q1, q2, q4} a a b a {q } {q0, q1, q2, q3, q4} {q0, q3, q4} b {q , q } 4 3 4 a a b b b a {q1, q2, q3, q4} Trang 78 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  79. Bài tập biến đổi nfa thành dfa „ Biến đổi những nfa sau thành dfa tương đương Nfa M1 Nfa M2 Nfa M3 a b λ a b λ a b λ q0 q1 q3 q1 q0 q1, q3 q3 q3 q0 q1 q2 q1 q1 q2 q2, q0 q1 q2 q2 q0 q1 q1, q2 q3 q3 q2 q1 q2 q1 q2 q0, q2 q3 q0, q4 q3 q4 q3 q4 q4 q3 q2, q3 q4 q3, q4 q4 q4 q4 q3 F = {q0} F = {q2} F = {q4} Trang 79 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  80. Rút gọn số trạng thái của một dfa „ Hai dfa được vẽ trong (a) và (b) là tương đương nhau 0, 1 1 q q 0 1 3 0 0, 1 1 q0 q0 q1 q2 1 1 q 1 q q 2 4 5 0 0, 1 0 0, 1 0 (a) (b) Trang 80 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  81. Rút gọn số trạng thái của một dfa (tt) „ Nhận xét „ Trong hình (a) có một trạng thái đặc biệt, trạng thái q5, nó là trạng thái không đạt tới được từ trạng thái khởi đầu, người ta gọi nó là trạng thái không đạt tới được. „ Trạng thái không đạt tới được (inaccessible state) „ Là trạng thái mà không tồn tại con đường đi từ trạng thái khởi đầu đến nó. „ Những trạng thái không đạt tới được (TTKĐTĐ) có thể bỏ đi (kèm với các cạnh chuyển trạng thái liên quan tới nó) mà không làm ảnh hưởng tới ngôn ngữ được chấp nhận bởi ôtômát. Trang 81 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  82. Rút gọn số trạng thái của một dfa (tt) „ Nhận xét (tt) „ Các chuyển trạng thái từ sau đỉnh q1 và q2 "có vẻ giống nhau", đối xứng nhau và ôtômát thứ hai "có vẻ như" kết hợp hai phần này. „ Từ đây dẫn tới định nghĩa hai trạng thái giống nhau hay không phân biệt được. „ Khái niệm giống nhau được định nghĩa tổng quát dựa trên việc: với mọi chuỗi nếu xuất phát từ hai trạng thái này thì kết quả về mặt chấp nhận chuỗi là giống nhau tức là hoặc cùng rơi vào trạng thái kết thúc, hoặc không cùng rơi vào trạng thái kết thúc. „ Như vậy hai trạng thái này có thể gom chung lại với nhau mà kết quả chấp nhận chuỗi không thay đổi. Trang 82 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  83. Định nghĩa hai trạng thái giống nhau „ Định nghĩa 2.7 „ Hai trạng thái p và q của một dfa được gọi là không phân biệt được (indistinguishable) hay giống nhau nếu với mọi w ∈∑* δ*(q, w) ∈ F suy ra δ*(p, w) ∈ F, và δ*(q, w) ∉ F suy ra δ*(p, w) ∉ F, Còn nếu tồn tại một chuỗi w nào đó ∈∑* sao cho δ*(q, w) ∈ F còn δ*(p, w) ∉ F, hay ngược lại thì p và q được gọi là phân biệt được (distinguishable) hay khác nhau bởi chuỗi w. „ Nhận xét „ Trạng thái kết thúc và không kết thúc không thể giống nhau. Trang 83 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  84. Nhận xét (tt) „ Chú ý „ Quan hệ giống nhau là một quan hệ tương đương. „ Vì vậy quan hệ này sẽ phân hoạch tập trạng thái Q thành các tập con rời nhau, mỗi tập con bao gồm các trạng thái giống nhau. Trang 84 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  85. Thủ tục đánh dấu - mark „ Để xác định các cặp trạng thái không phân biệt được, người ta thực hiện công việc ngược lại là xác định các cặp trạng thái không giống nhau „ Để làm điều này người ta sử dụng thủ tục mark (đánh dấu) bên dưới. „ Thủ tục: mark „ Input:Các cặp trạng thái, gồm (|Q| × (|Q| -1)/2) cặp, của dfa đầy đủ. „ Output:Các cặp trạng thái được đánh dấu phân biệt được. Trang 85 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  86. Thủ tục đánh dấu - mark B1. Loại bỏ tất cả các TTKĐTĐ. B2. Xét tất cả các cặp trạng thái (p, q). Nếu p ∈ F và q ∉ F hay ngược lại, đánh dấu cặp (p, q) là phân biệt được. Các cặp trạng thái được đánh dấu ở bước này sẽ được ghi là đánh dấu ở bước số 0 (gọi là bước cơ bản). Lặp lại bước B3 cho đến khi không còn cặp nào không được đánh dấu trước đó được đánh dấu ở bước này. B3. Đối với mọi cặp (p, q) chưa được đánh dấu và mọi a ∈∑, tính δ(p, a) = pa và δ(q, a) = qa. Nếu cặp (pa, qa) đã được đánh dấu là phân biệt được ở lần lặp trước đó, thì đánh dấu (p, q) là phân biệt được. Các cặp được đánh dấu ở bước này sẽ được ghi là được đánh dấu ở bước thứ i nếu đây là lần thứ i băng qua vòng lặp. Trang 86 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  87. Thủ tục đánh dấu – mark (tt) „ Định lý 2.3 „ Thủ tục mark, áp dụng cho một dfa đầy đủ bất kỳ M = (Q, ∑, δ, q0, F), kết thúc và xác định tất cả các trạng thái phân biệt được. „ Bổ đề 1 „ Cặp trạng thái qi và qj là phân biệt được bằng chuỗi có độ dài n, nếu và chỉ nếu có các chuyển trạng thái δ(qi, a) = qk và δ(qj, a) = ql với một a nào đó ∈∑, và qk và ql là cặp trạng thái phân biệt được bằng chuỗi có độ dài n-1. Trang 87 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  88. Thủ tục đánh dấu – mark (tt) „ Bổ đề 2 „ Khi băng qua vòng lặp trong bước⎫lần thứ n, thủ tục sẽ đánh dấu được thêm tất cả các cặp trạng thái phân biệt được bằng chuỗi có độ dài n mà chưa được đánh dấu. „ Bổ đề 3 „ Nếu thủ tục dừng lại sau n lần băng qua vòng lặp trong bước 3, thì không có cặp trạng thái nào của dfa mà phân biệt được bằng chuỗi có chiều dài lớn hơn n. Trang 88 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  89. Thủ tục rút gọn - reduce „ Thủ tục: reduce „ Input: dfa M = (Q, Σ, δ, q0, F) ∧ ⎛ ∧ ∧ ∧ ∧ ⎞ „ Output: dfa tối giản ⎜ ⎟ M = ⎜Q,Σ,δ,q0, F ⎟ ⎝ ⎠ B1. Sử dụng thủ tục mark để tìm tất cả các cặp trạng thái phân biệt được. Từ đây tìm ra các tập của tất cả các trạng thái không phân biệt được, gọi là {qi, qj, , qk}, {ql, qm, , qn}, B2. Đối với mỗi tập {q , q , , q } các trạng thái không phân biệt i j k ∧ được, tạo ra một trạng thái có nhãn ij k cho M . Trang 89 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  90. Thủ tục rút gọn - reduce B3. Đối với mỗi quy tắc chuyển trạng thái của M có dạng δ(qr, a) = qp, tìm các tập mà q và q thuộc về. Nếu q ∈ {q , q , , q } và q ∈ r p ∧ r∧ i j k p {ql, qm, , qn}, thì thêm vào δ quy tắc δ ( ij k, a) = lm n. ∧ B4. Trạng thái khởi đầu q 0 là trạng thái của mà nhãn của nó có chứa 0. ∧ B5. F là tập tất cả các trạng thái mà nhãn của nó chứa i sao cho qi ∈ F. Trang 90 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  91. Ví dụ „ Hãy rút gọn trạng thái của dfa sau (cho kèm bảng truyền tương ứng bên cạnh). q 0 1 1 0,1 0 1 0 0 q0 q1 q3 1 q q q q q 1 2 4 q0 2 4 q2 q1 q4 1 0 1 q3 q2 q4 q3 q4 q4 q4 Trang 91 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  92. Ví dụ (tt) 0 1 q0 q1 q3 (q0, q1)91 (q0, q3)91 (q1, q2) (q1, q4)90 (q2, q4)90 q1 q2 q4 (q0, q2)91 (q0, q4)90 (q1, q3) (q2, q3) (q3, q4)90 q2 q1 q4 q3 q2 q4 0 q4 q4 q4 0 0, 1 1,2,3 0,1 1 0 123 4 4 Trang 92 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  93. Định lý „ Định lý 2.4 „ Cho một dfa M bất kỳ, áp dụng thủ tục reduce tạo ra một dfa ∧ khác M sao cho ∧ L(M) = L( M ) Hơn nữa là tối giản theo nghĩa không có một dfa nào khác có số trạng thái nhỏ hơn mà cũng chấp nhận L(M). Trang 93 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  94. Ví dụ „ Hãy rút gọn trạng thái của dfa sau (cho kèm bảng truyền tương ứng bên cạnh). 0 1 q0 0 1 q0 q1 q2 q q q q1 q2 1 3 4 0 1 0,1 q2 q5 q5 1 0,1 0 q q q q3 q4 q5 q6 3 3 4 q4 q5 q5 0 1 0,1 q5 q6 q5 q6 q6 q6 Trang 94 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  95. Ví dụ (tt) 0 1 q0 q1 q2 (q0, q1)90 (q1, q2)90 (q2, q4) (q4, q5)90 q1 q3 q4 (q0, q2)90 (q1, q3) (q2, q5)90 (q4, q6)90 q2 q5 q5 (q0, q3)90 (q1, q4)91 (q2, q6)90 (q5, q6) q3 q3 q4 (q0, q4)90 (q1, q5)90 (q3, q4)91 q4 q5 q5 (q0, q5)91 (q1, q6)90 (q3, q5)90 q5 q6 q5 (q0, q6)91 (q2, q3)91 (q3, q6)90 q6 q6 q6 1,3 0 0 1 0,1 2,4 1,3 1 2,4 5,6 0 0,1 5,6 Trang 95 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  96. Bài tập rút gọn dfa „ Rút gọn những dfa sau thành dfa tối giản Dfa M1 Dfa M2 Dfa M3 Dfa M4 a b a b a b a b q0 q1 q4 q0 q1 q2 q0 q1 q2 q0 q1 q3 q1 q4 q2 q1 q2 q3 q1 q2 q3 q1 q2 q4 q2 q4 q3 q2 q2 q3 q2 q1 q4 q2 q0 q3 q3 q3 q3 q5 q4 q3 q4 q0 q3 q1 q4 q4 q4 q5 q4 q5 q3 q4 q3 q0 q4 q2 q3 q5 q4 q6 q5 q5 q5 q6 q7 q6 q6 q1 q7 q7 q7 q7 q6 q4 Trang 96 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  97. Chương 3 Ngôn ngữ chính qui và văn phạm chính qui 3.1 Biểu thức chính qui (Regular Expression) 3.2 Mối quan hệ giữa BTCQ và ngôn ngữ chính qui 3.3 Văn phạm chính qui (Regular Grammar) Trang 97 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  98. Biểu thức chính qui „ Biểu thức chính qui (BTCQ) là gì? „ Là một sự kết hợp các chuỗi kí hiệu của một bảng chữ cái ∑ nào đó, các dấu ngoặc, và các phép toán +, ., và *. trong đó phép + biểu thị cho phép hội, phép . biểu thị cho phép kết nối, phép * biểu thị cho phép bao đóng sao. „ Ví dụ „ Ngôn ngữ {a} được biểu thị bởi BTCQ a. „ Ngôn ngữ {a, b, c} được biểu thị bởi BTCQ a + b + c. „ Ngược lại BTCQ (a + b.c)* biểu thị cho ngôn ngữ {λ, a, bc, aa, abc, bca, bcbc, aaa, aabc, }. Trang 98 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  99. Định nghĩa hình thức BTCQ „ Định nghĩa 3.1 „ Cho ∑ là một bảng chữ cái, thì 1. ∅, λ, và a ∈∑tất cả đều là những BTCQ hơn nữa chúng được gọi là những BTCQ nguyên thủy. 2. Nếu r1 và r2 là những BTCQ, thì r1 + r2, r1. r2, r1*, và (r1) cũng vậy. 3. Một chuỗi là một BTCQ nếu và chỉ nếu nó có thể được dẫn xuất từ các BTCQ nguyên thủy bằng một số lần hữu hạn áp dụng các quy tắc trong (2). „ Ví dụ „ Cho ∑ = {a, b, c}, thì chuỗi (a + b.c)*.(c + ∅) là BTCQ, vì nó được xây dựng bằng cách áp dụng các qui tắc ở trên. Còn (a + b +) không phải là BTCQ. Trang 99 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  100. Ngôn ngữ tương ứng với BTCQ „ Định nghĩa 3.2 „ Ngôn ngữ L(r) được biểu thị bởi BTCQ bất kỳ là được định nghĩa bởi các qui tắc sau. 1. ∅ là BTCQ biểu thị tập trống, 2. λ là BTCQ biểu thị {λ}, 3. Đối với mọi a ∈∑, a là BTCQ biểu thị {a}, Nếu r1 và r2 là những BTCQ, thì 4. L(r1 + r2) = L(r1) ∪ L(r2), 5. L(r1.r2) = L(r1).L(r2), 6. L((r1)) = L(r1), 7. L(r1*) = (L(r1))*. Trang 100 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  101. Ngôn ngữ tương ứng với BTCQ (tt) „ Qui định về độ ưu tiên „ Độ ưu tiên của các phép toán theo thứ tự từ cao đến thấp là 1. bao đóng – sao, 2. kết nối, 3. hội. „ Ví dụ „ L(a* . (a + b)) = L(a*) L(a + b) = (L(a))* (L(a) ∪ L(b)) = {λ, a, aa, aaa, . . .}{a, b} = {a, aa, aaa, . . . , b, ab, aab, . . .} Trang 101 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  102. Xác định ngôn ngữ cho BTCQ „ Tìm ngôn ngữ của các BTCQ sau „ r1 = (aa)*(bb)*b „ r2 = (ab*a + b)* „ r3 = a(a + b)* „ Kết quả 2n 2m+1 „ L(r1) = {a b : n ≥ 0, m ≥ 0} „ L(r2) = {w ∈ {a, b}*: na(w)chẵn} „ L(r3) = {w ∈ {a, b}*: w được bắt đầu bằng a} Trang 102 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  103. Tìm BTCQ cho ngôn ngữ „ Tìm BTCQ cho các ngôn ngữ sau „ L1 = {tập tất cả các số thực của Pascal} „ L2 = {w ∈ {0, 1}*: w không có một cặp số 0 liên tiếp nào} „ L3 = {w ∈ {0, 1}*: n0(w) = n1(w)} „ Kết quả + + „ r1 = (‘+’+ ‘-’+ λ)(0 + 1 + + 9) (‘.’(0 + 1 + + 9) + λ) (‘E’ (‘+’+ ‘-’+ λ)(0 + 1 + + 9)+ + λ) „ r2 = [(1* 011*)* + 1*] (0 + λ) hoặc (1 + 01)* (0 + λ) „ Không tồn tại BTCQ biểu diễn cho L3 Trang 103 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  104. Một số phép toán mở rộng „ Phép chọn lựa r? hoặc [r] r ? = [r] = (r + λ) + „ Phép bao đóng dương r+ = r.r* „ Chú ý „ (r*)* = r* „ (r1* + r2)* = (r1 + r2)* „ (r1r2* + r2)* = (r1 + r2)* „ Trong một số tài liệu phép cộng (+) được kí hiệu bằng dấu | thay cho dấu + . Chẳng hạn (a + b).c thì được viết là (a | b).c Trang 104 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  105. BTCQ biểu thị NNCQ „ Định lý 3.1 „ Cho r là một BTCQ, thì tồn tại một nfa mà chấp nhận L(r). Vì vậy, L(r) là NNCQ. „ Bổ đề „ Với mọi nfa có nhiều hơn một trạng thái kết thúc luôn luôn có một nfa tương đương với chỉ một trạng thái kết thúc. q q f1 tương đương f1 λ với qf λ qfn qfn Trang 105 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  106. Thủ tục: re-to-nfa „ Từ bổ đề trên mọi nfa có thể được biểu diễn bằng sơ đồ như sau M „ Chứng minh q0 qf „ Thủ tục: re-to-nfa „ Input: Biểu thức chính qui r. „ Output: nfa M = (Q, Σ, δ, q0, F). B1. Xây dựng các nfa cho các BTCQ nguyên thủy a λ q q0 q1 q0 q1 0 q1 (a) nfa chấp nhận ∅ (b) nfa chấp nhận {λ} (c) nfa chấp nhận {a} Trang 106 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  107. Thủ tục: re-to-nfa (tt) B2. Xây dựng các nfa cho các BTCQ phức tạp „ nfa cho BTCQ r1 + r2 M(r1) q q M(r ) λ 01 f1 λ 1 hoặc M(r ) λ 2 λ q02 qf2 M(r2) ĐK: 1. Không có cạnh đi vào q01 và q02 2. Không có cạnh đi ra qf1 và qf2 Trang 107 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  108. Thủ tục: re-to-nfa (tt) „ nfa cho BTCQ r1r2 λλM(r1) M(r2) λ q01 qf1 q02 qf2 hoặc M(r1) M(r2) ĐK: 1. Không có cạnh đi ra qf1 hoặc 2. Không có cạnh đi vào q02 Trang 108 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  109. Thủ tục: re-to-nfa (tt) „ nfa cho BTCQ r* M(r) λ λ M(r) λ q0 qf hoặc q0≡ qf λ ĐK: 1. Không có cạnh đi vào q0 2. Không có cạnh đi ra qf Trang 109 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  110. Ví dụ „ Xây dựng nfa cho BTCQ sau r = (a + bb)*(ba* + λ) λ λ a λ λ λ b λ b λ λ λ λ λ λ λ λ Hoặc theo a a b λ λ a λ phương pháp λ λ cải tiến b λ λ b b λ Trang 110 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  111. Bài tập BTCQ „ Xây dựng nfa cho các BTCQ sau „ r1 = aa* + aba*b* „ r2 = ab(a + ab)* (b + aa) „ r3 = ab*aa + bba*ab „ r4 = a*b(ab + b)*a* „ r5 = (ab* + a*b)(a + b*a)* b „ r6 = (b + a*)(ba* + ab)*(b*a + ab) Trang 111 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  112. BTCQ cho NNCQ „ Đồ thị chuyển trạng thái tổng quát (generallized transition graphs): „ Là một ĐTCTT ngoại trừ các cạnh của nó được gán nhãn bằng các BTCQ. „ Ngôn ngữ được chấp nhận bởi nó là tập tất cả các chuỗi được sinh ra bởi các BTCQ mà là nhãn của một con đường nào đó đi từ trạng thái khởi đầu đến một trạng thái kết thúc nào đócủa ĐTCTT tổng quát (ĐTCTTTQ). Trang 112 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  113. Đồ thị chuyển trạng thái tổng quát a* c* „ Hình bên biểu diễn một ĐTCTTTQ. a + b „ NN được chấp nhận bởi nó là L(a*(a + b)c*) „ Nhận xét „ ĐTCTT của một nfa bất kỳ có thể được xem là ĐTTCTTTQ nếu các nhãn cạnh được diễn dịch như sau. „ Một cạnh được gán nhãn là một kí hiệu đơn a được diễn dịch thành cạnh được gán nhãn là biểu thức a. „ Một cạnh được gán nhãn với nhiều kí hiệu a, b, . . . thì được diễn dịch thành cạnh được gán nhãn là biểu thức a + b + . . . „ Mọi NNCQ đều ∃ một ĐTCTTTQ chấp nhận nó. Ngược lại, mỗi NN mà được chấp nhận bởi một ĐTCTTTQ là chính qui. Trang 113 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  114. Rút gọn trạng thái của ĐTCTTTQ „ Để tìm BTCQ cho một ĐTCTTTQ ta sẽ thực hiện quá trình rút gọn các trạng thái trung gian của nó thành ĐTCTTTQ tương đương đơn giản nhất có thể được. „ Trạng thái trung gian „ Là trạng thái mà không phải là trạng thái khởi đầu, cũng không phải là trạng thái kết thúc. Rút gọn trạng thái e ae*d ce*b a b trung gian q. ae*b qi q qj qi qj d c ce*d Trang 114 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  115. Định lý „ Rút gọn trạng thái q của ĐTCTT sau (a+b)a q a 1 ab aa q b 1 a + b)b aa+b a a+ a+b q q λ b q ( 0 b 0 a a +b b q a 2 b q2 „ Định lý 3.2 a „ Cho L là một NNCQ, thì tồn tại một BTCQ r sao cho L = L(r). r1 r4 r Đồ thị chuyển 2 q r q r = r *r (r + r r *r )* trạng thái 0 3 f 1 2 4 3 1 2 Trang 115 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  116. Ví dụ „ Xác định BTCQ cho nfa sau b b a, b b+ab*a a+b a b ab*b q0 q1 q2 q0 q2 a r = (b + ab*a)* ab*b(a + b)* Trang 116 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  117. BTCQ dùng để mô tả các mẫu đơn giản „ Dùng trong các ngôn ngữ lập trình „ BTCQ được dùng để mô tả các token chẳng hạn như „ Danh hiệu „ Số nguyên thực „ „ Dùng trong các trình soạn thảo văn bản, các ứng dụng xử lý chuỗi „ BTCQ được dùng để mô tả các mẫu tìm kiếm, thay thế „ del tmp*.??? Trang 117 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  118. Văn phạm chính qui „ Văn phạm tuyến tính - phải và – trái. „ Văn phạm tuyến tính - phải sinh ra NNCQ. „ Văn phạm tuyến tính - phải cho NNCQ. „ Sự tương đương giữa VPCQ và NNCQ. Trang 118 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  119. Văn phạm tuyến tính - phải và - trái „ Định nghĩa 3.3 „ Một văn phạm G = (V, T, S, P) được gọi là tuyến tính - phải (TT-P) (right-linear) nếu tất cả luật sinh là có dạng A → xB A → x trong đó A, B ∈ V, x ∈ T*. Một văn phạm được gọi là tuyến tính - trái (TT-T) (left-linear) nếu tất cả các luật sinh là có dạng A → Bx A → x „ Một văn phạm chính qui (VPCQ) là hoặc tuyến tính-phải hoặc tuyến tính-trái. Trang 119 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  120. Ví dụ „ VP G1 = ({S}, {a, b}, S, P1), với P1 được cho như sau là TT-P S → abS | a „ VP G2 = ({S, S1, S2}, {a, b}, S, P2), với P2 như sau là TT-T S → S1ab, S1 → S1ab | S2, S2 → a, „ Dãy S => abS => ababS => ababa là một dẫn xuất trong G1. L(G1) = L((ab)*a) L(G2) = L(a(ab)*ab) Trang 120 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  121. Văn phạm tuyến tính „ VP G = ({S, A, B}, {a, b}, S, P), với các luật sinh S → A, A → aB | λ, B → Ab, không phải là một VPCQ. Đây là một ví dụ của văn phạm tuyến tính (VPTT). „ Văn phạm tuyến tính (Linear Grammar) „ Một văn phạm được gọi là tuyến tính nếu mọi luật sinh của nó có dạng có tối đa một biến xuất hiện ở vế phải của luật sinh và không có sự giới hạn nào trên vị trí xuất hiện của biến này. Trang 121 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  122. Văn phạm TT-P sinh ra NNCQ „ Định lý 3.3 „ Cho G = (V, T, S, P) là một VPTT-P. Thì L(G) là NNCQ. „ Chứng minh „ Thủ tục: GP to nfa „ Input: Văn phạm tuyến tính-phải GP = (V, T, S, P) „ Output: nfa M = (Q, Σ, δ, q0, F) B1. Ứng với mỗi biến Vi của văn phạm ta xây dựng một trạng thái mang nhãn Vi cho nfa tức là: Q ⊃ V. B2. Ứng với biến khởi đầu V0, trạng thái V0 của nfa sẽ trở thành trạng thái khởi đầu, tức là: S = V0 B3. Nếu trong văn phạm có một luật sinh nào đódạng Vi → a1a2 am thì thêm vào nfa một và chỉ một trạng thái kết thúc Vf. Trang 122 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  123. Văn phạm TT-P sinh ra NNCQ (tt) B4. Ứng với mỗi luật sinh của văn phạm có dạng Vi → a1a2 amVj thêm vào nfa các chuyển trạng thái δ*(Vi, a1a2 am) = Vj B5. Ứng với mỗi luật sinh dạng Vi → a1a2 am thêm vào nfa các chuyển trạng thái δ*(Vi, a1a2 am) = Vf a1 a2 an Biểu diễn Vi Vj Vi → a1a2 amVj a a 1 2 an Biểu diễn V V i f V → a a a Trang 123 i 1 2 m Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  124. Ví dụ „ Xây dựng một nfa chấp nhận ngôn ngữ của văn phạm sau: V0 → aV1 | ba V1 → aV1 | abV0 | b „ Nfa kết quả b a a b V0 V1 Vf b a a Trang 124 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  125. Văn phạm TT-P cho NNCQ „ Định lý 3.4 „ Nếu L là một NNCQ trên bảng chữ cái Σ, thì ∃ một VPTT-P G = (V, Σ, S, P) sao cho L = L(G). „ Chứng minh „ Thủ tục: nfa to GP „ Input: nfa M = (Q, Σ, δ, q0, F) „ Output: Văn phạm tuyến tính-phải GP = (V, Σ, S, P) „ Giả thiết Q = {q0, q1, , qn} và Σ = {a1, a2, , am}. B1. V = Q, S = q0 (tức là mỗi trạng thái trong nfa trở thành một biến trong văn phạm) Trang 125 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  126. Thủ tục: nfa to GP B2. Với mỗi chuyển trạng thái δ(qi, aj) = qk của M ta xây dựng luật sinh TT-P tương ứng qi → ajqk. B3. Đối với mỗi trạng thái qf ∈ F chúng ta xây dựng luật sinh qf →λ. „ Ví dụ „ Xây dựng VPTT-P cho ngôn ngữ L(aab*a). b GP: q0 → aq1 a a a q1 → aq2 q0 q1 q2 qf q2 → aqf | bq2 qf → λ Trang 126 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  127. Sự tương đương giữa VPCQ và NNCQ „ Nhận xét „ Lớp VPTT-P tương đương với lớp NNCQ „ Định lý 3.5 „ Ngôn ngữ L là chính qui nếu và chỉ nếu tồn tại một VPTT-T G sao cho L = L(G). „ Ta chứng minh mối quan hệ tương đương thông qua VPTT-P. „ Bổ đề 1 „ Từ VPTT-TGT đã cho ta xây dựng VPTT-PGP tương ứng như sau Trang 127 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  128. Sự tương đương giữa VPCQ và NNCQ 1. Ứng với luật sinh TT-TA→ Bv ta xây dựng luật sinh TT-PA→ vRB. 2. Ứng với luật sinh TT-TA→ v ta xây dựng luật sinh TT-PA→ vR. „ GP được xây dựng theo cách trên có quan hệ với GT như sau R L(GT) = L(GP) „ Bổ đề 2 R „ Nếu L là chính qui thì L cũng chính qui. „ Nhận xét „ Lớp VPTT-T tương đương với lớp NNCQ „ Định lý 3.6 „ Một ngôn ngữ L là chính qui nếu và chỉ nếu tồn tại một VPCQ G sao cho L = L(G). Trang 128 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  129. Ví dụ „ Xây dựng nfa M, VPTT-T GT tương đương với VPTT-P GP sau S → aS | bA A → bB | a B → aS | b a a A Y b a b a R M S b U b X M a B b a Z b R GP X → aY | bZ GT X → Ya | Zb Y → bU Y → Ub Z → bY Z → Yb U→ aU | aZ | λ U→ Ua | Za | λ Trang 129 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  130. Chương 4 Các tính chất của ngôn ngữ chính qui „ NNCQ tổng quát là như thế nào? Có phải chăng mọi ngôn ngữ hình thức đều là chính qui? „ Khi chúng ta thực hiện các phép toán trên NNCQ thì kết quả sẽ như thế nào, có còn là một NNCQ không? „ Một ngôn ngữ nào đócóhữu hạn không? Có rỗng không? „ Làm thế nào để biết một ngôn ngữ đã cho có là chính qui không? Trang 130 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  131. Chương 4 Các tính chất của ngôn ngữ chính qui 4.1 Tính đóng của ngôn ngữ chính qui. 4.2 Các câu hỏi cơ bản về ngôn ngữ chính qui 4.3 Nhận biết các ngôn ngữ không chính qui Trang 131 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  132. Tính đóng của NNCQ „ Đóng dưới các phép toán tập hợp đơn giản. „ Định lý 4.1 „ Nếu L1 và L2 là các NNCQ, thì L1∪L2, L1∩L2 , L1L2, L và L1* cũng vậy. Chúng ta nói rằng họ NNCQ là đóng dưới các phép hội, giao, kết nối, bù và bao đóng-sao. „ Chứng minh „ Nếu L1, L2 là chính qui thì ∃ các BTCQ r1, r2 sao cho L1= L(r1), L2= L(r2). Theo định nghĩa r1 + r2, r1r2 và r1* là các BTCQ định nghĩa các ngôn ngữ L1∪L2, L1L2, và L1*. Vì vậy họ NNCQ là đóng đối với các phép toán này. „ Để CM tính đóng đối với phép bù, cho M = (Q, Σ, δ, q0, F) là ^ dfa chấp nhận L1, thì dfa M = (Q, Σ , δ, q0, Q - F) chấp nhận L . Trang 132 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  133. Đóng dưới các phép toán tập hợp đơn giản „ Để CM tính đóng đối với phép giao ta có hai cách như sau. Cách thứ nhất „ Dựa vào qui tắc De Morgan ta có L1 I L2 = L1 I L2 = L1 U L2 Dựa vào tính đóng của phép bù và phép hội vừa được chứng minh ở trên ta suy ra tính đóng đối với phép giao. Cách thứ hai „ Ta sẽ xây dựng một dfa cho L1 ∩ L2. „ Cho M1 = (Q, Σ, δ1, q0, F1) và M2 = (P, Σ, δ2, p0, F2) là các dfa lần lượt chấp nhận L , L . ^ 1 ^2 ^ ^ „ Ta xây dựng dfa M = ( Q , Σ , δ , ( q 0 , p 0 ), F ) chấp nhận L1 ∩ L2 bằng thủ tục intersection sau. Trang 133 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  134. Thủ tục: intersection „ Thủ tục: intersection „ Input: dfa M1 = (Q, Σ, δ1, q0, F1) và dfa M2 = (P, Σ, δ2, p0, F2) ^ ^ ^ ^ „ Output: dfa M = (Q,Σ,δ ,(q0 , p0 ), F ) ^ ^ „ Q = Q × P, tức làQ = {(qi, pj): trong đó qi ∈ Q còn pj ∈ P}. Các chuyển trạng thái được xây dựng như sau ^ δ ((qi, pj), a) = (qk, pl) nếu và chỉ nếu δ1(qi, a) = qk và δ2(pj, a) = pl ^ F = {(qi, pj): trong đó qi ∈ F1 còn pj ∈ F2} Trang 134 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  135. Thủ tục: intersection (tt) „ Cách xây dựng trên mô phỏng lại quá trình xử lý của đồng thời ^ ^ hai dfa M1 và M2. Ngoài ra dựa vào định nghĩa của δ ta thấy M chỉ chấp nhận những chuỗi mà được đồng thời cả hai dfa M và ^ 1 M2 chấp nhận. Vì vậy M chấp nhận L1 ∩ L2. „ Ví dụ 2n m 3n 2m „ Tìm dfa giao của L1={a b : n, m ≥ 0} và L2={a b : n, m ≥ 0} q 1 b q1 p0 a a a a b q p q p L1 q q 0 1 0 2 0 2 a a a p p 2 1 q1 p2 q1 p1 a a b b a a b L2 p p p L1 ∩ L2 q p q p 0 3 4 0 0 b 2 3 q2 p4 b Trang 135 b Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  136. Đóng dưới các phép toán tập hợp đơn giản (tt) „ Định lý 4.2 „ Họ NNCQ là đóng dưới phép hiệu và nghịch đảo. „ Chứng minh „ Để chứng minh tính đóng đối với phép hiệu dựa vào các qui tắc tập hợp ta có: L - L = L ∩ 1 2 1 L2 „ Dựa vào tính đóng của phép bù và phép giao đã được chứng minh, suy ra tính đóng cho phép hiệu. „ Tính đóng của phép nghịch đảo đã được chứng minh ở Chương 3, slide 128. Trang 136 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  137. Đóng dưới các phép toán khác „ Phép đồng hình (homomorphism) „ Định nghĩa 4.1 „ Giả sử Σ và Γ là các bảng chữ cái, thì một hàm h: Σ→Γ* được gọi là một phép đồng hình. Bằng lời, một phép đồng hình là một sự thay thế trong đómỗi kí hiệu đơn được thay thế bằng một chuỗi. „ Mở rộng nếu w = a1a2. . . an, thì h(w) = h(a1)h(a2). . .h(an) „ Nếu L là ngôn ngữ trên Σ, thì ảnh đồng hình (homomorphic image) của nó được định nghĩa là h(L) = {h(w): w ∈ L}. Trang 137 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  138. Ví dụ „ Cho Σ ={a, b}, Γ ={a, b, c} và h được định nghĩa như sau h(a) = ab, h(b) = bbc. Thì h(aba) = abbbcab. Ảnh đồng hình của L = {aa, aba} là ngôn ngữ h(L) = {abab, abbbcab}. „ Cho Σ ={a, b}, Γ ={ b, c, d } và h được định nghĩa như sau h(a) = dbcc, h(b) = bdc. Nếu L là ngôn ngữ được biểu thị bởi BTCQ r = (a + b*)(aa)*, thì r1 = (dbcc + (bdc)*)(dbccdbcc)*, là BTCQ biểu thị cho h(L). Từ đódẫn ta tới định lý sau Trang 138 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  139. Định lý „ Định lý 4.3 „ Cho h là một đồng hình. Nếu L là một NNCQ, thì ảnh đồng hình của nó h(L) cũng là NNCQ. Họ các NNCQ vì vậy là đóng dưới phép đồng hình bất kỳ. „ Phép thương đúng „ Định nghĩa 4.2 „ Cho w, v ∈Σ* thì thương đúng (right quotient) của w cho v được kí hiệu và định nghĩa là w/v = u nếu w = uv, nghĩa là nếu v là tiếp vĩ ngữ của w thì w/v là tiếp đầu ngữ tương ứng của w. „ Cho L1 và L2 là các ngôn ngữ trên bảng chữ cái giống nhau, thì thương đúng của L1 với L2 được định nghĩa là L1/L2 = {w/v: w ∈ L1, v ∈ L2 } = {x : xy ∈ L1 với một y nào đó ∈ L2 } Trang 139 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  140. Ví dụ n m m „ Cho L1 = {a b : n ≥ 1, m ≥ 0} ∪ {ba} và L2 = {b : m ≥ 1}, thì n m L1 /L2 = { a b : n ≥ 1, m ≥ 0}. „ Vì L1, L2, và L1 /L2 là các NNCQ , điều này gợi ý cho chúng ta rằng thương đúng của hai NNCQ cũng là NNCQ. „ Bổ đề „ Cho M1 = (Q1, Σ, δ1, q0, F1) là một dfa cho L1.Nếu một trạng thái q nào đó ∈ Q1 có tính chất tồn tại một chuỗi y nào đó ∈ L2 sao cho δ1*(q, y) ∈ F1 thì ∀ x mà δ1*(q0, x) = q, x sẽ ∈ L1/L2. Và vì vậy nếu thay những trạng thái kết thúc của M bằng những trạng thái q có tính chất này thì ta sẽ có một dfa mà chấp nhận L1/L2. Trang 140 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  141. Định lý M xy 1 q q q 0 f * ∀x mà δ1 (q0, x) = q thì x ∈ L1/L2 M2 y p0 pf „ Định lý 4.4 „ Nếu L1 và L2 là các NNCQ, thì L1/L2 cũng chính qui. Chúng ta nói rằng họ NNCQ là đóng dưới phép thương đúng. „ Chứng minh „ Cho L1 = L(M) trong đó M = (Q, Σ, δ, q0, F) là một dfa. Ta xây ^ ^ dựng một dfa khác M =( Q, Σ, δ, q0, F ), chấp nhận L1/L2,bằng cách chỉ thay đổi tập F thông qua thủ tục sau. Trang 141 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  142. Thủ tục: right quotient „ Thủ tục: right quotient „ Input: dfa M1 = (Q, Σ, δ1, q0, F1) và dfa M2 = (P, Σ, δ2, p0, F2) ^ ^ „ Output: dfa M = (Q, Σ, δ1, q0,)F ^ „ Ta xác định F bằng cách xác định với mỗi qi ∈ Q, có tồn tại hay không chuỗi y ∈ L sao cho δ*(q , y) ∈ F. Nếu đúng thì đưa ^ 2 i qi vào F . „ Điều này có thể thực hiện được bằng cách xét các dfa Mi = (Q, Σ, δ1, qi, F). chính là M nhưng trạng thái khởi đầu q0 được thay bằng q . Rồi xét xem L ∩ L(M ) có ≠∅không. Nếu khác thì q i 2 i ^ i có tính chất đã nói ở trên và thêm qi vào F . Thực hiện điều này ^ ^ ∀ qi ∈ Q, ta sẽ xác định được F và vì vậy xây dựng được M . Trang 142 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  143. Ví dụ „ Tìm L1/L2 cho L1 = L(a*baa*), L2 = L(ab*). a a a a M1 b a L1/L2 b a q0 q1 q2 q0 q1 q2 b M2 a p0 p1 Trang 143 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  144. Các câu hỏi cơ bản về NNCQ „ Cho một ngôn ngữ L và một chuỗi w, chúng ta có thể xác định được w có phải là một phần tử của L hay không? „ Đây là một câu hỏi thành viên (membership) và phương pháp để trả lời nó được gọi là giải thuật thành viên. „ Một ngôn ngữ đã cho là hữu hạn hay vô hạn? „ Hai ngôn ngữ nào đócógiống nhau không? „ Có hay không một ngôn ngữ là tập con của một ngôn ngữ khác? „ Biểu diễn chuẩn (Standard representation) „ Chúng ta nói rằng một NNCQ là được cho trong một dạng biểu diễn chuẩn nếu và chỉ nếu nó được mô tả bởi một trong ba dạng sau đây: một ôtômát hữu hạn, một BTCQ hoặc một VPCQ. „ Chú ý từ một dạng biểu diễn chuẩn này luôn có thể xác định được các dạng biểu diễn chuẩn khác nhờ vào các định lý đã được CM trước đây. Trang 144 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  145. Các định lý „ Định lý 4.5 „ Cho một biểu diễn chuẩn của một NNCQ L bất kỳ trên Σ và một chuỗi w bất kỳ ∈Σ*, thì tồn tại giải thuật để xác định w có ∈ L hay không. „ Chứng minh „ Chúng ta biểu diễn ngôn ngữ bằng một dfa rồi kiểm tra xem w có được chấp nhận bởi dfa này không. „ Định lý 4.6 „ Tồn tại giải thuật để xác định một NNCQ đã cho trong một dạng biểu diễn chuẩn có trống, hữu hạn, vô hạn hay không. Trang 145 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  146. Các định lý (tt) „ Chứng minh „ Chúng ta biểu diễn ngôn ngữ bằng một dfa. Nếu tồn tại một con đường đi từ trạng thái khởi đầu đến một trạng thái kết thúc nào đó thì ngôn ngữ là khác trống. „ Để xác định ngôn ngữ có vô hạn không, ta tìm tất cả các đỉnh mà có chu trình đi qua nó. Nếu có một đỉnh trong số này thuộc một con đường nào đó đi từ trạng thái khởi đầu đến một trạng thái kết thúc thì ngôn ngữ là vô hạn, ngược lại thì là hữu hạn. Trang 146 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  147. Các định lý (tt) „ Định lý 4.7 „ Cho các biểu diễn chuẩn của hai NNCQ L1 và L2, tồn tại giải thuật để xác định có hay không L1 = L2. „ Chứng minh „ Sử dụng L1 và L2 chúng ta xây dựng ngôn ngữ: L3 = (L1 I L2 ) U (L1 I L2 ) „ Theo lý thuyết tập hợp ta có L1 = L2 khi và chỉ khi L3 = ∅. Vậy thay vì kiểm tra L1 có bằng L2 không ta chuyển về kiểm tra L3 có bằng ∅ không. Bằng tính đóng L3 là chính qui, và chúng ta có thể tìm thấy dfa M mà chấp nhận L3. Thêm vào đó chúng ta đã có giải thuật trong Định lý 4.6 để xác định xem L3 có bằng trống không. Nếu L3 = ∅ thì L1 = L2, ngược lại thì không. Trang 147 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  148. Nhận biết các NN không CQ „ Sử dụng nguyên lý chuồng chim bồ câu „ Nếu chúng ta đặt n vật thể vào trong m hộp, và nếu n > m, thì ít nhất có một hộp chứa nhiều hơn một vật thể. „ Ngôn ngữ L = {anbn : n ≥ 0} có chính qui không? „ Câu trả lời là không, như chúng ta sẽ chứng tỏ bằng cách sử dụng phương pháp phản chứng sau. Giả sử L là chính qui thì ∃ dfa M = (Q, {a,b}, δ, q0, F) nào đó cho L. i Xét δ*(q0, a ) với i = 0, 1, 2, 3, Vì có một số không giới hạn các i, nhưng chỉ có một số hữu hạn các trạng thái trong M, theo nguyên lý chuồng chim bồ câu thì phải có một trạng thái nào đó, chẳng hạn q, sao cho n m δ*(q0, a ) = q và δ*(q0, a ) = q, với n ≠ m. Trang 148 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  149. Nhận biết các NN không CQ Nhưng vì M chấp nhận anbn nên ta có n δ*(q, b ) = qf ∈ F. Kết hợp với ở trên ta suy ra m n n δ*(q0, a b ) = δ*(q, b ) = qf . Vì vậy M chấp nhận cả chuỗi ambn với n ≠ m. Điều này mâu thuẫn với định nghĩa của L, suy ra L không chính qui. „ Nhận xét „ Trong lý luận này, nguyên lý chuồng chim bồ câu đơn giản phát biểu rằng một ôtômát hữu hạn có một bộ nhớ hữu hạn. Để chấp nhận tất cả các chuỗi anbn, một ôtômát phải phân biệt giữa mọi tiếp đầu ngữ an và am. Nhưng vì chỉ có một số hữu hạn các trạng thái nội để thực hiện điều này, nên phải có một n và một m nào đómà đối với chúng ôtômát không thể phân biệt được. Trang 149 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  150. Bổ đề bơm „ Định lý 4.8 „ Cho L là một NNCQ vô hạn, thì tồn tại một số nguyên dương m nào đó sao cho ∀ w ∈ L và |w| ≥ m đều tồn tại một cách phân tích w thành bộ ba w = xyz, với |xy| ≤ m, và |y| ≥ 1, sao cho i wi =xy z ∈ L ∀ i = 0, 1, 2, „ Chứng minh „ Nếu L là chính qui, thì ∃ một dfa chấp nhận nó. Lấy một dfa như thế có tập trạng thái Q = {q0, q1, q2, ,qn}. Chọn m = |Q| = n + 1. Trang 150 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  151. Chứng minh bổ đề bơm (tt) Lấy một chuỗi w bất kỳ ∈ L và |w| = k ≥ m. Xét một dãy các trạng thái mà ôtômát đi qua khi xử lý chuỗi w, giả sử là q0, qi, qj, . . . .,qf Vì |w| = k suy ra dãy này có k + 1 phần tử. Vì k + 1 > n + 1 nên có ít nhất một trạng thái phải được lặp lại, và sự lặp lại này nằm trong n + 2 phần tử đầu tiên của dãy. Vì vậy dãy trên phải có dạng q0 , qi , qj , , qr , , qr , , qf Trang 151 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  152. Chứng minh bổ đề bơm (tt) suy ra phải có các chuỗi con x, y, z của w sao cho δ*(q0, x) = qr , δ*(qr, y) = qr , δ*(qr, z) = qf , với |xy| ≤ n + 1 = m, vì sự lặp lại trạng thái xảy ra trong n + 2 phần tử đầu tiên, và |y| ≥ 1. Từ điều này suy ra δ*(qr, xz) = qf , cũng như i δ*(qr, xy z) = qf , ∀ i = 0, 1, 2 , Đến đây định lý được chứng minh. Trang 152 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  153. Vận dụng bổ đề bơm „ Sử dụng bổ đề bơm để chứng minh L = {anbn: n ≥ 0} là không chính qui. „ Giả sử L là chính qui, dễ thấy L vô hạn. Theo bổ đề bơm tồn tại số nguyên dương m. m m „ Chọn w = a b ∈ L, |w|=2m ≥ m. Theo bổ đề bơm ∃ một cách phân tích w thành bộ ba w = xyz, trong đó|xy|≤ m (1), |y|= k ≥ 1 (2). „ Từ cách chọn w có m kí hiệu a đi đầu, kết hợp với (1) suy ra xy chỉ chứa a, từ đây suy ra y cũng chỉ chứa a. Vậy y = ak. i n - k n „ Xét wi = xy z với i = 0, ta có w0 = a b ∈ L theo bổ đề bơm, nhưng điều này mâu thuẫn với định nghĩa của L. Vậy L là không chính qui. Trang 153 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  154. Vận dụng bổ đề bơm (tt) „ Nhận xét „ Lý luận này có thể được trực quan hóa như một trò chơi chúng ta đấu với một đối thủ. Mục đích của chúng ta là thắng ván chơi bằng cách tạo ra một sự mâu thuẫn của bổ đề bơm, trong khi đối thủ thử chặn đứng chúng ta. Có bốn bước đi trong trò chơi này như sau. (1) Đối thủ lấy m. (2) Với m đã cho chúng ta lấy một chuỗi w ∈ L thõa |w| ≥ m. (3) Đối thủ chọn phân hoạch xyz, thõa |xy| ≤ m, |y| ≥ 1. Chúng ta phải giả thiết rằng đối thủ chọn lựa làm sao cho chúng ta khó thắng ván chơi nhất. (4) Chúng ta chọn i sao cho chuỗi được bơm lên ∉ L. Trang 154 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  155. Vận dụng bổ đề bơm (tt) „ Bước quyết định ở đây là bước (2). Trong khi chúng ta không thể ép buộc đối thủ lấy một phân hoạch cụ thể của chuỗi w, chúng ta có thể chọn chuỗi w sao cho đối thủ bị hạn chế nghiêm ngặt trong bước (3), ép buộc một sự chọn lựa của x, y, z sao cho cho phép chúng ta tạo ra một mâu thuẫn với bổ đề bơm trên bước kế tiếp của chúng ta. „ Ví dụ Chứng minh các ngôn ngữ sau là không chính qui. R „ L1 = {ww : w ∈ {a, b}*} n l „ L2 = {a b : n ≠ l} Trang 155 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  156. Tóm tắt họ NNCQ Đóng với hội, giao, kết nối, bù, bao đóng sao, hiệu, nghịch đảo, đồng Dfa hình, thương đúng min w ∈ L ? NNCQ Dfa Nfa L = ∅ ? L vô hạn ? L1 = L2 ? L chính qui ? VPTT-T VPTT-P BTCQ Trang 156 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  157. Chương 5 Ngôn ngữ phi ngữ cảnh 5.1 Văn phạm phi ngữ cảnh 5.2 Phân tích cú pháp và tính nhập nhằng 5.3 Văn phạm phi ngữ cảnh và ngôn ngữ lập trình Trang 157 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  158. Văn phạm phi ngữ cảnh „ Định nghĩa 5.1 „ Một văn phạm G = (V, T, S, P) được gọi là phi ngữ cảnh (context free) nếu mọi luật sinh trong P có dạng A → x, trong đó A ∈ V còn x ∈ (V ∪T)*. „ Một ngôn ngữ được gọi là phi ngữ cảnh nếu và chỉ nếu có một VPPNC G sao cho L = L(G). „ Nhận xét „ Mọi NNCQ đều là PNC, nhưng điều ngược lại thì không. Như chúng ta sẽ thấy sau này họ NNCQ là một tập con thực sự của họ NNPNC. Trang 158 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  159. Các ví dụ về NNPNC „ Ví dụ 1 „ Văn phạm G = ({S}, {a, b}, S, P), có các luật sinh S → aSa | bSb | λ, là PNC. Một dẫn xuất điển hình trong văn phạm này là S ⇒ aSa ⇒ aaSaa ⇒ aabSbaa ⇒ aabbaa Dễ thấy L(G) = {wwR: w ∈ {a, b}*} „ Văn phạm trong ví dụ trên không những là PNC mà còn là tuyến tính. Các VPCQ và tuyến tính rõ ràng là PNC, nhưng một VPPNC không nhất thiết là tuyến tính. Trang 159 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  160. Các ví dụ về NNPNC (tt) „ Ví dụ 2 „ Ngôn ngữ sau là PNC. L = {anbn: n ≥ 0} VPPNC cho ngôn ngữ này là: S → aSb | λ „ Ví dụ 3 „ Ngôn ngữ sau là PNC. L = {anbm: n ≠ m} Trường hợp n > m Trường hợp m > n VP kết quả S → AS1 S → S1BS → AS1 | S1B S1→ aS1b | λ S1→ aS1b | λ S1→ aS1b | λ A → aA | a B → bB | b A → aA | a B → bB | b Trang 160 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  161. Các ví dụ về NNPNC (tt) „ Ví dụ 4 „ Xét văn phạm sau S → aSb | SS | λ. Văn phạm này sinh ra ngôn ngữ L = {w ∈ {a, b}*: na(w) = nb(w) và na(v) ≥ nb(v), với v là một tiếp đầu ngữ bất kỳ của w} „ Nhận xét „ Nếu trong ngôn ngữ trên thay a bằng dấu mở ngoặc (, b bằng dấu đóng ngoặc ), thì ngôn ngữ sẽ tương ứng với cấu trúc ngoặc lồng nhau, chẳng hạn (( )) hay (( ) ( )), phổ biến trong các ngôn ngữ lập trình. Trang 161 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  162. Dẫn xuất trái nhất và phải nhất „ Trong VPPNC mà không tuyến tính, một dẫn xuất có thể bao gồm nhiều dạng câu với nhiều hơn một biến. Như vậy, chúng ta có một sự lựa chọn thứ tự biến để thay thế. „ Xét văn phạm G = ({A, B, S}, {a,b}, S, P) với các luật sinh 1. S → AB,2.A → aaA, 4. B → Bb, 3. A →λ,5.B →λ. Dễ dàng thấy rằng văn phạm này sinh ra ngôn ngữ L(G) = {a2nbm : n ≥ 0, m ≥ 0}. Bây giờ xét hai dẫn xuất của chuỗi aab 1 2 3 4 5 S ⇒ AB ⇒ aaAB⇒ aaB⇒ aaBb⇒ aab 1 4 2 5 3 S ⇒ AB ⇒ ABb⇒ aaABb⇒ aaAb⇒ aab. Trang 162 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  163. Dẫn xuất trái nhất và phải nhất (tt) „ Để trình bày luật sinh nào được sử dụng, chúng ta đã đánh số các luật sinh và ghi số thích hợp trên kí hiệu dẫn xuất ⇒. „ Từ đây chúng ta thấy rằng hai dẫn xuất không chỉ tạo ra cùng một câu mà còn sử dụng chính xác các luật sinh giống nhau chỉ khác biệt về thứ tự các luật sinh được áp dụng. „ Để loại bỏ các yếu tố không quan trọng như thế, chúng ta thường yêu cầu rằng các biến được thay thế trong một thứ tự chỉ định. Từ đây chúng ta đưa ra định nghĩa sau. „ Định nghĩa 5.2 „ Một dẫn xuất được gọi là trái nhất (DXTN - leftmost derivation) nếu trong mỗi bước biến trái nhất trong dạng câu được thay thế. Nếu biến phải nhất được thay thế, chúng ta gọi là dẫn xuất phải nhất (DXPN - rightmost derivation). Trang 163 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  164. Ví dụ „ Xét văn phạm với các luật sinh (được đánh chỉ số bên tay phải) S → aAB,1 A → bBb,2 B → A | λ, 3, 4 1 2 3 2 4 4 S⇒ aAB ⇒ abBbB ⇒ abAbB ⇒ abbBbbB ⇒ abbbbB ⇒ abbbb là một DXTN của chuỗi abbbb. Một DXPN của chuỗi này là 1 4 2 3 2 4 S⇒ aAB ⇒ aA ⇒ abBb ⇒ abAb ⇒ abbBbb ⇒ abbbb „ DXTN và DXPN có lợi điểm là ta chỉ cần trình bày dãy số hiệu luật sinh được dùng để sinh ra câu đó mà không sợ bị nhầm lẫn. „ DXTN của abbbb là: 123244. „ DXPN của abbbb là: 142324. Trang 164 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  165. Cây dẫn xuất „ Một cách thứ hai để trình bày các dẫn xuất, độc lập với thứ tự các luật sinh được áp dụng, là bằng cây dẫn xuất (CDX). „ Một CDX là một cây có thứ tự trong đó các nốt được gán nhãn với vế trái của luật sinh còn các con của các nốt biểu diễn vế phải tương ứng của nó. Chẳng hạn, bên dưới trình bày một phần của CDX biểu diễn luật sinh A → abABc. A a b A B c Trang 165 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  166. Cây dẫn xuất (tt) „ Định nghĩa 5.3 „ Cho G = (V, T, S, P) là một VPPNC. Một cây có thứ tự là một cây dẫn xuất cho G nếu và chỉ nếu có các tính chất sau. 1.Gốc được gán nhãn là S. 2.Mỗi lá có một nhãn lấy từ tập T ∪ {λ}. 3.Mỗi nốt bên trong (không phải là lá) có một nhãn lấy từ V. 4.Nếu mỗi nốt có nhãn A ∈ V, và các con của nó được gán nhãn (từ trái sang phải) a1, a2, , an, thì P phải chứa một luật sinh có dạng A → a1a2 an 5.Một lá được gán nhãn λ thì không có anh chị em, tức là, một nốt với một con được gán nhãn λ không thể có con nào khác. Trang 166 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  167. Cây dẫn xuất (tt) „ Một cây mà có các tính chất 3, 4 và 5, còn tính chất (1) không nhất thiết được giữ và tính chất 2 được thay thế bằng 2’.Mỗi lá có một nhãn lấy từ tập V ∪ T ∪ {λ} thì được gọi là một cây dẫn xuất riêng phần (CDXRP). „ Chuỗi kí hiệu nhận được bằng cách đọc các nốt lá của cây từ trái sang phải, bỏ qua bất kỳ λ nào được bắt gặp, được gọi là kết quả (yield) của cây. Trang 167 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  168. Ví dụ „ Xét văn phạm G với các luật sinh sau S → aAB, A → bBb, B → A | λ, CDX riêng phần CDX cho chuỗi abbbb S S a A B a A B b B b b B b A λ b B b Trang 168 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin λ
  169. Mối quan hệ giữa dạng câu và CDX „ Nhận xét „ CDX đưa ra một mô tả của dẫn xuất rất tường minh và dễ hiểu. Giống như ĐTCTT cho ôtômát hữu hạn, sự tường minh là một sự giúp đỡ lớn trong việc thực hiện lý luận. Tuy vậy, đầu tiên chúng ta phải thiết lập một quan hệ giữa dẫn xuất và CDX. „ Định lý 5.1 „ Cho G = (V, T, S, P) là một VPPNC, thì ∀ w ∈ L(G), tồn tại một CDX của G mà kết quả của nó là w. Ngược lại, kết quả của một CDX bất kỳ là thuộc L(G). Tương tự, nếu tG là một CDX riêng phần bất kỳ của G mà gốc của nó được gán nhãn là S thì kết quả của tG là một dạng câu của G. Trang 169 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  170. Phân tích cú pháp và tính nhập nhằng „ Phân tích cú pháp (Syntax analysis hay parsing) „ Phân tích cú pháp (PTCP) là quá trình xác định một chuỗi có được sinh ra bởi một văn phạm nào đó không, cụ thể là quá trình tìm CDX cho chuỗi đó. „ Kết qủa của quá trình PTCP rơi vào một trong hai khả năng “yes”hoặc “no”. “Yes” có nghĩa là chuỗi được sinh ra bởi văn phạm và kèm theo một hay một số dẫn xuất sinh ra chuỗi. “No” có nghĩa là chuỗi không được sinh ra bởi văn phạm hay còn gọi là chuỗi không đúng cú pháp, có lỗi (error). „ Các giải thuật phân tích cú pháp thường có dạng như sau: Input: G = (V, T, S, P) và chuỗi w cần phân tích Output: “yes” hay “no”. Trong trường hợp “yes” thường có kèm theo DXTN hay DXPN của chuỗi. Trang 170 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  171. Các trường phái phân tích cú pháp „ Có hai trường phái PTCP cơ bản 1. PTCP từ trên xuống (Top-down parsing): xây dựng CDX từ gốc xuống lá. 2. PTCP từ dưới lên (Bottom-up parsing): xây dựng CDX từ lá lên gốc. „ Ví dụ „ Cho văn phạm G sau: S → aAbS | bBS | λ (1, 2, 3) A → aAA | aS | b (4, 5, 6) B → bBB | bS | a (7, 8, 9) Hãy PTCP từ trên xuống cho chuỗi sau: w = aabbbba. Trang 171 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  172. Ví dụ về PTCP từ trên xuống „ Quá trình phân tích bắt đầu từ kí hiệu mục tiêu S. Là quá trình thay thế biến trong dạng câu để đi từ dạng này sang dạng câu khác chi tiết hơn cho đến khi hoặc đến được chuỗi cần phân tích hoặc không (còn được gọi là gặp lỗi). „ Việc PTCP từ trên xuống bao gồm hai đầu đọc, một đọc trên chuỗi kí hiệu nhập, di chuyển từ trái sang phải, một đọc trên các dạng câu, cũng di chuyển từ trái sang phải. Vào thời điểm khởi đầu, đầu đọc 1 nằm ở vị trí khởi đầu của chuỗi nhập, đầu đọc 2 nằm ở vị trí khởi đầu của dạng câu thứ nhất chính là kí hiệu mục tiêu S. Ta thể hiện mỗi đầu đọc bằng một dấu chấm •. „ Vấn đề cốt lõi của PTCP từ trên xuống là quyết định chọn vế phải nào trong các vế phải của biến cần thay thế mà có khả năng nhất sinh ra được chuỗi nhập. Trang 172 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  173. Ví dụ về PTCP từ trên xuống (tt) S → aAbS | bBS | λ (1, 2, 3) A → aAA | aS | b (4, 5, 6) DXTN: 1.4.6.6.2.9.3 B → bBB | bS | a (7, 8, 9) Khởi đầu 1 4 Chuỗi nhập •aabbbba •aabbbba a•abbbba a•abbbba aa•bbbba Dạng câu •S •aAbS a•AbS a•aAAbS aa•AAbS 6 6 Chuỗi nhập aa•bbbb aab•bbba aab•bbba aabb•bba aabbb•ba Dạng câu aaa•bAbS aab•AbS aab•bbS aabb•bS aabbb•S 2 9 3 Chuỗi nhập aabbb•ba aabbbb•a aabbbb•a aabbbba• aabbbba• Dạng câu aabbb•bBS aabbbb•BS aabbbb•aS aabbbba•S aabbbba• Trang 173 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  174. Ví dụ về PTCP từ dưới lên „ Hãy PTCP từ dưới lên cho w = abbcde trên văn phạm G sau: S → aABe (1) A → Abc | b (2, 3) B → d (4) B1. Các lá của cây dẫn xuất a b b c d e A B2. Thu giảm bằng A → b a b b c d e A A B3. Thu giảm bằng A → Abc Trang 174 a b b c d e Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  175. Ví dụ về PTCP từ dưới lên (tt) S → aABe (1) A → Abc | b (2, 3) A B → d (4) A B B4. Thu giảm bằng B → d a b b c d e S A A B B5. Thu giảm bằng S → aABe a b b c d e 3241 „ Kết quả: abbcde ⇐ aAbcde ⇐ aAde ⇐ aABe ⇐ S 1 4 23 „ Hay S ⇒ aABe ⇒ aAde ⇒ aAbcde ⇒ abbcde (DXPN) Trang 175 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  176. Phương pháp PTCP vét cạn „ Qua ví dụ trên ta thấy, vấn đề cốt lõi của PTCP từ dưới lên là là quyết định chọn chuỗi thành phần nào của dạng câu để thu gọn mà có khả năng nhấtthu gọn được về thành biến mục tiêu. „ Phương pháp phân tích cú pháp vét cạn (PPPTCPVC - exhaustive search parsing) 1. Ở lượt (round) thứ nhất xem xét tất cả các luật sinh có dạng S → x, tìm tất cả các x mà có thể được dẫn xuất từ S bởi một bước. 2. Nếu không có kết quả nào trong số này trùng với w, chúng ta sẽ đi tiếp đến lượt tiếp theo, trong đó chúng ta áp dụng tất cả các luật sinh có thể tới biến trái nhất của mỗi x. Trang 176 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  177. Phương pháp PTCP vét cạn (tt) 3. Trong mỗi lượt kế tiếp, chúng ta lại lấy tất cả các biến trái nhất và áp dụng tất cả các luật sinh có thể, rồi lặp lại bước 2. „ Nhận xét „ Sau lượt thứ n chúng ta có các dạng câu mà có thể được dẫn xuất từ S với n luật sinh. „ Nếu w ∈ L(G), thì nó phải có một DXTN có độ dài hữu hạn. Vì vậy phương pháp này cuối cùng sẽ tìm được một DXTN của w. „ Ví dụ „ Xét văn phạm S → SS | aSb | bSa | λ 1, 2, 3, 4 và chuỗi w = aabb. Trang 177 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  178. Ví dụ S → SS | aSb | bSa | λ 1, 2, 3, 4 w = aabb. Lượt 1 Lượt 2 1. S ⇒ SS 1.1 S ⇒ SS ⇒ SSS 2. S ⇒ aSb 1.2 S ⇒ SS ⇒ aSbS 3. S ⇒ bSa 1.3 S ⇒ SS ⇒ bSaS 4. S ⇒λ 1.4 S ⇒ SS ⇒ S 2.1 S ⇒ aSb ⇒ aSSb 2.2 S ⇒ aSb ⇒ aaSbb 2.3 S ⇒ aSb ⇒ abSab 2.4 S ⇒ aSb ⇒ ab „ Đến Lượt 3 ta tìm thấy 2.2.4 S ⇒ aSb ⇒ abSab ⇒ abab „ Vậy chuỗi aabb thuộc ngôn ngữ của văn phạm đang xét. Trang 178 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  179. Nhận xét „ PPPTCPVC có các nhược điểm nghiêm trọng sau. 1. Không hiệu quả. Bị bùng nổ tổ hợp. 2. Có khả năng không bao giờ kết thúc đối với các chuỗi ∉ L(G). Chẳng hạn với w = abb, phương pháp này sẽ đi đến việc sinh ra vô hạn các dạng câu mà không dừng lại, trừ phi chúng ta bổ sung thêm vào cách để cho nó dừng lại. „ Nhược điểm 2 có thể khắc phục được nếu chúng ta giới hạn văn phạm không được phép chứa các luật sinh rỗng (A →λ)và đơn vị (A → B). Trang 179 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  180. Định lý „ Định lý 5.2 „ Giả sử rằng G = (V, T, S, P) là một VPPNC mà không có bất kỳ luật sinh nào có dạng A → λ, hay A → B, trong đó A, B ∈V, thì PPPTCPVC có thể được hiện thực thành một giải thuật mà ∀ w ∈ T*, hoặc tạo ra được sự PTCP của w, hoặc biết rằng không có sự PTCP nào là có thể cho nó. „ Chứng minh „ Ở mỗi bước dẫn xuất hoặc chiều dài hoặc số kí hiệu kết thúc của dạng câu tăng ít nhất 1 đơn vị. Vì vậy sau không quá (2|w| - 1) lượt, chúng ta sẽ xác định được w có ∈ L(G) không. Trang 180 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  181. Định lý (tt) „ Định lý 5.3 „ Đối ∀ VPPNC ∃ giải thuật mà phân tích một chuỗi w bất kỳ có ∈ L(G) không trong một số bước tỉ lệ với |w|3. „ Nhận xét 3 „ Một PP mà thời gian tỉ lệ với |w| là không hiệu quả. Nếu một trình biên dịch dựa trên đósẽ cần một lượng thời gian khá lớn để PTCP cho thậm chí một chương trình có độ dài trung bình. „ Những gì mà chúng ta muốn là tỉ lệ với |w|. Chúng ta gọi những PP như vậy là PPPTCP thời gian tuyến tính. „ Tổng quát, chúng ta không biết một PPPTCP thời gian tuyến tính nào cho NNPNC, nhưng các PP như thế có thể được tìm thấy đối với một số lớp VP đặc biệt. Trang 181 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  182. Văn phạm-s „ Văn phạm-s (simple grammar) „ Là một VPPNC trong đó các luật sinh có dạng A → ax trong đó A ∈ V, a ∈ T, x ∈ V*, và mỗicặp (A, a) chỉ có thể xuất hiện tối đa trên một luật sinh. Nói cách khác, nếu hai luật sinh bất kỳ mà có vế trái giống nhau thì vế phải của chúng phải bắt đầu bằng các kí hiệu kết thúc khác nhau. „ Ví dụ „ Bên dưới là một ví dụ về văn phạm-s S → aS | bA (1, 2) A → aAA | b (3, 4) Trang 182 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  183. Văn phạm-s (tt) „ Văn phạm-s cho phép PTCP một chuỗi w bất kỳ không quá |w| bước. „ Với mỗi cặp (A, a) trong đó A là biến cần thay thế, a là kí hiệu đang được xét ở chuỗi nhập, có tối đa một vế phải của A có thể được áp dụng. S → aS | bA (1, 2) „ Ví dụ với VP trên việc PTCP chuỗi ababb A → aAA | b (3, 4) chỉ tốn 5 bước và được kết quả như sau. 3 S ⇒12aS ⇒ abA ⇒ abaAA ⇒ 4ababA ⇒4 ababb „ Văn phạm-s có thể mở rộng ở x, bằng cách cho x ∈ (V ∪ T)*. Điều này không làm thay đổi khả năng và tính chất của văn phạm mà còn làm quá trình PTCP đơn giản hơn một chút. „ Ngôn ngữ Pascal có thể được biểu thị bằng văn phạm-s. Trang 183 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  184. Tính nhập nhằng trong VP và NN „ Định nghĩa 5.4 „ Một VPPNC G được gọi là nhập nhằng nếu ∃ một w ∈ L(G) mà có ít nhất hai CDX khác nhau. Nói cách khác, sự nhập nhằng suy ra tồn tại hai hay nhiều DXTN hay PN. „ Ví dụ „ Xét văn phạm sau G = (V, T, E, P) với V = {E, I}, T = {a, b, c, +, *, (, )} và các luật sinh E → I | E + E | E * E | (E) I → a | b | c „ Văn phạm này là nhập nhằng vì với chuỗi a + b * c có hai CDX khác nhau trên G như sau. Trang 184 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  185. Tính nhập nhằng trong VP và NN (tt) E E E E + E E * E E + T I E * E E + E I T T * F a I I I I c F F I b c a b I I c „ VP sau tương đương với VP trên a b nhưng không có nhập nhằng. E → T | E + T „ Tập biến V = {E, T, F, I} T → F | T * F F → I | (E) Trang 185 I → a | b | c Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  186. Tính nhập nhằng trong VP và NN (tt) „ Định nghĩa 5.5 „ Nếu L là một NNPNC mà đối với nó ∃ một VP không nhập nhằng, thì L được gọi là không nhập nhằng. Nếu mọi VP sinh ra L mà nhập nhằng, thì NN được gọi là nhập nhằng cố hữu. „ Ví dụ n n m n m m „ Ngôn ngữ L = {a b c } ∪ { a b c } với n, m không âm là một NNPNC nhập nhằng cố hữu. (Chú ý L = L1 ∪ L2). G1: S1 → X1C G2: S2 → AX2 X1 → aX1b | λ X2 → bX2c | λ C → cC | λ A → aA | λ „ Một VP cho L bằng cách kết hợp hai VP trên với luật sinh thêm vào là S → S1 | S2 Trang 186 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  187. Tính nhập nhằng trong VP và NN (tt) n n n „ Văn phạm này là nhập nhằng vì chuỗi a b c thuộc cả L1 lẫn L2 nên nó có hai dẫn xuất riêng biệt một cái bắt đầu bằng S ⇒ S1 và một cái bắt đầu bằng S ⇒ S2. „ Điều này cũng gợi ý cho chúng ta chứng minh rằng mọi VP cho L đều sẽ nhập nhằng trên chuỗi anbncn tương tự như trường hợp trên. „ Một chứng minh chặt chẽ đã được thực hiện trong tài liệu của Harrison năm 1978. Ở đây nó được để lại như bài tập cho các bạn. Trang 187 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  188. VPPNC và ngôn ngữ lập trình „ Một ứng dụng quan trọng của lý thuyết NNHT là định nghĩa các NNLT cũng như xây dựng các trình dịch cho chúng. „ Theo truyền thống người ta dùng dạng ký pháp Backus-Naur (viết tắt là BNF) để viết một NNLT . Chẳng hạn ::= | + , ::= | * , ::= if „ Văn phạm-s không đủ sức để biểu diễn các NNLT. „ Có hai loại văn phạm là LL và LR có khả năng biểu diễn các NNLT, và còn cho phép PTCP trong thời gian tuyến tính. „ Không ∃ giải thuật loại bỏ sự nhập nhằng của VP. „ VPPNC không thể biểu diễn mặt ngữ nghĩa của các NNLT. Trang 188 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  189. Chương 6 Đơn giản hóa VPPNC và các dạng chuẩn 6.1 Các phương pháp để biến đổi văn phạm 6.2 Hai dạng chuẩn quan trọng 6.3 Giải thuật thành viên cho văn phạm phi ngữ cảnh Trang 189 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  190. Các phương pháp để biến đổi văn phạm „ Chuỗi trống đóng một vai trò khá đặc biệt trong nhiều định lý và chứng minh, và thường cần có một sự chú ý đặc biệt cho nó. „ Nếu L ∋λthì biểu diễn L = L1 ∪ {λ} với L1 = L –{λ}. Nếu G1 = (V1, T, S1, P1) là văn phạm biểu diễn cho L1 thì G = (V1 ∪ {S}, T, S, P1 ∪ {S → S1 | λ}) là văn phạm biểu diễn cho L. „ Trong chương này, chúng ta chỉ xem xét các NNPNC không chứa λ. „ Tuy nhiên những kết luận cho ngôn ngữ không chứa λ vẫn có thể áp dụng cho ngôn ngữ có chứa λ. Trang 190 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  191. Một vài qui tắc thay thế hiệu quả „ Định lý 6.1 „ Cho G = (V, T, S, P) là một VPPNC. Giả sử P có chứa luật sinh A → x1Bx2 trong đó A, B là các biến khác nhau và B → y1 | y2 | | yn là tập tất cả các luật sinh trong P mà có B ở vế trái. Cho G1= (V, T, S, P1) là VP được xây dựng bằng cách xóa đi A → x1Bx2 từ P, và thêm vào nó A → x1y1x2 | x1y2x2| | x1ynx2 Thì L(G) = L(G1) Trang 191 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  192. Ví dụ „ Xét văn phạm G = ({A, B}, {a, b}, A, P) với các luật sinh A → a | aA | bBc, B → abA | b. Sau khi thay thế biến B ta nhận được VP tương đương như sau A → a | aA | babAc | bbc, B → abA | b „ Chuỗi abbc có các dẫn xuất trong G và G1 lần lượt như sau: A ⇒ aA ⇒ abBc ⇒ abbc A ⇒ aA ⇒ abbc „ Chú ý rằng, biến B và các luật sinh của nó vẫn còn ở trong VP mặc dù chúng không còn đóng vai trò gì trong bất kỳ dẫn xuất nào. Sau này chúng ta sẽ thấy rằng những luật sinh không cần thiết như vậy có thể bị loại bỏ ra khỏi văn phạm. Trang 192 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  193. Loại bỏ đệ qui trái „ Định lý 6.2 (Loại bỏ đệ qui trái) „ Cho G = (V, T, S, P) là một VPPNC. Chia tập các luật sinh mà vế trái của chúng là một biến đã cho nào đó(chẳng hạn là A), thành hai tập con riêng biệt A → Ax1 | Ax2 | | Axn (6.2) A → y1 | y2 | | ym (6.3) với xi, yi ∈ (V ∪ T)*, và A không là prefix của bất kỳ yi nào. Xét G1 = (V ∪ {Z}, T, S, P1), trong đó Z ∉ V và P1 nhận được bằng cách thay mọi luật sinh của P có dạng (6.2 ) và (6.3) bởi A → yi | yiZ, i = 1, 2, . . . , m, Z → xi | xiZ, i = 1, 2, . . . , n, Thì L(G) = L(G1). Trang 193 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  194. Loại bỏ đệ qui trái (tt) „ Chứng minh „ Các dạng câu mà A sinh ra trong văn phạm G có dạng: * AA⇒ (x1 + x2 + + xn)* ⇒ yi(x1 + x2 + + xn)* Các dạng câu này cũng có thể được sinh ra trong G1 bằng cách chú ý Z có thể sinh ra các dạng câu có dạng * Z ⇒ (x1 + x2 + + xn)(x1 + x2 + + xn)* mà A → y | y Z nên i i * Ay⇒ i(x1 + x2 + + xn)* Vì vậy L(G) = L(G1). „ Ghi chú „ Các luật sinh đệ qui-trái chỉ là một trường hợp đặc biệt của đệ qui-trái trong văn phạm như được phát biểu sau. „ Một văn phạm được gọi là đệ qui-trái nếu có một biến A nào đó mà đối với nó AAx⇒* là có thể. Trang 194 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  195. Ví dụ „ Sử dụng Định lý 6.2 để loại bỏ các luật sinh đệ qui-trái khỏi VP A → Aa | aBc | λ B → Bb | ba „ Áp dụng định lý cho biến A ta được tập luật sinh mới như sau: A → aBc | λ | aBcZ | Z B → Bb | ba Z → a | aZ „ Áp dụng định lý một lần nữa lần này cho biến B ta được tập luật sinh kết quả cuối cùng như sau: A → aBc | aBcZ | Z | λ B → ba | baY Z → a | aZ Y → b | bY „ Nhận xét „ Việc loại bỏ các luật sinh đệ qui-trái đưa ra các biến mới. VP kết quả có thể là "đơn giản" hơn đáng kể so với VP gốc nhưng một cách tổng quát nó sẽ có nhiều biến và luật sinh hơn. Trang 195 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  196. Luật sinh vô dụng „ Định nghĩa 6.1: „ Cho G = (V, T, S, P) là một VPPNC. Một biến A ∈ V được gọi là khả dụng nếu và chỉ nếu có ít nhất một chuỗi w ∈ L(G) sao cho SxAyw⇒* ⇒* , với x, y ∈ (V ∪ T)*. Bằng lời, một biến là khả dụng nếu và chỉ nếu nó xuất hiện trong ít nhất một dẫn xuất. Một biến mà không khả dụng thì gọi là vô dụng. Một luật sinh được gọi là vô dụng nếu nó có chứa bất kỳ biến vô dụng nào. „ Các dạng vô dụng „ Vô dụng loại 1: Aw⇒* ∈ T* „ Vô dụng loại 2: SxAy⇒* Trang 196 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  197. Loại bỏ các luật sinh vô dụng „ Định lý 6.3 „ Cho G = (V, T, S, P) là một VPPNC, ∃ một VP tương đương G0 = (V0, T, S, P0) mà không chứa bất kỳ biến vô dụng nào. „ Chứng minh „ Loại bỏ các biến và luật sinh vô dụng loại 1 Tạo văn phạm G1 = (V1, T, S, P1) với V1 là tập biến không vô dụng loại 1. Ta tìm V1 như sau: 1. Khởi tạo V1 = ∅. 2. Lặp lại bước sau cho đến khi không còn biến nào được thêm vào V1. „ Đối với mỗi A ∈ V mà có luật sinh A → x, x ∈ (V1∪T)*, thì thêm A vào V1. 3. Loại khỏi P các luật sinh có chứa các biến ∉ V1, ta được P1. Trang 197 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  198. Loại bỏ các luật sinh vô dụng (tt) „ Để loại tiếp các biến và các luật sinh vô dụng loại 2 ta dựa vào G1 vừa có ở trên và vẽ đồ thị phụ thuộc cho nó, sau đótìm tập các biến không đạt tới được từ S. Loại các biến này và các luật sinh liên quan đến nó ra khỏi G1 ta được văn phạm kết quả G0. „ Đồ thị phụ thuộc (dependency graph) „ Là một đồ thị có các đỉnh biểu diễn các biến, còn một cạnh nối hai đỉnh A và B khi và chỉ khi có luật sinh dạng A → xBy A B „ Ví dụ „ Loại bỏ các biến và các luật sinh vô dụng ra khỏi văn phạm G = ({S, A, B, C}, {a, b}, S, P), với tập luật sinh P là: S → aS | A | C B → aa A → aC → aCb Trang 198 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  199. Ví dụ „ Loại bỏ các biến vô dụng loại 1 ta được S → aS | A | C V1 = {S, A, B} và tập luật sinh P1 A → a S → aS | A B → aa A → a C → aCb B → aa „ Loại bỏ các biến vô dụng loại 2 ta được S A B văn phạm kết quả S → aS | A A → a „ Nhận xét „ Nếu thay đổi thứ tự loại bỏ (loại bỏ các biến và luật sinh vô dụng loại 2 trước) thì sẽ không loại bỏ được tất cả các biến và luật sinh vô dụng chỉ bằng một lần như ví dụ sau cho thấy. Trang 199 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  200. Ví dụ (tt) „ Xét văn phạm sau S → aSb | ab | A A → aAB B → b „ Nếu loại bỏ các biến và luật sinh vô dụng loại 2 trước ta thấy văn phạm vẫn không thay đổi vì tất cả các biến đều đạt tới được từ S. Sau đóloại bỏ tiếp các biến và luật sinh vô dụng loại 1 ta sẽ được văn phạm sau: S → aSb | ab | A B → b „ Rõ ràng văn phạm này còn biến B là vô dụng loại 2. Trang 200 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  201. Loại bỏ luật sinh-λ „ Định nghĩa 6.2 „ Bất kỳ luật sinh nào của VPPNC có dạng A → λ được gọi là luật sinh-λ. Bất kỳ biến A nào mà A⇒* λ là có thể thì được gọi là khả trống (nullable). „ Định lý 6.4 „ Cho G là một VPPNC bất kỳ mà L(G) không chứa λ, thì tồn tại một văn phạm G0 tương đương mà không có chứa luật sinh-λ. „ Chứng minh: Bước 1 „ Tìm tập VN tất cả các biến khả trống của G bằng các bước sau. Trang 201 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  202. Loại bỏ luật sinh-λ 1. Đối với mọi luật sinh A → λ, đưa A vào VN. 2. Lặp lại bước sau cho đến khi không còn biến nào được thêm vào VN. „ Đối với mọi luật sinh B → A1A2 An, mà A1, A2, An ∈ VN thì đặt B vào VN. Bước 2 „ Sau khi có tập VN ta xây dựng tập luật sinh như sau. „ Ứng với mỗi luật sinh có dạng A → x1x2 xm, m ≥ 1, trong đó mỗi xi ∈ V ∪ T, đặt luật sinh này vào cùng với các luật sinh được sinh ra bằng cách thay thế các biến khả trống bằng λ trong mọi tổ hợp có thể, ngoại trừ nếu tất cả các xi đều khả trống thì không đặt luật sinh A → λ vào P0 của G0 Trang 202 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  203. Ví dụ „ Loại bỏ các luật sinh-λ của văn phạm sau: S → ABaC C → D | λ A → BC D → d B → b | λ „ Vì B → λ và C → λ suy ra B và C là các biến khả trống. „ Vì A → BC nên suy ra A cũng là biến khả trống. Ngoài ra không còn biến nào khác là khả trống. „ Theo Bước 2 ta xây dựng được tập luật sinh mới tương đương như sau: S → ABaC | BaC | AaC | ABa | aC | Aa | Ba | a A → BC | B | C B → b C → D D → d Trang 203 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  204. Loại bỏ luật sinh đơn vị „ Định nghĩa 6.3 „ Bất kỳ luật sinh nào của VPPNC có dạng A → B trong đó A, B ∈ V được gọi là luật sinh-đơn vị. „ Định lý 6.5 „ Cho G = (V, T, S, P) là một VPPNC bất kỳ không có luật sinh- λ, thì tồn tại một VPPNC G1 = (V1, T, S, P1) mà không có bất kỳ luật sinh đơn vị nào và tương đương với G1. „ Chứng minh 1. Đặt vào trong P1 tất cả các luật sinh không đơn vị của P. 2. Đối với mỗi biến A tìm tất cả các biến B mà AB⇒* (*) „ Điều này thực hiện bằng cách vẽ đồ thị phụ thuộc cho G nhưng một cạnh nối 2 đỉnh A và B khi và chỉ khi có luật sinh-đơn vị A → B. Hai biến A và B thõa (*) khi và chỉ khi có một con đường trong đồ thị đi từ A đến B. Trang 204 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  205. Ví dụ 3. Đối với mỗi A, B thõa (*) thêm vào trong P1 các luật sinh A → y1 | y2 | | yn với B → y1 | y2 | | yn là các luật sinh không đơn vị của B. „ Ví dụ „ Loại bỏ các luật sinh đơn vị Trước hết, đặt các luật sinh cho VP sau không đơn vị vào trong P1 S → Aa | B S → Aa B → A | bb A → a | bc A → a | bc | B B → bb Từ ĐTPT ta đưa được thêm các luật sinh sau vào S A B S → a | bc | bb A → bb Trang 205 B → a | bc Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  206. Ví dụ (tt) „ Kết quả ta có văn phạm tương đương sau không có luật sinh đơn vị S → Aa | a | bc | bb A → a | bc | bb B → bb | a | bc „ Định lý 6.6 „ Cho L là một NNPNC không chứa λ, tồn tại một VPPNC sinh ra L mà không chứa bất kỳ luật sinh vô dụng, luật sinh-λ, hay luật sinh-đơn vị nào. „ Chứng minh: B1. Loại bỏ luật sinh-λ B2. Loại bỏ luật sinh đơn vị B3. Loại bỏ luật sinh vô dụng loại 1, rồi vô dụng loại 2 Trang 206 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  207. Một số nhận xét 1. Loại bỏ biến vô dụng loại 1 có thể sinh ra biến vô dụng loại 2. 2. Việc loại bỏ biến vô dụng loại 2 không sinh ra biến vô dụng loại 1. 3. Văn phạm không có luật sinh đơn vị thì việc loại bỏ luật sinh-λ có thể sinh ra luật sinh-đơn vị. 4. Văn phạm không có luật sinh-λ thì việc loại bỏ luật sinh-đơn vị không thể sinh ra luật sinh-λ mới. 5. Loại bỏ luật sinh-λ có thể sinh ra biến vô dụng loại 1. 6. Loại bỏ luật sinh-đơn vị có thể sinh ra biến vô dụng loại 2. 7. Văn phạm không có luật sinh-λ, luật sinh-đơn vị thì việc loại bỏ các luật sinh vô dụng loại 1, loại 2 không sinh ra thêm bất kỳ luật sinh-λ và luật sinh-đơn vị nào mới. Trang 207 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  208. Dạng chuẩn Chomsky „ Định nghĩa 6.4 „ Một VPPNC là thuộc dạng chuẩn Chomsky nếu mọi luật sinh có dạng A → BC, hoặc A → a trong đó A, B, C ∈ V, còn a ∈ T. „ Định lý 6.7 „ Bất kỳ VPPNC G = (V, T, S, P) nào với λ∉L(G) đều có một văn phạm tương đương G1 = (V1, T, S, P1) có dạng chuẩn Chomsky. „ Chứng minh „ Không mất tổng quát giả sử G không có luật sinh-vô dụng, luật sinh-đơn vị và luật sinh-λ. Ta xây dựng văn phạm G1 có dạng chuẩn Chomsky bằng thủ tục sau: Trang 208 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  209. Thủ tục: G-to-GChomsky „ Input: G = (V, T, S, P) với λ∉L(G) „ Output: G1 = (V1, T, S, P1) có dạng chuẩn Chomsky. 1. Đặt các luật sinh A → a vào P1. 2. Đối với các luật sinh A → x1x2 xn với n ≥ 2, xi ∈ (V ∪ T) thì thay các kí hiệu kết thúc, chẳng hạn xk = a, bằng các biến đại diện mới Ba, tạo thành các luật sinh trung gian A → C1C2 Cn. 3. Ứng với mỗi biến đại diện Ba đặt vào P1 các luật sinh Ba → a. 4. Sau khi thực hiện bước 2, ứng với mỗi luật sinh A → C1C2 Cn mà n = 2 đặt nó vào P1. Ngược lại ứng với n > 2 ta giới thiệu các biến mới D1, D2, và đưa vào các luật sinh sau: A → C1D1 D1 → D1D2 M Dn-2 → Cn-1Cn Trang 209 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  210. Ví dụ „ Hãy biến đổi VP sau thành VP có dạng chuẩn Chomsky. 1 S → a S → AD1 ớc Bư B → b c 4 D1 → BXa ướ B A → XaD2 S → a | ABa S → ABX Bước 2 a D2 → XaXb A → aab A → XaXaXb B → b | Ac B → AXc S → a | AD1 B D1 → BXa ướ X → a c 3 a A → XaD2 X → b b Kết quả D2 → XaXb X → c c B → b | AXc Xa → a Xb → b Trang 210 Xc → c Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  211. Dạng chuẩn Greibach „ Định nghĩa 6.5 „ Một VPPNC là thuộc dạng chuẩn Greibach nếu mọi luật sinh có dạng A → ax trong đó a ∈ T còn x ∈ V*. „ Định lý 6.8 „ Đối với mọi VPPNC G với λ∉L(G), thì tồn tại một văn phạm tương đương trong dạng chuẩn Greibach. „ Chứng minh „ Không mất tính tổng quát giả sử G không có luật sinh-vô dụng, luật sinh-đơn vị và luật sinh-λ. Ta xây dựng văn phạm có dạng chuẩn Greibach bằng thủ tục sau. Trang 211 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  212. Thủ tục: G-to-GGreibach „ Input: G = (V, T, S, P) với λ∉L(G) „ Output: G1 = (V1, T, S, P1) có dạng chuẩn Greibach. 1. Đánh số thứ tự cho các biến chẳng hạn là A1, A2, . . . An. 2. Dùng Định lý 6.1 và 6.2 để viết lại VP sao cho các luật sinh có một trong ba dạng sau Ai → Ajxj, i j thì thay Aj đi đầu bằng các vế phải của nó, và làm cho đến khi các luật sinh của Ai có dạng Ai → Ajx, i ≤ j. Đến đây loại đệ qui trái cho Ai thì các luật sinh của nó sẽ có dạng như đã nêu. Trang 212 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  213. Thủ tục: G-to-GGreibach (tt) 3. Sau khi thực hiện bước 2, tất cả các luật sinh của An phải có dạng An → axn „ Thay An đi đầu vế phải của các luật sinh bằng các vế phải của nó. Kết quả các luật sinh của An-1 có dạng An-1 → axn-1 „ Tương tự thay thế An-1 đi đầu vế phải của các luật sinh bằng các vế phải của nó. Và thực hiện lần lượt cho đến A1. 4. Thay các kí hiệu kết thúc, chẳng hạn a, không đi đầu vế phải bằng các biến đại diện, chẳng hạn Xa, đồng thời thêm vào các luật sinh mới Xa → a. „ Ví dụ S → SBb | Ab „ Biến đổi VP sau thành VP A → Sb | Ba có dạng chuẩn Greibach Trang 213 B → Sa | b Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin