›
›

Ngôn ngữ hình thức & ôtômát

ppt 174 trang phuongnguyen 2350
Download
Bạn đang xem 20 trang mẫu của tài liệu "Ngôn ngữ hình thức & ôtômát", để 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:

  • pptngon_ngu_hinh_thuc_otomat.ppt

Nội dung text: Ngôn ngữ hình thức & ôtômát

  1. ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN NGÔN NGỮ HÌNH THỨC & ÔTÔMÁT Giáo trình Kiến trúc máy tính và Hệ 1 điều hành
  2. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG Giới thiệu Mục tiêu giáo trình 1. Cung cấp những kiến thức cơ bản về ngôn ngữ, văn phạm và ôtômát. 2. Cung cấp các phương pháp phân tích từ vựng, phân tích cú pháp. 3. Cơ sở cho việc tìm hiểu các ngôn ngữ lập trình. 4. Rèn luyện kỹ năng lập trình cho sinh viênGiáo trình Kiến trúc máy tính và Hệ 2 điều hành
  3. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG Giới thiệu Nội dung giáo trình CHƯƠNG 1. MỞ ĐẦU CHƯƠNG 2. ÔTÔMÁT HỮU HẠN CHƯƠNG 3. BIỂU THỨC VÀ VĂN PHẠM CHÍNH QUI CHƯƠNG 4. VĂN PHẠM VÀ NGÔN NGỮ PHI NGỮ CẢNH CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG CHƯƠNG 6. MÁY TURING Giáo trình Kiến trúc máy tính và Hệ 3 điều hành
  4. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU ❖ Một số vấn đề về ngôn ngữ ❖ Khái niệm văn phạm ❖ Khái niệm Ôtômát Giáo trình Kiến trúc máy tính và Hệ 4 điều hành
  5. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.1. Xâu - Bộ chữ (bảng chữ) là tập hợp hữu hạn các ký hiệu Ví dụ:{0,1} bộ chữ gồm 2 ký hiệu 0 và 1 {a,b,c, ,z} bộ chữ gồm các ký hiệu a →z Tập các chữ cái tiếng việt Giáo trình Kiến trúc máy tính và Hệ 5 điều hành
  6. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.1. Xâu - Xâu trên bộ chữ V là 1 dãy các ký hiệu của V Ví dụ: 0110 là xâu trên bộ chữ {0,1} a, ab, giathanh là xâu trên bộ chữ {a,b, ,z} - Độ dài xâu là số các ký hiệu trong xâu Ký hiệu: độ dài xâu x là |x| Giáo trình Kiến trúc máy tính và Hệ 6 Ví dụ: |01110|=5điều hành
  7. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.1. Xâu - Xâu rỗng là xâu có độ dài bằng 0 Ký hiệu: , ||=0 - Tập tất cả các xâu trên V là V*, {}V* V+ =V *-{} V*: tập vô hạn đếm được *={ Giáo trình Kiến trúc máy tính và Hệ Ví dụ: V={a,b}→V ,a,b,aa,bb,ab,ba, 7 } điều hành
  8. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.1. Xâu - Các phép toán trên xâu • Ghép tiếp: cho 2 xâu x,y. Ghép tiếp của x, y là x.y hay xy là 1 xâu viết x trước, rồi đến y sau chứ không có dấu cách. Ví dụ: x=01 y=0110 Giáo trình Kiến trúc máy tính và Hệ 8 xy=010110điều hành
  9. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.1. Xâu • Đảo ngược xâu x (xr): xâu được viết theo thứ tự ngược lại của xâu x Ví dụ: x=0101 →xr =1010 Chú ý: r= , 1r =1 - Xâu x mà x=xr thì x là xâu hình tháp (xâu đối xứng) Giáo trình Kiến trúc máy tính và Hệ r 9 Ví dụ: x=0110điều → hànhx =0110, x: xâu hình tháp
  10. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.1. Xâu • Lũy thừa xâu x (xn): xâu nhận được bằng cách ghép tiếp chính xâu x n lần. xn = x.x.x x (n lần x) x0 =  với mọi xâu x Ví dụ: x=01 →x3 =010101 10=  Giáo trình Kiến trúc máy tính và Hệ 10 điều hành
  11. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.2. Ngôn ngữ - Ngôn ngữ L trên bộ chữ V là tập hợp các xâu trên V, LV* - Các phép toán trên ngôn ngữ • Vì ngôn ngữ là tập hợp nên có các phép toán tập hợp: (giao), (hợp), -(hiệu), bù • Ghép tiếp 2 ngôn ngữ Giáo trình Kiến trúc máy tính và Hệ 11 điều hành
  12. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.2. Ngôn ngữ - Các phép toán trên ngôn ngữ: Cho L1, L2 trên bộ chữ V • Phép giao: L1L2 = {x | x L1 và x L2} • Phép hợp: L1L2 = {x | x L1 hoặc x L2} • Phép hiệu: L1- L2 = {x | x L1 và x L2} * Giáo trình Kiến trúc máy tính và Hệ • Phép bù: L=V - L 12 điều hành
  13. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.2. Ngôn ngữ • Ghép tiếp 2 ngôn ngữ Cho 2 ngôn ngữ L1, L2. Ta gọi ghép tiếp L1.L2 (L1L2) của L1 và L2 là một tập hợp L1L2={xy/(x L1) và (y L2)} x.x=x2; x.x.x=x3; x0=; xi=xi-1x L0={}; Li=Li-1.L Giáo trình Kiến trúc máy tính và Hệ 0 1 2 + 1 2 13 - L*=L L Lđiều hành ; L =L L  
  14. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.3. Biểu diễn ngôn ngữ ❖ Ngôn ngữ đơn giản - Phương pháp liệt kê: ngôn ngữ có số xâu là hữu hạn và có thể xác định được. Ví dụ: ngôn ngữ là các số tự nhiên nhỏ hơn 20 và lớn hơn 12 L={13, 14, 15, 16, 17, 18, 19} Giáo trình Kiến trúc máy tính và Hệ 14 điều hành
  15. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.3. Biểu diễn ngôn ngữ ❖ Ngôn ngữ đơn giản - Phương pháp sử dụng tân từ P(x): ngôn ngữ mà các xâu có cùng các đặc điểm. Ví dụ: ngôn ngữ là các số thực nhỏ hơn 5. L={x/ (x R) và (x<5)} Giáo trình Kiến trúc máy tính và Hệ 15 điều hành
  16. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 1. Một số vấn đề về ngôn ngữ 1.3. Biểu diễn ngôn ngữ ❖ Ngôn ngữ phức tạp - Văn phạm: cơ chế để sản sinh ra ngôn ngữ - Đối với ngôn ngữ tự nhiên: văn phạm là hệ thống ngữ pháp. - Đối với ngôn ngữ lập trình: văn phạm là qui tắc cú pháp viết chương trình. Giáo trình Kiến trúc máy tính và Hệ 16 điều hành
  17. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.1. Định nghĩa: G=(Σ, Δ, s, p) trong đó: Σ: tập hữu hạn các ký hiệu kết thúc. Δ: tập hữu hạn các ký hiệu chưa kết thúc. s: ký hiệu bắt đầu; s Δ p: tập hữu hạn các sản xuất có dạng → với - (Σ  Δ)+, có ít nhất một ký hiệu chưa kết thúc Giáo trình Kiến trúc máy tính và Hệ 17 -  (ΣΔ)*điều hành
  18. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.1. Định nghĩa: G=(Σ, Δ, s, p) trong đó: Σ: tập hữu hạn các ký hiệu kết thúc. Δ: tập hữu hạn các ký hiệu chưa kết thúc. s: ký hiệu bắt đầu; s Δ p: tập hữu hạn các sản xuất có dạng → với - (Σ  Δ)+, có ít nhất một ký hiệu chưa kết thúc Giáo trình Kiến trúc máy tính và Hệ 18 -  (ΣΔ)*điều hành
  19. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm ❖ Qui ước: - Ký hiệu kết thúc được viết bằng chữ thường - Ký hiệu chưa kết thúc được viết bằng chữ in - Ký hiệu chưa kết thúc nằm bên trái của sản xuất đầu tiên là ký hiệu bắt đầu. Giáo trình Kiến trúc máy tính và Hệ 19 điều hành
  20. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.2. Các khái niệm ➢ Xâu (câu) và dạng câu: - gọi là xâu khi Σ* - gọi là dạng câu khi (ΣΔ)* Giáo trình Kiến trúc máy tính và Hệ 20 điều hành
  21. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.2. Các khái niệm ➢ Quan hệ suy dẫn: - A có quan hệ suy dẫn ra hay được suy dẫn từ A, có nghĩa là từ A áp dụng các sản xuất sinh ra được - Quan hệ suy dẫn trực tiếp: từ A áp dụng một sản xuất sinh được * Giáo trình Kiến trúc máy tính và Hệ Ký hiệu: A với A Δ và (ΣΔ) 21 điều hành
  22. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.2. Các khái niệm ➢ Quan hệ suy dẫn: - Quan hệ suy dẫn nhiều lần: từ A áp dụng nhiều sản xuất mới sinh được Ký hiệu: A + với A Δ và (ΣΔ)* - Độ dài suy dẫn: số lần áp dụng các sản xuất - Độ dài của suy dẫn trực tiếp bằng 1 Giáo trình Kiến trúc máy tính và Hệ 22 điều hành
  23. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.3. Ngôn ngữ được sinh ra từ văn phạm - Tập hợp các câu được sinh ra từ văn phạm sẽ tạo nên ngôn ngữ. - Xác định câu được sinh ra từ văn phạm: Từ ký hiệu bắt đầu của văn phạm áp dụng các sản xuất để sinh các câu. Giáo trình Kiến trúc máy tính và Hệ 23 điều hành
  24. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.3. Ngôn ngữ được sinh ra từ văn phạm (1) (2) - Ví dụ: cho G: S→0S1 |  (1) (2) S==>0S1==>01 (1) (1) (2) S==>0S1==>00S11==>0011 (1) (1) (1) (2) S==>0S1==>00S11==>000S111==>000111 Vậy L(G)={0n1n | với n>=0} Giáo trình Kiến trúc máy tính và Hệ 24 điều hành
  25. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.3. Ngôn ngữ được sinh ra từ văn phạm - Ví dụ 2: Cho G: S→aA A→aA | b L(G)={anb | n>0} Giáo trình Kiến trúc máy tính và Hệ 25 điều hành
  26. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.4. Phân cấp văn phạm của Chomsky - Nếu các sản xuất đều có dạng A→a |aB với A,B ;a : văn phạm chính quy (VP loại 3) - Nếu các sản xuất có dạng A→ với A ; ( )*: văn phạm phi ngữ cảnh (VP loại 2) - Nếu các sản xuất có dạng → với ,  ( )*: văn phạm cảm ngữ cảnh (VP loại 1) Giáo trình Kiến trúc máy tính và Hệ - Nếu không có hạn chế gì trên sản xuất: văn26 phạm tự do (VP loạiđiều 0) hành
  27. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 2. Văn phạm 2.4. Phân cấp văn phạm của Chomsky ❖ Lưu ý: - Văn phạm loại 3 là trường hợp đặc biệt của văn phạm loại 2. - Văn phạm loại 2 là trường hợp đặc biệt của văn phạm loại 1. - Văn phạm loại 1 là trường hợp đặc biệt của văn Giáo trình Kiến trúc máy tính và Hệ phạm loại 0. 27 điều hành
  28. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU 3. Khái niệm Ôtômát - Bộ gồm: tập các trạng thái và các điều khiển dịch chuyển từ trạng thái này sang trạng thái khác khi nhận dữ liệu vào. - Ôtômát biểu diễn hoạt động của bóng điện ấn công tắc Tắt Bật - Ôtômát đoán nhận từ khóa int i n t i in int Giáo trình Kiến trúc máy tính và Hệ 28 điều hành
  29. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN ❖ Ôtômát hữu hạn đơn định(DFA) ❖ Ôtômát hữu hạn không đơn định(NFA) ❖ Sự tương đương của DFA và NFA ❖ Ứng dụng Giáo trình Kiến trúc máy tính và Hệ 29 điều hành
  30. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định(Deterministic finite automata –DFA) 1.1. Mô tả - Ôtômát hữu hạn là một cái máy đoán nhận xâu gồm: • Một băng vào được chia thành nhiều ô, mỗi ô chứa một ký hiệu của xâu vào • Một đầu đọc, mỗi thời điểm trỏ vào một ô trên băng Giáo trình Kiến trúc máy tính và Hệ 30 điều hành
  31. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.1. Mô tả • Một bộ điều khiển Q gồm các trạng thái, tại mỗi thời điểm nó có một trạng thái được xác định qua hàm chuyển trạng thái 0 1 0 1 1 Băng vào Đầu đọc Bộ điều khiển q Giáo trình Kiến trúc máy tính và Hệ 31 điều hành
  32. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.1. Mô tả - Tại một thời điểm, trạng thái q ở bộ điều khiển và ký hiệu mà đầu đọc đang đọc sẽ xác định trạng thái tiếp theo ở bộ điều khiển. - Mỗi lần đọc xong một ô, đầu đọc chuyển sang phải một ô. - Trạng thái đầu tiên ở bộ điều khiển: trạng thái bắt đầu của ôtômát Giáo trình Kiến trúc máy tính và Hệ 32 điều hành
  33. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.2. Định nghĩa: M(Σ, Q, δ, q0, F) Σ: bộ chữ vào Q: tập hữu hạn các trạng thái q0 Q: trạng thái đầu F  Q: tập các trạng thái kết thúc δ: hàm chuyển trạng thái có dạng δ(q,a)=p Với q,p Q, a Σ Với mỗi δ(q,a)=p chỉ có một trạng thái p duy nhất Giáo trình Kiến trúc máy tính và Hệ 33 điều hành
  34. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.2. Định nghĩa: - Ví dụ: DFA M(Σ, Q, δ, q0, F) Σ: {0,1} Q: {0,1} q0: 0 F: {1} tập các trạng thái kết thúc Giáo trình Kiến trúc máy tính và Hệ δ: δ(0,0)=0, δ(0,1)=1, δ(1,1)=1 và δ(1,0)=034 điều hành
  35. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Otomat hữu hạn đơn định 1.3. Biểu diễn các hàm chuyển trạng thái ❖ Dùng bảng: sử dụng ma trận δ có: - Chỉ số hàng: trạng thái - Chỉ số cột: ký hiệu vào - Giá trị tại hàng q, cột a là trạng thái p, sao cho δ(q,a)=p Giáo trình Kiến trúc máy tính và Hệ 35 điều hành
  36. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Otomat hữu hạn đơn định 1.3. Biểu diễn các hàm chuyển trạng thái ❖ Dùng bảng: Ví dụ: có hàm chuyển của một Otomat như sau: δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 δ a b c 1 2 Giáo trình2 Kiến trúc máy tính và Hệ 2 2 36 điều hành
  37. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Otomat hữu hạn đơn định 1.3. Biểu diễn các hàm chuyển trạng thái ❖ Biểu đồ dịch chuyển: - Mỗi trạng thái q Q được đặt trong các vòng tròn. - Trạng thái bắt đầu q0 có thêm dấu ‘>’ ở đầu. - Trạng thái kết thúc q F được đặt trong vòng tròn kép. - Các cungGiáo nối trình Kiếntừ trúctrạng máy tính thái và Hệ q sang trạng thái p có 37 mang các nhãnđiều a hànhΣ, có nghĩa δ(q,a)=p
  38. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômat hữu hạn đơn định 1.3. Biểu diễn các hàm chuyển trạng thái ❖ Biểu đồ dịch chuyển: Ví dụ: có hàm chuyển của một Otomat như sau: δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 b a c 1 2 Giáo trình Kiến trúc máy tính và Hệ 38 điều hành
  39. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.4. Hàm chuyển trạng thái mở rộng - Ở trạng thái q1đọc xong xâu x=a1a2a3 ai-1=yai-1 chuyển sang trạng thái qi - Có (q1,a1)=q2; (q2,a2)=q3; , (qi-1,ai-1)=qi : ta * có thể biểu diễn như sau:  (q1,x)=qi * * -  (q1,x)= ( (q1,y),ai-1)=qi: hàm chuyển trạng thái mở rộng. Giáo trình Kiến trúc máy tính và Hệ 39 điều hành
  40. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.4. Hàm chuyển trạng thái mở rộng Cho δ: δ(0,0)=0, δ(0,1)=1, δ(1,1)=1 và δ(1,0)=0 Xác định *(0,01101)=? (0,0) = 0 *(0,01) = ((0,0),1) = 1 *(0,011) = (*(0,01),1) = 1 *(0,0110) = (*(0,011),0) = 0 Giáo trình Kiến trúc máy tính và Hệ 40 *(0,01101) = điều( hành*(0,0110),1) = 1
  41. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.5. Hoạt động đoán nhận xâu - Từ trạng thái bắt đầu, đọc từng ký hiệu vào từ trái sang phải. Mỗi lần đọc thì xác định lại trạng thái qua hàm chuyển trạng thái. - Nếu đọc xong xâu vào mà rơi vào trạng thái kết thúc thì xâu vào được đoán nhận ngược lại xâu vào không được đoán nhận - Nếu không thể đọc xong xâu vào thì xâu vào Giáo trình Kiến trúc máy tính và Hệ 41 không được đoánđiều hành nhận.
  42. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.5. Hoạt động đoán nhận xâu - Xâu x được đoán nhận bởi ôtômat DFA *  (q0,x)=p F - Cho DFA M({a,b},{0,1,2,3,4},,0,{4}), δ: δ(0,a)=1, δ(1,b)=2, δ(2,a)=3, δ(2,b)=4 δ(3,a)=3, δ(3,b)=4, δ(4,b)=4 xâu x=abaabbb có được đoán nhận k0? Giáo trình Kiến trúc máy tính và Hệ 42 điều hành
  43. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.5. Hoạt động đoán nhận xâu a b (0,a) = 1 0 1 2 *(0,ab) = ((0,a),b) = 2 a b a *(0,aba) = (*(0,ab),a) = 3 3 *(0,abaa) = (*(0,aba),a) = 3 b *(0,abaab) = (*(0,abaa),b) = 4 b 4 *(0,abaabb) = (*(0,abaab),b) = 4 * *  (0,abaabbb)Giáo trình Kiến=  trúc( máy(0,abaabb),b) tính và Hệ = 4 F, xâu x 43 được đoán nhậnđiều hành
  44. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.5. Hoạt động đoán nhận xâu a b Ta có thể viết lại như sau: 0 1 2 0abaabbb 1baabbb a b a 2aabbb 3 3abbb b 3bbb b 4 4bb Giáo trình4b Kiến trúc máy tính và Hệ 44 điều hành 4 F, xâu x được đoán nhận
  45. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định 1.6. Ngôn ngữ được đoán nhận bởi DFA - Cho DFA M(Σ, Q, δ, q0, F), ngôn ngữ L được đoán nhận bởi M được xác định như sau: * * L(M)={x  |  (q0,x)=p F} - Ví dụ: vẽ ôtômat đoán nhận ngôn ngữ L gồm các xâu là số nhị phân có độ dài >=2 0|1 0|1 0|1 Giáo0 trình Kiến trúc máy1 tính và Hệ 2 45 điều hành
  46. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định ❖ Trạng thái không chấp nhận được - Trạng thái không có mũi tên đi vào chỉ có mũ tên đi ra (trừ trạng thái bắt đầu). - Trạng thái chỉ có mũi tên đi vào không có mũi tên đi ra (trừ trạng thái kết thúc q q Giáo trình Kiến trúc máy tính và Hệ 46 điều hành
  47. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định ❖ Bài tập: (1)Cho M, xâu x: kiểm tra xâu x có được đoán nhận hay không? x: aabbca, abbbca, abbaca, aaaca a b a b c a 0 1 2 3 4 Giáo trình Kiến trúc máy tính và Hệ c 47 điều hành
  48. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định ❖ Bài tập: (2)Xây dựng DFA đoán nhận ngôn ngữ L(M) sau: - L(M)={abcnbm với n>=0, m>0} - L(M)={0(10)n với n>0} - L(M)={0n1m với n>=0, m>0} - L(M)={0n1m với n>0, m>0} Giáo trình Kiến trúc máy tính và Hệ 48 điều hành
  49. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 1. Ôtômát hữu hạn đơn định ❖ Bài tập: (3)Xây dựng ôtômat đoán nhận L(M) là: - Một số nhị phân chẵn có độ dài xâu lớn hơn 2. - Một số nguyên có dấu, không dấu. - Một số nguyên không dấu của NNLT C - Một số thực tĩnh có dấu, không dấu. Giáo trình Kiến trúc máy tính và Hệ 49 điều hành
  50. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 2. Ôtômat hữu hạn không đơn định (Nondeterministic finite automata –NFA) 2.1. Định nghĩa: M(Σ, Q, δ, q0, F) Σ: bộ chữ vào Q: tập hữu hạn các trạng thái q0 Q: trạng thái đầu F  Q: tập các trạng thái kết thúc δ: hàm chuyển trạng thái có dạng δ(q,a)=P Với q Q, a (Σ), PQ Giáo trình Kiến trúc máy tính và Hệ 50 điều hành
  51. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 2. Ôtômat hữu hạn không đơn định Ví dụ: Ôtômát đoán nhận các xâu có độ dài chẵn trên bộ chữ {0,1} 0|1 0|1 0 1 2  Giáo trình Kiến trúc máy tính và Hệ 51 điều hành
  52. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 2. Ôtômat hữu hạn không đơn định ❖ Sự khác nhau giữa DFA và NFA - NFA: δ(q,a)=P, với q Q, a (Σ), PQ DFA: δ(q,a)=p, với q,p Q, a Σ - NFA: có thể có dịch chuyển khi đọc  DFA: không thể dịch chuyển khi đọc  Giáo trình Kiến trúc máy tính và Hệ 52 điều hành
  53. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 2. Ôtômat hữu hạn không đơn định 2.2. Hàm dịch chuyển mở rộng - (q0,a1)={q1, q2} và (q1,a2)={q3,q4} (q2,a2)={q5,q6} * -  (q0,a1a2)= (q1,a2)(q2,a2)={q3,q4,q5,q6} * - Có  (q,x)={p1, p2, ,pk} thì k * *(q,xa)=  ( pi ,a) với x  , a  i=1 Giáo trình Kiến trúc máy tính và Hệ 53 điều hành
  54. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 2. Ôtômat hữu hạn không đơn định 2.2. Hàm dịch chuyển mở rộng - Cho NFA, *(0,01001)=? 0 1 (0,0)={1} 0 1 2 *(0,01)= (1,1)={1,2} 0|1 *(0,010)= (1,0)  (2,0) ={1} *(0,0100)= (1,0) ={1} Giáo trình Kiến trúc máy tính và Hệ *(0,01001)= (1,1) ={1,2} 54 điều hành
  55. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 2. Ôtômat hữu hạn không đơn định 2.3. Đoán nhận xâu x bởi NFA - Xâu x được đoán nhận bởi ôtômat *  (q0,x)F  - Theo ví dụ trước: *(0,01001)= {1,2} {1,2}F ={2} : xâu 01001 được đoán nhận Giáo trình Kiến trúc máy tính và Hệ 55 điều hành
  56. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 2. Ôtômat hữu hạn không đơn định 2.4. Ngôn ngữ được đoán nhận bởi NFA - Cho NFA M(Σ, Q, δ, q0, F), ngôn ngữ L được đoán nhận bởi M được xác định như sau: * * L(M)={x  |  (q0,x)  F } - Theo ví dụ trước các xâu bắt đầu bằng 0 và kết thúc bằng 1 được đoán nhận: 00111, 0100101, 0111, 010101, Giáo trình Kiến trúc máy tính và Hệ 56 điều hành
  57. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 3. Xây dựng DFA từ NFA - Cho NFA M(ΣN, QN, δN, q0, FN) thì DFA M(ΣN, QD, δD, q0, FD) - Xác định QD, δD, FD • Tạo tất cả các tập con T từ tập QN • Xác định D(T,a)=N(qi,a) với qi T, a  • Mỗi tập T tương ứng với 1 trạng thái của DFA • Loại bỏ các trạng thái không chấp nhận được Giáo trình Kiến trúc máy tính và Hệ • Trạng thái tương ứng với tập T có chứa trạng57 điều hành thái kết thúc sẽ là trạng thái kết thúc của DFA
  58. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 3. Xây dựng DFA từ NFA - Ví dụ: 0|1 0 1 0 1 2 0 1 0 1 →{0} {0,1} {0} →q0 q3 q0 {1} {2} q1 q2 *{2} *q2 {0,1} {0,1} {0,2} q3 q3 q4 *{0,2} {0,1} {0} * q4 q3 q0 *{1,2} Giáo trình Kiến trúc{2} máy tính và Hệ * q5 q2 58 *{1,2,0} {0,1} điều{0,2} hành * q6 q3 q4
  59. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 3. Xây dựng DFA từ NFA - Ví dụ: 1 0 0 1 0 1 →q0 q3 q0 q0 q3 q4 0 q1 q2 1 *q2 q1 q3 q3 q4 1 0 1 1 *q4 q3 q0 q2 q5 q6 *q5 q2 *q6 q3 q4 Giáo trình Kiến trúc máy tính và Hệ 59 điều hành
  60. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 3. Xây dựng DFA từ NFA - Các trạng thái q1, q2, q5, q6: không chấp nhận được - q4 tương ứng {0,2}: là trạng thái kết thúc 1 0 0 1 →q0 q3 q0 0 1 q0 q3 q4 q3 q3 q4 0 *q4 q3 q0 1 Giáo trình Kiến trúc máy tính và Hệ 60 điều hành
  61. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN 4. Ứng dụng - Đoán nhận từ khóa, số, , từ tố - DFA đoán nhận khóa float f l o a t 0 1 2 3 4 5 - NFA đoán nhận số nguyên có dấu 0| |9 +| - | 0| |9 Giáo trình Kiến0 trúc máy tính và Hệ1 2 61 điều hành
  62. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN ❖ Bài tập (1)Vẽ NFA đoán nhận - các số nhị phân có độ dài là bội số của 4. - các từ 110, 101. - Các từ 0(101)+1 (2)Chuyển NFA thành DFA - Các NFA ở câu (1) Giáo trình Kiến trúc máy tính và Hệ 62 điều hành
  63. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN ❖ Bài tập - NFA ở hình vẽ sau: 0|1 0|1 0 0|1 0 0 1 2 3 - NFA có hàm chuyển sau:  a b c d →0 {1,2} {1} {2} 1 {0} {2} {0,1} Giáo trình Kiến trúc máy tính và Hệ 63 *2 điều hành
  64. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. ÔTÔMÁT HỮU HẠN ❖ Bài tập - NFA có hàm chuyển sau:  0 1 →0 {1,3} {1} *1 {2} {1,2} 2 {3} {0} *3 {0} Giáo trình Kiến trúc máy tính và Hệ 64 điều hành
  65. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY ❖ Biểu thức chính quy ❖ Ngôn ngữ chính quy ❖ Văn phạm chính qui Giáo trình Kiến trúc máy tính và Hệ 65 điều hành
  66. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.1. Định nghĩa: Cho bộ chữ , biểu thức chính quy (BTCQ) trên  được định nghĩa đệ qui như sau: -  là BTCQ -  là BTCQ - a , a là BTCQ - Với r, s là BTCQ thì (r+s), rs, r*, s* là BTCQ Giáo trình Kiến trúc máy tính và Hệ 66 Có thể viết (r+s)điều hànhhay (r  s)
  67. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.1. Định nghĩa: Ví dụ: Cho ={0,1} ta có: - , , 0, 1 là BTCQ - (0+1), 01, 0*, 1*, (0+1)01, (0+1)0*, (01)*, ((0+1)01)* là BTCQ Giáo trình Kiến trúc máy tính và Hệ 67 điều hành
  68. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.1. Định nghĩa: ➢ Ví dụ: - (a+b+c) là BTCQ chỉ định 3 xâu a, b, c trên bộ chữ {a, b, c} - (a+b)* là BTCQ chỉ định mọi xâu trên {a, b} - aa*bb* hay a+b+ là BTCQ chỉ định các xâu bắt đầu bằng một số ký hiệu a, tiếp theo là một số Giáo trình Kiến trúc máy tính và Hệ ký hiệu b trong đó ký hiệu a và b xuất hiện68 ít nhất 1 lần điều hành
  69. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.1. Định nghĩa: ➢ Ví dụ: - (b+)(a+ab)* là BTCQ chỉ định các xâu trên {a, b} không chứa bb - (0+1)*1 là BTCQ chỉ định các xâu là số nhị phân lẻ Giáo trình Kiến trúc máy tính và Hệ 69 điều hành
  70. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.2. Thứ tự ưu tiên của các phép toán - Phép bao đóng (*) - Phép ghép tiếp (.) - Phép hợp (+) ➢ Ví dụ: 10*+0 : (1(0)*)+0 Giáo trình Kiến trúc máy tính và Hệ 70 điều hành
  71. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.3. Tính chất đại số - Tính giao hoán: r + s = s + r - Tính kết hợp: (r + s) + t = r + (s + t) r(st)=(rs)t Giáo trình Kiến trúc máy tính và Hệ 71 điều hành
  72. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.3. Tính chất đại số - Tính chất phân bổ r (s + t) = rs + rt (r + s)t = rt + st - Một số tính chất khác (r*)* = r* r = r = r *=  r + r = r r* = r+ +  Giáo trình Kiến trúc máy tính và Hệ 72 điều hành r+ = rr* = r*r (r*s*)* =(r + s)*
  73. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.4. Ngôn ngữ được chỉ định bởi BTCQ Ngôn ngữ L(r) được chỉ định bởi BTCQ r bất kỳ là được xây dựng dựa trên quy tắc - L( ) = {} - L(a) = {a} - L(r+s)=L(r)L(s) - L(rs) = L(r)L(s) Giáo trình Kiến trúc máy tính và Hệ 73 - L(r*) = (L(r))*điều hành
  74. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy 1.4. Ngôn ngữ được chỉ định bởi BTCQ ➢ Ví dụ: xây dựng BTCQ chỉ định ngôn ngữ L có ít nhất một ký hiệu a và 1 ký hiệu b trên {a, b} - L(r) = L(r1)  L(r2)=L(r1+r2) - L(r1): các xâu r1 có dạng w1aw2bw3 - L(r2): các xâu r2 có dạng w1bw2aw3 - BTCQ chỉ định L: Giáo trình Kiến trúc máy tính và Hệ 74 (a+b)*a(a+b)*b(a+b)*điều hành + (a+b)*b(a+b)*a(a+b)*
  75. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy ❖ Bài tập (1)Xây dựng BTCQ chỉ định các ngôn ngữ sau: - Tập hợp các xâu trên {a,b} có độ dài chia hết cho 3 - Tập hợp các xâu trên {a, b, c} chỉ chứa 1 ký hiệu a, còn lại là các ký hiệu b và c - Tập hợp các số nhị phân có tận cùng là 11 Giáo trình Kiến trúc máy tính và Hệ 75 - Tập hợp các sốđiều nguyên hành k0 dấu chia hết cho 5
  76. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 1. Biểu Thức chính quy ❖ Bài tập (2)Mô tả ngôn ngữ được chỉ định bởi BTCQ sau: - (a+b+c+d)*(a+d) - 1(0+1)(0+1)(0+1) - ((0+1)(0+1))+ - a(a+b)*a Giáo trình Kiến trúc máy tính và Hệ - (ab)* + (ba)* 76 điều hành
  77. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy 2.1. Khái niệm - Ngôn ngữ chính quy là ngôn ngữ được biểu diễn bởi biểu thức chính qui. - Ngôn ngữ chính qui được đoán nhận bởi ôtômát hữu hạn. - Ngôn ngữ được sản sinh từ văn phạm chính quy là ngôn ngữ chính qui Giáo trình Kiến trúc máy tính và Hệ 77 điều hành
  78. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy 2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ - BTCQ là a a - BTCQ là   Giáo trình Kiến trúc máy tính và Hệ 78 điều hành
  79. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy 2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ - BTCQ là rs  r s Giáo trình Kiến trúc máy tính và Hệ 79 điều hành
  80. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy 2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ - BTCQ là (r+s)  r    s Giáo trình Kiến trúc máy tính và Hệ 80 điều hành
  81. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy 2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ - BTCQ là r*    r  Giáo trình Kiến trúc máy tính và Hệ 81 điều hành
  82. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy 2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ - Ví dụ: xây dựng NFA đoán nhận (0+1)(01)* 0     1 Giáo trình Kiến trúc máy tính và Hệ 82 điều hành
  83. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy 2.2. Ôtômat đoán nhận ngôn ngữ được biểu diễn bởi BTCQ - Ví dụ: (0+1)(01)*   0 1   Giáo trình Kiến trúc máy tính và Hệ 83 điều hành
  84. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy  0    0 1   1   0|1 0 1 0 1 2 3 Giáo trình Kiến trúc máy tính và Hệ 84 điều hành 
  85. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy 2.3. Tính chất đóng của ngôn ngữ chính quy Cho L1(r) và L2(s) là ngôn ngữ chính quy thì: - L1(r)  L2(s): ngôn ngữ chính quy - L1(r)  L2(s): ngôn ngữ chính quy - L1(r).L2(s): ngôn ngữ chính quy - (L1(r))*: ngôn ngữ chính quy Giáo trình Kiến trúc máy tính và Hệ 85 điều hành
  86. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy ❖ Bài tập (1)Vẽ NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ sau: - (01)*(0+10*) - (10+(0+01)1*0) - (0+1)*(11+00)(0+1)* Giáo trình Kiến trúc máy tính và Hệ 86 điều hành
  87. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 2. Ngôn ngữ chính quy ❖ Bài tập (2)Vẽ DFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ sau: - 1*01+ - 10*11* - (a+b)c*ab* Giáo trình Kiến trúc máy tính và Hệ 87 điều hành
  88. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.1. Định nghĩa văn phạm tuyến tính trái - Một văn phạm G=(Σ, Δ, s, p) được gọi là văn phạm tuyến tính trái nếu tất cả các sản xuất có dạng A→Bw hay A→B với A,B Δ; w Σ* - Ví dụ: S→S a | S b | a Giáo trình Kiến trúc máy tính và Hệ 88 điều hành
  89. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.2. Định nghĩa văn phạm tuyến tính phải - Một văn phạm G=(Σ, Δ, s, p) được gọi là văn phạm tuyến tính phải nếu tất cả các sản xuất có dạng A→wB hay A→B với A,B Δ; w Σ* - Ví dụ: S→a A A→a A | b A |  Giáo trình Kiến trúc máy tính và Hệ 89 điều hành
  90. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.3. Định nghĩa văn phạm chính quy - Văn phạm tuyến tính trái, văn phạm tuyến tính phải là văn phạm chính quy. Giáo trình Kiến trúc máy tính và Hệ 90 điều hành
  91. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.4. Xây dựng NFA từ văn phạm tuyến tính phải Cho văn phạm chính qui G=(ΣG , Δ, s, p) xây dựng NFA M=(Q, Σ, q0, , F) đoán nhận ngôn ngữ được sinh ra từ G - Σ = ΣG - Với A Δ thì A Q Giáo trình Kiến trúc máy tính và Hệ - q0 = S 91 điều hành
  92. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.4. Xây dựng NFA từ văn phạm tuyến tính phải - Nếu A→a1a2 ai thì *(A,a1a2 ai)=qi : thêm qi vào Q và F - Nếu A→a1a2 ai thì đặt vào  các dịch chuyển trạng thái và thêm vào Q các trạng thái mới sao cho *(A,a1a2 ai)=qi a1 a2 ai GiáoA trình Kiến trúc máy tính và Hệ q92i điều hành
  93. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.4. Xây dựng NFA từ văn phạm tuyến tính phải - Nếu A→a1a2 aiB thì đặt vào  các dịch chuyển trạng thái và thêm vào Q các trạng thái mới sao cho *(A,a1a2 ai)=B a1 a2 ai A B Giáo trình Kiến trúc máy tính và Hệ - Nếu A→ thì thêm A vào F 93 điều hành
  94. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.4. Xây dựng NFA từ văn phạm tuyến tính phải - Ví dụ: S→a A A→a A | b A |  a |b a S A Giáo trình Kiến trúc máy tính và Hệ 94 điều hành
  95. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.4. Xây dựng văn phạm chính quy từ NFA Cho NFA M=(Q, Σ, q0, , F) xây dựng văn phạm chính qui G=(ΣG , Δ, s, p) - ΣG = Σ - Δ=Q - S=q0 - q→ap nếu (q,a)=p Giáo trình Kiến trúc máy tính và Hệ 95 - q→ nếu q Fđiều hành
  96. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy 3.4. Xây dựng văn phạm chính quy từ NFA Ví dụ: a |b - ΣG = {a,b} a S A - Δ={S, A} - S=S - S→aA vì (S,a)=A ; A→aA vì (A,a)=A Giáo trình Kiến trúc máy tính và Hệ - A→bA vì (A,b)=A; A→ vì A F 96 điều hành
  97. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy ❖ Bài tập (1)Vẽ otomat NFA từ G sau: - S→0S| 1S | 1 - S→ + A |- A A→0 A| 1A| | 9A |0| |9 - S→abA A→bB| B Giáo trình Kiến trúc máy tính và Hệ 97 điều hành B→c
  98. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 3. Văn phạm chính quy ❖ Bài tập (2)Xây dựng G từ NFA sau: 0|1 0|1 0 0|1 0 A B C D Giáo trình Kiến trúc máy tính và Hệ 98 điều hành
  99. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương - Với w * có *(p,w)=ql {p, q} là cặp và * (q,w)=qt trạng thái mà qt, ql cùng kết thúc tương đương. hoặc cùng không kết thúc - {q,p} và {p,k} các cặp trạng thái tương đương thì cặp {q,k} cũng tương đương (t/c bắt cầu) Giáo trình Kiến trúc máy tính và Hệ - Hai trạng thái không tương đương được gọi99 là hai trạng thái phânđiều hành biệt.
  100. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương - Xây dựng bảng đánh dấu cặp trạng thái phân biệt (1)Nếu p là trạng thái không kết thúc và q là trạng thái kết thúc thì {p,q} là trạng thái phân biệt. (2)Với a  có (p,a)=ql và (q,a)=qt mà {qt, ql} là cặp trạng thái phân biệt thì {p, q} cặp trạng thái phân biệt. Giáo trình Kiến trúc máy tính và Hệ 100 điều hành
  101. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương ➢ Ví dụ: xây dựng bảng đánh dấu cặp trạng thái phân biệt cho otomat sau 0 B E 0,1 0 1 0,1 0,1 A D G 1 0 0 1 C F Giáo trình Kiến trúc máy tính và Hệ 101 điều hành 1
  102. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương - Ta có B, D, E, G: trạng thái kết thúc A,C,F: trạng thái không kết thúc Áp dụng (qt1) nên các cặp sau là phân biệt: {A,B}, {A,D}, {A,E}, {A,G}, {C,B}, {C,D}, {C,E}, {C,G}, Giáo trình Kiến trúc máy tính và Hệ {F,B}, {F,D}, {F,E}, {F,G} 102 điều hành
  103. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương - Đánh dấu x vào các ô là cặp trạng thái phân biệt B X C X D X X E X X F X X X G X X X Giáo trình Kiến trúc máy tính và Hệ 103 A điềuB hành C D E F
  104. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương - Áp dụng (qt2) đối với từng cặp trạng thái phân biệt • {A,B}, {A,D}, {A,E}, {A,G}: vì A là trạng thái bắt đầu nên không có qt2. • {C,B}: được tạo ra từ cùng trạng thái A nên k0 có (qt2) Giáo trình Kiến trúc máy tính và Hệ • {C,D}: (A,1)=C và (B,1)=D nên {A,B}104 phân biệt (đã đánh dấuđiều hành rồi)
  105. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương • {C,E}: k0 có a thỏa (qt2) • {C,G}: (A,1)=C và (E,1)=G nên {A,E} phân biệt (đã đánh dấu rồi) • {F,B}: k0 có a thỏa (qt2) • {F,D}: (C,1)=F và (B,1)=D nên {C,B} phân biệt (đã đánh dấu rồi) Giáo trình Kiến trúc máy tính và Hệ 105 • {F,E}: k0 có ađiều thỏa hành (qt2)
  106. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương • {F,G}: (E,1)=G và (C,1)=F nên {C,E} phân biệt (đã đánh dấu rồi) (G,1)=G và (C,1)=F nên {G,C} phân biệt (đã đánh dấu rồi) (F,1)=F và (G,1)=G nên {F,G} phân biệt (đã đánh dấu rồi) Giáo trình Kiến trúc máy tính và Hệ 106 Ta k0 tìm thêmđiều được hành cặp trạng thái phân biệt nào
  107. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương - Ta được bảng đánh dấu trạng thái phân biệt sau B X C X D X X E X X F X X X G X X X Giáo trìnhA Kiến trúc Bmáy tính vàC Hệ D E F 107 điều hành
  108. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.1. Trạng thái tương đương - Ta được các cặp trạng thái tương đương sau: {A,C}, {A,F}, {B,D}, {B,E}, {B,G}, {C,F}, {D,E}, {D,G}, {E,G} Giáo trình Kiến trúc máy tính và Hệ 108 điều hành
  109. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.2. Hai otomat tương đương - Hai otomat cùng đoán nhận một ngôn ngữ thì tương đương. - Hai DFA tương đương thì cặp trạng thái đầu tương đương. - Cực tiểu hóa DFA: tìm DFA tương đương có số trạng thái ít nhất. Giáo trình Kiến trúc máy tính và Hệ 109 điều hành
  110. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.3. Thuật toán - Loại bỏ các trạng thái không chấp nhận được - Xác định tất cả các cặp trạng thái tương đương - Chia các trạng thái thành các nhóm, sao cho: • các trạng thái trong cùng một nhóm tương đương nhau • Không có cặp trạng thái nào ở 2 nhóm khác Giáo trình Kiến trúc máy tính và Hệ 110 nhau là tương điềuđương. hành
  111. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.3. Thuật toán - min(S,a)=T khi q S thì (q,a)=p T - Trạng thái đầu Mmin là trạng thái có chứa trạng thái đầu của M - Trạng thái kết thúc Mmin là những trạng thái có chứa trạng thái kết thúc của M Giáo trình Kiến trúc máy tính và Hệ 111 điều hành
  112. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA 4.3. Thuật toán ➢ Ví dụ: Cực tiểu hóa DFA ở ví dụ trước - Ta có các cặp trạng thái tương đương sau: {A,C}, {A,F}, {B,D}, {B,E}, {B,G}, {C,F}, {D,E}, {D,G}, {E,G} - Tạo thành các nhóm trạng thái tương đương: {A,C,F}, {B,D,E,G} 1 0|1 Giáo trình Kiến trúc máy tính và Hệ 0 112 điều hành ACF BDEG
  113. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA ❖ Bài tập: Cực tiểu các DFA sau: (1)  0 1 →A B F B G C *C A C D C G E H F F C G G G E Giáo trình Kiến trúc máy tính và Hệ H G C 113 điều hành
  114. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY 4. Cực tiểu hóa DFA ❖ Bài tập: Cực tiểu các DFA sau: (2)  0 1 →A B E B D C *C C C D E C *E D C Giáo trình Kiến trúc máy tính và Hệ 114 điều hành
  115. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH ❖ Văn phạm phi ngữ cảnh ❖ Sự nhập nhằng trong văn phạm phi ngữ cảnh ❖ Ngôn ngữ phi ngữ cảnh ❖ Dạng chuẩn của văn phạm phi ngữ cảnh Giáo trình Kiến trúc máy tính và Hệ 115 điều hành
  116. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 1. Văn phạm phi ngữ cảnh ➢ Định nghĩa: G=(Σ, Δ, s, p) trong đó: Σ: tập hữu hạn các ký hiệu kết thúc. Δ: tập hữu hạn các ký hiệu chưa kết thúc. s: ký hiệu bắt đầu; s Δ p: tập hữu hạn các sản xuất có dạng A→ với A Δ và (ΣΔ)* Giáo trình Kiến trúc máy tính và Hệ 116 điều hành
  117. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 1. Văn phạm phi ngữ cảnh ➢ Ví dụ: S→S(S)S |  Giáo trình Kiến trúc máy tính và Hệ 117 điều hành
  118. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 1. Văn phạm phi ngữ cảnh ➢ Suy dẫn trái, suy dẫn phải - Nếu luôn luôn thay thế ký hiệu chưa kết thúc ở bên trái nhất gọi là suy dẫn trái. - Tương tự ta có suy dẫn phải - Ví dụ: viết suy dẫn trái, suy dẫn phải tạo ra xâu a+a*a của văn phạm sau: E→E+E |E*E| (E) |a Giáo trình Kiến trúc máy tính và Hệ 118 điều hành
  119. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 1. Văn phạm phi ngữ cảnh ➢ Cây suy dẫn: cây thoả mãn các điều kiện: - Mỗi nút có 1 nhãn: ký hiệu kết thúc hoặc chưa kết thúc - Nhãn của nút gốc: ký hiệu bắt đầu - Nhãn của nút lá: ký hiệu kết thúc - Nếu một nút có nhãn A có các nút con của nó từ trái sang phải có nhãn x1, x2, x3, xn thì Giáo trình Kiến trúc máy tính và Hệ A→x1x2x3 xn p 119 điều hành
  120. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 1. Văn phạm phi ngữ cảnh ➢ Cây suy dẫn - Suy dẫn trái tạo ra cây suy dẫn trái. - Suy dẫn phải tạo ra cây suy dẫn phải - Ví dụ: vẽ cây suy dẫn trái, cây suy dẫn phải tạo ra xâu a+a*a của văn phạm sau: E→E+E |E*E| (E) |a Giáo trình Kiến trúc máy tính và Hệ 120 điều hành
  121. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 2. Sự nhập nhằng trong văn phạm phi ngữ cảnh ➢ Khái niệm văn phạm nhập nhằng - Cho văn phạm phi ngữ cảnh G. Nếu x L(G) được sinh ra từ 2 cây suy dẫn khác nhau thì G được gọi là văn phạm nhập nhằng - Ví dụ: E→E+E | E*E | (E) | a Giáo trình Kiến trúc máy tính và Hệ 121 điều hành
  122. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 2. Sự nhập nhằng trong văn phạm phi ngữ cảnh ➢ Khử sự nhập nhằng - Đưa vào văn phạm luật ưu tiên - Đặt thừa số chung Giáo trình Kiến trúc máy tính và Hệ 122 điều hành
  123. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 2. Sự nhập nhằng trong văn phạm phi ngữ cảnh ➢ Khử sự nhập nhằng - Ví dụ: S→aS | aSbS |  Giáo trình Kiến trúc máy tính và Hệ 123 điều hành
  124. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 3. Ngôn ngữ phi ngữ cảnh - Tập hợp các xâu được sinh ra từ văn phạm phi ngữ cảnh là ngôn ngữ phi ngữ cảnh Giáo trình Kiến trúc máy tính và Hệ 124 điều hành
  125. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khái niệm Văn phạm phi ngữ cảnh k0 chứa: • Ký hiệu thừa • Sản xuất  • Sản xuất đơn vị Được gọi là văn phạm phi ngữ cảnh ở dạng chuẩn Giáo trình Kiến trúc máy tính và Hệ 125 điều hành
  126. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Xác định và khử ký hiệu thừa - Ký hiệu thừa có 2 loại: • Ký hiệu vô sinh • Ký hiệu k0 đạt đến được - Ký hiệu A được gọi là ký hiệu vô sinh khi A * - Ký hiệu A được gọi là ký hiệu k0 đạt đến Giáo trình Kiến trúc máy tính và Hệ + 126 được khi S điều A hành
  127. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Xác định và khử ký hiệu thừa - Ví dụ: xác định ký hiệu thừa của VP sau: (1)S→0S | 1S | A|  A→0A (2)S→0S | 1S |  A→0A | 1 Giáo trình Kiến trúc máy tính và Hệ 127 điều hành
  128. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Xác định và khử ký hiệu thừa - Xác định ký hiệu k0 vô sinh: •  k0 vô sinh • a  k0 vô sinh • Với A→ mà mọi ký hiệu thuộc k0 vô sinh thì A k0 vô sinh. - Ký hiệu k0 phải là ký hiệu k0 vô sinh thì là ký Giáo trình Kiến trúc máy tính và Hệ 128 hiệu vô sinh điều hành
  129. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Xác định và khử ký hiệu thừa - Xác định ký hiệu đạt đến được: • S là ký hiệu đạt đến được • Với A→ mà A là ký hiệu đạt đến được thì mọi ký hiệu thuộc là ký hiệu đạt đến được. - Ký hiệu k0 phải là ký hiệu đạt đến thì là ký Giáo trình Kiến trúc máy tính và Hệ hiệu k0 đạt đến được 129 điều hành
  130. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Xác định và khử ký hiệu thừa - Khử ký hiệu thừa: • Loại bỏ tất cả các ký hiệu vô sinh và các sản xuất chứa nó. • Loại bỏ tất cả các ký hiệu k0 đạt đến được và các sản xuất chứa nó. Giáo trình Kiến trúc máy tính và Hệ 130 điều hành
  131. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Xác định và khử ký hiệu thừa - Ví dụ: Khử ký hiệu thừa của các văn phạm: (1)S→0S | 1S | A|  A→0A (2)S→0S | 1S |  A→0A | 1 Giáo trình Kiến trúc máy tính và Hệ 131 điều hành
  132. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất  - A là biến triệt tiêu khi A + - Xác định biến triệt tiêu: • A→  thì A: biến triệt tiêu • A→C1C2 Cn nếu C1, C2, ,Cn là biến triệt tiêu thì A là biến triệt tiêu Giáo trình Kiến trúc máy tính và Hệ 132 điều hành
  133. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất  - Cho G(, , S, p), khử sản xuất  ta được G’(, , S, p’) với p’ xác định như sau: Với mỗi A→B1B2 Bn p ta thêm các A→x1x2 xn vào p’ trong đó mỗi xi thay thế Bi thỏa mãn: • Nếu Bi là biến k0 triệt tiêu được thì xi=Bi • Nếu Bi là biến triệt tiêu thì xi= và xi=Bi Giáo trình Kiến trúc máy tính và Hệ 133 điều hành • Không cho tất cả các xi=
  134. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất  - Ví dụ: khử sản xuất  của văn phạm : S→AB A→aAB |  B→bAB |  Giáo trình Kiến trúc máy tính và Hệ 134 điều hành
  135. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất  - Ta có S, A, B: là biến triệt tiêu - Xét S→AB có A là biến triệt tiêu nên thay A bằng  và A B là biến triệt tiêu nên thay B bằng  và B ta được: S→AB | B | A Giáo trình Kiến trúc máy tính và Hệ 135 điều hành
  136. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất  - Xét A→aAB ta được: A→aAB | aB | aA | a - Xét B→bAB ta được: B→bAB| bB | bA | b Vậy ta được văn phạm sau: S→AB | B | A A→aAB | aB | aA | a Giáo trình Kiến trúc máy tính và Hệ B→bAB| bB | bA | b 136 điều hành
  137. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất  ❖ Bài tập: khử sản xuất  của các văn phạm sau: (1)S→0S |1S |  (2)S→S(S)S |  (3)S→a S b | b S a |  Giáo trình Kiến trúc máy tính và Hệ 137 điều hành
  138. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Sản xuất đơn vị - Sản xuất có dạng A→B được gọi là sản xuất đơn vị; với A,B - Cặp (A,B) cặp biến của sản xuất đơn vị Giáo trình Kiến trúc máy tính và Hệ 138 điều hành
  139. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất đơn vị Cho G(, , S, p), khử sản xuất đơn vị ta được G’(, , S, p’) với p’ xác định như sau: - Thêm các sản xuất không đơn vị vào p’ - Xác định các cặp biến (A,B) mà A +B (chỉ sử dụng các sản xuất đơn vị) - Với mỗi cặp biến (A,B) xác định ở trên, thêm Giáo trình Kiến trúc máy tính và Hệ vào p’ các sản xuất A→ ; với B→ là sản139 xuất không đơn vị trongđiều hành G
  140. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất đơn vị - Ví dụ: Khử sản xuất đơn vị cho văn phạm sau: S→aA |A | bB A→B | a B→A | ab | bb Giáo trình Kiến trúc máy tính và Hệ 140 điều hành
  141. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất đơn vị - Ta có các sản xuất không đơn vị: S→aA| bB A→a B→ab |bb - Ta có các cặp biến (S,A), (S,B), (A,B), (B,A) thỏa mãn S +A; S +B; A +B; B +A Giáo trình Kiến trúc máy tính và Hệ 141 • cặp (S,A),điều có hành A→a nên thêm: S→a
  142. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất đơn vị • cặp (S,B), có B→ab và B→bb nên thêm: S→ab |bb • cặp (A,B), có B→ab và B→bb nên thêm: A→ab |bb • cặp (B,A), có A→a nên thêm: B→a Giáo trình Kiến trúc máy tính và Hệ 142 điều hành
  143. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất đơn vị Vậy ta được văn phạm sau: S→aA | a | ab |bb |bB A→a | ab | bb B→ab |bb | a Giáo trình Kiến trúc máy tính và Hệ 143 điều hành
  144. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH 4. Dạng chuẩn của văn phạm phi ngữ cảnh ➢ Khử sản xuất đơn vị ❖ Bài tập: khử sản xuất đơn vị cho văn phạm sau: (1)S→0A | 1 A | A A→S | 0 | 1 (2)E→E+T | T T→T*F | F Giáo trình Kiến trúc máy tính và Hệ F→(E) | a 144 điều hành
  145. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG ❖ Ôtômat đẩy xuống (PDA) ❖ Ngôn ngữ được đoán nhận PDA ❖ Sự tương đương giữa PDA và văn phạm phi ngữ cảnh ❖ Ôtômat đẩy xuống đơn định Giáo trình Kiến trúc máy tính và Hệ 145 điều hành
  146. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống (Push Down Automat - PDA) 1.1. Mô tả 0 1 0 1 1 Băng vào Đầu đọc q Bộ điều khiển Giáo trình Kiến trúc máy tính và Hệ 146 Ngănđiều xếp hành
  147. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.1. Mô tả Tại một thời điểm bộ điểu khiển: • Trạng thái q • Đọc một ký hiệu trên băng vào (: k0 đọc) • Nhìn ký hiệu ở đỉnh ngăn xếp xác định trạng thái tiếp theo và quyết định hành động liên quan đến ngăn xếp Giáo trình Kiến trúc máy tính và Hệ 147 điều hành
  148. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.1. Mô tả Có 2 cách để ôtômát đẩy xuống đoán nhận xâu vào: • Đọc xong xâu vào và ôtômat ở trạng thái kết thúc • Đọc xong xâu vào và ngăn xếp rỗng Giáo trình Kiến trúc máy tính và Hệ 148 điều hành
  149. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.2. Định nghĩa: M(Σ, Q, , z, δ, q0, F) Σ: bộ chữ vào Q: tập hữu hạn các trạng thái q0 Q: trạng thái đầu F  Q: tập các trạng thái kết thúc  : tập ký hiệu trên ngăn xếp z  : ký hiệu đầu tiên ở đỉnh ngăn xếp Giáo trình Kiến trúc máy tính và Hệ δ: hàm chuyển trạng thái dạng δ(q,a,x)={(p, 149)} Với q,p Q, a Σđiều{ hành}, x , *
  150. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.2. Định nghĩa: M(Σ, Q, , z, δ, q0, F) δ: hàm chuyển trạng thái dạng δ(q,a,x)={(p, )} Với q,p Q, a Σ{}, x , * X: ký hiệu ở đỉnh ngăn xếp : chuỗi ký hiệu thay thế x ở đỉnh ngăn xếp = : ký hiệu x trên đỉnh ngăn xếp được lấy ra =x: ngăn xếp không thay đổi. =yz: lấy x ra, đẩy z vào, đẩy y vào. Giáo trình Kiến trúc máy tính và Hệ 150 điều hành
  151. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.2. Định nghĩa Ví dụ: Otomát đẩy xuống đoán nhận các xâu anbn với n>=0: M(Σ, Q, , z, δ, q0, F) Σ: {a,b} Q: {q0, q1, q2, q3} q0: trạng thái đầu {q3}: tập các trạng thái kết thúc {1,z} : tập ký hiệu trên ngăn xếp Giáo trình Kiến trúc máy tính và Hệ 151 điều hành z : ký hiệu đầu tiên ở đỉnh ngăn xếp
  152. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.2. Định nghĩa δ(q0,a,z)={(q1,1z )} δ(q0,,z)={(q3, )} δ(q1,a,1)={(q1,11)} δ(q1,b,1)={(q2,)} δ(q2,b,1)={(q2, )} δ(q2,,z)={(q3, )} Giáo trình Kiến trúc máy tính và Hệ 152 điều hành
  153. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.3. Biểu diễn PDA bằng biểu đồ dịch chuyển - Các trạng thái được đặt trong các vòng tròn - Trạng thái đầu có dấu “>” gắn phía trước - Trạng thái kết thúc đặt trong vòng tròn kép - δ(q,a,x)=(p, ): từ trạng thái q sang trạng thái p có nhãn a, x| - Ký hiệu đầu đỉnh ngăn xếp qui ước là z Giáo trình Kiến trúc máy tính và Hệ 153 điều hành
  154. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.3. Biểu diễn PDA bằng biểu đồ dịch chuyển - Ví dụ: vẽ ôtômat PDA đoán nhận xâu anbn với n>=0 a,1|11 b,1| a,z|1z b,1| ,z| q0 q1 q2 q3 Giáo trình Kiến trúc máy ,z|tính và Hệ 154 điều hành
  155. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.4. Cấu hình của PDA Cấu hình của PDA là bộ (q,w, ): - q: trạng thái - w: phần xâu vào sẽ đọc - : nội dung của ngăn xếp (đỉnh-đáy: trái-phải) Giáo trình Kiến trúc máy tính và Hệ 155 điều hành
  156. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 1. Ôtômat đẩy xuống 1.4. Cấu hình của PDA Ví dụ: Cấu hình của PDA ở ví dụ trước đoán nhận xâu: aaabbb - (q0,aaabbb,z) |- (q1,aabbb,1z) |- (q1,abbb,11z) |- (q1,bbb,111z) |- (q2,bb,11z) |- (q2,b,1z) |- (q2,,z) |- (q3,,) - Có nghĩa (q0,aaabbb,z) |-* (q3,,) : xâu vào được đoán nhận Giáo trình Kiến trúc máy tính và Hệ 156 điều hành
  157. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.1. Đoán nhận bởi trạng thái kết thúc - Ngôn ngữ L được PDA M đoán nhận bởi trạng thái kết thúc là: L(M)={w | (q0,w,z ) |-* (qf ,, )} với qf F, * Giáo trình Kiến trúc máy tính và Hệ 157 điều hành
  158. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.2. Đoán nhận bởi ngăn xếp rỗng - Ngôn ngữ L được PDA M đoán nhận bởi ngăn xếp rỗng : L(M)={w | (q0,w,z ) |-* (qk ,,)} với qk Q Giáo trình Kiến trúc máy tính và Hệ 158 điều hành
  159. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA ❖ Bài tập: vẽ PDA đoán nhận xâu x là: (1) anbmcm với n,m>=0 (2) anbmcn với n,m>0 (3) Các cặp dấu () tương thích (4) Số nhị phân có số chữ số 0 bằng số chữ số 1 (5) biểu thức số học ở dạng hậu tố có 1 số hạng a Giáo trình Kiến trúc máy tính và Hệ (6)Số nhị phân có số chữ số 0 gấp đôi số chữ159 số 1 và xâu khác  điều hành
  160. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.3. Chuyển PDA từ đoán nhận bởi ngăn xếp rỗng sang đoán nhận bởi trạng thái kết thúc Cho PDA M(Σ, Q, , z, δ, q0) đoán nhận bởi ngăn xếp rỗng thành M’(Σ, Q’, ’, z’, δ’, q0’, F) đoán nhận bởi trạng thái kết thúc có: - Q’=Q{q0’,qf} - F={qf} Giáo trình Kiến trúc máy tính và Hệ - ’= {z’} 160 điều hành
  161. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.3. Chuyển PDA từ đoán nhận bởi ngăn xếp rỗng sang đoán nhận bởi trạng thái kết thúc - δ’ được xác định: ,z’|  ,z’|  ,z’|zz’ M ,z’|  q q0’ q0 f Giáo trình Kiến trúc máy tính và Hệ 161 điều hành
  162. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.3. Chuyển PDA từ đoán nhận bởi ngăn xếp rỗng sang đoán nhận bởi trạng thái kết thúc Ví dụ: a,z|1z a,1|11 b,1| ,z| q0 q1 Giáo trình Kiến trúc máy tính và Hệ 162 điều hành
  163. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.3. Chuyển PDA từ đoán nhận bởi ngăn xếp rỗng sang đoán nhận bởi trạng thái kết thúc a,z|1z Ví dụ: a,1|11 b,1| a,z|1z a,1|11 ,z| q0 q1 b,1| ,z’|zz’ ,z| ,z’| q0’ q0 q1 qf Giáo trình Kiến trúc máy tính và Hệ 163 điều hành
  164. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.3. Chuyển PDA từ đoán nhận bởi ngăn xếp rỗng sang đoán nhận bởi trạng thái kết thúc Ví dụ: a,z|1z a,1|11 b,1| ,z| q0 q1 Giáo trình Kiến trúc máy tính và Hệ 164 điều hành
  165. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.3. Chuyển PDA từ đoán nhận bởi ngăn xếp rỗng sang đoán nhận bởi trạng thái kết thúc Ví dụ: (ab)n với n>0 a,z|zz a,z|zz b,z| ,z| q0 q1 q1 q3 Giáo trình Kiến trúc máy tính và Hệ 165 điều hành
  166. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.4. Chuyển PDA từ đoán nhận bởi trạng thái cuối sang đoán nhận bởi ngăn xếp rỗng Cho PDA M(Σ, Q, , z, δ, q0, F) đoán nhận bởi ngăn xếp rỗng thành M’(Σ,Q’,’, z’, δ’,q0’) đoán nhận bởi trạng thái kết thúc có: - Q’=Q{q0’,qk} - ’= {z’} Giáo trình Kiến trúc máy tính và Hệ 166 điều hành
  167. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.4. Chuyển PDA từ đoán nhận bởi trạng thái cuối sang đoán nhận bởi ngăn xếp rỗng - δ’ được xác định: , ’|  ,z’|zz’ M , ’|  q q0’ q0 k , ’|  Giáo trình Kiến trúc máy tính và Hệ 167 điều hành
  168. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.4. Chuyển PDA từ đoán nhận bởi trạng thái cuối sang đoán nhận bởi ngăn xếp rỗng Ví dụ: anbm với n,m>=0 a,z|1z a,1|11 b,1|11 b,z|1z b,1|11 q0 q1 ,z|z Giáo trình Kiến trúc máy tính và Hệ 168 điều hành
  169. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 2. Ngôn ngữ được đoán nhận bởi PDA 2.4. Chuyển PDA từ đoán nhận bởi trạng thái cuối sang đoán nhận bởi ngăn xếp rỗng Ví dụ: anbn với n>=0 a,z|1z ,z| a,1|11 b,1|11 ,1| b,z|1z ,z| b,1|11 ,1| q0 q1 qf ,z|z Giáo trình Kiến trúc máy tính và Hệ 169 điều hành
  170. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 3. Ôtômat đẩy xuống đơn định - Ôtômát đẩy xuống thỏa mãn: (1) (q,a,X) chỉ chứa một giá trị duy nhất (2)(q,a,X) không rỗng thì (q,,X) phải rỗng Giáo trình Kiến trúc máy tính và Hệ 170 điều hành
  171. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 4. Sự tương đương giữa PDA và văn phạm phi ngữ cảnh 4.1. Chuyển văn phạm phi ngữ cảnh thành PDA - Bộ chữ (bảng chữ) là tập hợp hữu hạn các ký hiệu Ví dụ:{0,1} bộ chữ gồm 2 ký hiệu 0 và 1 {a,b,c, ,z} bộ chữ gồm các ký hiệu a →z Tập các chữ cái tiếng việt Giáo trình Kiến trúc máy tính và Hệ 171 điều hành
  172. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG 4. Sự tương đương giữa PDA và văn phạm phi ngữ cảnh 4.2. Chuyển PDA thành văn phạm phi ngữ cảnh - Bộ chữ (bảng chữ) là tập hợp hữu hạn các ký hiệu Ví dụ:{0,1} bộ chữ gồm 2 ký hiệu 0 và 1 {a,b,c, ,z} bộ chữ gồm các ký hiệu a →z Tập các chữ cái tiếng việt Giáo trình Kiến trúc máy tính và Hệ 172 điều hành
  173. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 6. MÁY TURING 1. Một số vấn đề về ngôn ngữ 1.1. Xâu - Bộ chữ (bảng chữ) là tập hợp hữu hạn các ký hiệu Ví dụ:{0,1} bộ chữ gồm 2 ký hiệu 0 và 1 {a,b,c, ,z} bộ chữ gồm các ký hiệu a →z Tập các chữ cái tiếng việt Giáo trình Kiến trúc máy tính và Hệ 173 điều hành
  174. TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 6. MÁY TURING 1. Một số vấn đề về ngôn ngữ 1.1. Xâu - Bộ chữ (bảng chữ) là tập hợp hữu hạn các ký hiệu Ví dụ:{0,1} bộ chữ gồm 2 ký hiệu 0 và 1 {a,b,c, ,z} bộ chữ gồm các ký hiệu a →z Tập các chữ cái tiếng việt Giáo trình Kiến trúc máy tính và Hệ 174 điều hành