Bài giảng Lý thuyết automat và ứng dụng: Chương 1, 2, 3, 4 - TS. Vũ Đức Lung

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

178
lượt xem 15
download

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

Bài giảng Lý thuyết automat và ứng dụng - Chương 1, 2, 3, 4 trình bày những kiến thức về: Bổ túc toán, ngôn ngữ và biểu diễn ngôn ngữ, automat hữu hạn và biểu thức chính qui, văn phạm chính qui và các tính chất, văn phạm phi ngữ cảnh. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Lý thuyết automat và ứng dụng: Chương 1, 2, 3, 4 - TS. Vũ Đức Lung

26/09/2011 Chương 1 – Tổng quan Automat là gì? Automat theory is the study of abstract computing devices, or “machines” Lý thuyết automat và ứng dụng Lý thuyết automat là lý thuyết làm nền tảng cho việc hiểu các (AUTOMATA THEORY AND ITS APPLICATIONS) mô hình tự động mà điển hình nhất là các máy tính số ngày nay Sự liên quan giữa lý thuyết automat và ngôn ngữ hình thức Giảng viên: TS. Vũ Đức Lung Email: lungvd@uit.edu.vn Khoa KTMT Vũ Đức Lung 1 2 Tại sao học automat? Các ứng dụng chủ yếu Thăm dò ý kiến tại một số trường ĐH danh tiếng như Xây dựng ngôn ngữ lập trình và các trình dịch trường Stanford với những sinh viên sau tốt nghiệp 5 năm: – Bộ phân tích từ vựng và cú pháp trong các trình biên dịch Kiến thức môn học nào được sử dụng nhiều nhất trong – Xử lý chuỗi trong ngôn ngữ lập trình và ngôn ngữ tự nhiên công việc? – Dịch từ ngôn ngữ này sang ngôn ngữ khác: từ ngôn ngữ cấp cao sang cấp thấp, từ tiếng Anh qua tiếng Pháp,… Ngoài các môn cơ bản thì môn này được đánh giá cao trong các môn học tự chọn Thiết kế các hệ thống số – Mạch tuần tự – Mạch đếm – Máy trạng thái Phần mềm khai phá dữ liệu web, doc, chống đạo văn Các giao thức truyền thông, truyền tin mật 3 4 Các kiến thức yêu cầu Yêu cầu và tính điểm Đặt nền tảng trên lý thuyết tập hợp Bài tập kiểm tra trên lớp: 20% Lý thuyết đồ thị – Bài kiểm tra 1: 10% – Bài kiểm tra 2: 10% Kỹ thuật chứng minh qui nạp,chứng minh phản chứng Thi giữa kỳ: 20% Báo cáo seminar: 30% – Thành lập các nhóm 2-3 sinh viên – Buổi học 2-4 đăng ký đề tài – Báo cáo vào 2 tuần cuối của HK – Điểm: Báo cáo + trình bày Thi cuối kỳ: 30% 5 6 1
26/09/2011 Tài liệu tham khảo NỘI DUNG Hồ Văn Quân. Lý thuyết automat và ngôn ngữ hình thức. Bổ túc toán Đọc thêm: Ngôn ngữ và biểu diễn ngôn ngữ – Hopcroft, Motwani, Ullman. Automata Theory, Languages, and Automat hữu hạn và biểu thức chính qui Computation 2nd Edition. Văn phạm chính qui và các tính chất – Bakhadyr Khoussainov. Automata theory and its application. Free reading: http://books.google.com (Ai tìm được phiên bản đầy đủ share Văn phạm phi ngữ cảnh + bonus) Auomat đẩy xuống Tài liệu học tập: Máy turing – https://sites.google.com/site/vdlung/automat Ứng dụng thiết kế số 7 Khoa KTMT Vũ Đức Lung 8 Bổ túc toán Tập hợp (Set) Phần tử Nội dung: Ví dụ: • Tập hợp • D = {Mon, Tue, Wed, Thu, Fri, Sat, Sun} • Quan hệ • Tập các đối tượng rời rạc • Phép chứng minh quy nạp • Không trùng lắp • Đồ thị và cây Định nghĩa: • Tập hợp là tập các đối tượng không có sự lặp lại 9 10 Ký hiệu tập hợp Một số dạng tập hợp đặc biệt Tập rỗng: Liệt kê phần tử: • Ký hiệu: ∅ hoặc { } • D = {1, 2, 3} Tập hợp con: Đặc tả tính chất đặc trưng: • Ký hiệu: A ⊂ B (Ngược lại: A ⊄ B ) • D = { x | x là một ngày trong tuần } • { 1, 2, 4 } ⊂ { 1, 2, 3, 4, 5 } • { 2, 4, 6 } ⊄ { 1, 2, 3, 4, 5 } 11 12 2
26/09/2011 Một số dạng tập hợp đặc biệt Các phép toán trên tập hợp Tập hợp bằng nhau: Phần bù (complement): • Ký hiệu: A = B (Ngược lại: A ≠ B ) • A’ = { x | x ∉ A } • { 1, 2 } = { 2, 1 } nhưng { 1, 2, 3 } ≠ { 2, 1 } Phép hợp (Union): Tập lũy thừa: • A ∪ B = { x | x ∈ A hoặc x ∈ B } • Ký hiệu: 2A Phép giao (intersection): • A = { 1, 2, 3 } thì 2A= {∅∅, {1}, {2}, {3}, {1, 2}, • A ∩ B = { x | x ∈A và x ∈ B } {2, 3}, {3, 1}, {1, 2, 3} } 13 14 Các phép toán trên tập hợp Các phép toán trên tập hợp Phép trừ (difference): Ví dụ: cho A = {1, 2} và B = {2, 3} • A \ B = { x | x ∈ A nhưng x ∉ B } • A ∪ B = { 1, 2, 3 } Tích Đềcác: • A∩B = { 2 } • A x B = { (a,b) | a ∈ A và b ∈ B } • A\ B = {1 } • A x B = { (1,2 ), (1, 3), (2, 2), (2, 3) } • 2A = { ∅, {1}, {2}, {1, 2} } 15 16 Quan hệ Quan hệ Ví dụ: cho S = {0, 1, 2, 3} S • Quan hệ ‘thứ tự nhỏ hơn’ L = { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) } R ( A × B ) = aRb • Quan hệ ‘bằng’ miền xác định (domain) × miền giá trị (range) E = { (0, 0), (1, 1), (2, 2), (3, 3) } • Quan hệ ‘chẵn lẻ’ P = { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)} 17 18 3
26/09/2011 Các tính chất của quan hệ Quan hệ tương đương Phản xạ (reflexive): nếu aRa là đúng với Quan hệ tương đương = Quan hệ phản xạ, ∀a∈ ∈S đối xứng và bắc cầu Đối xứng (symmetric): nếu aRb thì bRa Ví dụ: • E và P là quan hệ tương đương Bắc cầu (transitive): nếu aRb và bRc thì aRc • L không là quan hệ tương đương Ví dụ:ở ví dụ trên • L không là quan hệ phản xạ trên S vì (0,0)∉L hay đối xứng trên S vì (0,1)∈L nhưng (1,0) ∉L • E và P mang tính phản xạ, đối xứng và bắc cầu 19 20 Lớp tương đương Bao đóng của quan hệ Nếu R là quan hệ tương đương trên S thì R P-closure = quan hệ nhỏ nhất thỏa các tính phân hoạch S thành các lớp tương đương chất trong P không rỗng và rời nhau: S = S1 ∪ S2 ∪ f Bao đóng bắc cầu R+: Tính chất: • Nếu (a,b) ∈ R thì (a,b) ∈R+ • Si ∩ Sj = ∅ • Nếu (a,b) ∈ R+ và (b,c) ∈ R thì (a,c) ∈ R+ • Nếu a, b cùng thuộc Si thì aRb đúng • Không còn gì thêm trong R+ • Nếu a ∈ Si và b ∈ Sj thì aRb sai Bao đóng phản xạ và bắc cầu R*: Ví dụ: P có 2 lớp tương đương {0, 2} và {1, 3} • R* = R+ ∪ { (a, a)  a ∈ S } 21 22 Bao đóng của quan hệ Nguyên lý quy nạp Ví dụ: R = { (1, 2), (2, 2), (2, 3) } trên S = {1, 2, 3} Bước 1 (cơ sở quy nạp): chứng minh P(0) • R+ = { (1, 2), (2, 2), (2, 3), (1, 3) } Bước 2 (giả thiết quy nạp): giả sử P(n-1) • R* = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) } Bước 3 (quy nạp): P(n - 1) ⇒ P(n), ∀ n ≥ 1. Ví dụ: chứng minh n n ( n + 1)(2n + 1) ∑i i =0 2 = 6 23 24 4
26/09/2011 Đồ thị có hướng (Directed graph) Cây (Trees) Đồ thị G = (V, E) Cây: là đồ thị có hướng • V : tập các đỉnh (nút) • E : tập các cung có hướng v w • 1 nút gốc Ví dụ: đồ thị G = (V, E) • Nút trung gian (nút trong) • V = { 1, 2, 3, 4 } • Nút lá: không dẫn ra nút con • E={i→ji
26/09/2011 Nội dung: Chương 02 – Ngôn ngữ và biểu • Khái niệm ngôn ngữ diễn ngôn ngữ • Cách biểu diễn ngôn ngữ • Văn phạm • Sự phân lớp văn phạm Giảng viên: TS. Vũ Đức Lung Email: lungvd@uit.edu.vn Khoa KTMT Vũ Đức Lung 1 2 Ký hiệu, bộ chữ cái, chuỗi Chuỗi Ký hiệu (symbol): là một thực thể trừu tượng mà ta Độ dài chuỗi: là số các ký hiệu tạo thành chuỗi không định nghĩa được một cách hình thức • |abca| = 4 • Các chữ cái a, b, c : hoặc các số 1, 2, 3 : Chuỗi rỗng: ký hiệu ε, là chuỗi không có ký hiệu nào Bộ chữ cái (alphabet): Σ • |ε| = 0 • Là một tập (không rỗng) các ký hiệu nào đó Chuỗi con: chuỗi v là chuỗi con của w nếu v được tạo bởi các ký hiệu liền kề nhau trong chuỗi w. • Bộ chữ cái Latin {A, B, C, :, a, b, c, :, z} • Chuỗi 10 là chuỗi con của chuỗi 010001 Chuỗi (string): một chuỗi (hay một từ - word) trên bộ Chuỗi tiền tố: là chuỗi con bất kỳ nằm ở đầu chuỗi chữ cái Σ Chuỗi hậu tố: là chuỗi con bất kỳ nằm ở cuối chuỗi • Là một dãy hữu hạn các ký hiệu của Σ • Chuỗi abc có các tiền tố a, ab, abc • Một ký hiệu có thể xuất hiện nhiều lần • Chuỗi 0246 có các hậu tố 6, 46, 246, 0246 3 4 Chuỗi Ngôn ngữ (Languages) Chuỗi nối kết (ghép): là chuỗi được tạo thành bằng Tổng quan về ngôn ngữ: cách viết chuỗi thứ nhất, sau đó viết chuỗi thứ hai, ... • Ngôn ngữ tự nhiên: tiếng Việt, tiếng Anh, : • Nối ghép của chuỗi Long và Int là LongInt • Ngôn ngữ lập trình: Pascal, C/C++, : • Nối kết của chuỗi rỗng: εw = wε = w (với mọi w) • Là tập hợp các câu theo cấu trúc quy định nào đó → ε là đơn vị của phép nối kết • Biểu thị các ý nghĩ, các sự kiện hay các khái niệm Chuỗi đảo ngược: của chuỗi w, ký hiệu wR, là chuỗi • Bao gồm một tập các ký hiệu và các quy tắc để w được viết theo thứ tự ngược lại. vận dụng chúng w = abcd → wR = dcba εR = ε 5 6 1
26/09/2011 Ngôn ngữ (Languages) Các phép toán trên ngôn ngữ Một ngôn ngữ (hình thức) L là một tập hợp các chuỗi Phép bao đóng (closure): thành lập một ngôn ngữ của các ký hiệu từ một bộ chữ cái Σ nào đó. bằng cách kết nối các chuỗi (với số lượng bất kỳ) các chuỗi của một ngôn ngữ L cho trước Σ* và Σ+ : i Bao đóng Kleene: L* = ∪ ∞ L ● Σ* : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng i = 0 L+ = ∪ L i ε, sinh ra từ bộ chữ cái Σ. Bao đóng dương (positive): ∞ ● Σ+ : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi i=1 rỗng ε, sinh ra từ bộ chữ cái Σ. Chú ý: L+ = L*L = LL* L* = L+ ∪ {ε} Σ* = Σ+ + {ε} Σ+ = Σ* - {ε} Ví dụ: cho L = {a, ba} • L2 = {aa, aba, baa, baba} ● Σ = {0,1} thì: • L3 = {aaa, aaba, abaa, ababa, baaa,baaba, babaa, bababa} 絃 Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, :} • L* = {ε, a, ba, aa, aba, baa, baba, aaa, aaba, :} + 絃 Σ = {0, 1, 00, 01, 10, 11, 000, :} 7 8 絃 Chuỗi 010210 ∉ Σ* vì có số 2 ∉ Σ Biểu diễn ngôn ngữ Định nghĩa văn phạm Liệt kê chuỗi: L = {aa, aba, baa, baba} Theo từ điển, văn phạm là một tập các quy tắc về cấu tạo từ và các quy tắc về cách thức liên kết từ lại thành Mô tả đặc điểm chủ yếu: L = {ai | i là số nguyên tố} câu Biểu diễn thông qua văn phạm và automata: Định nghĩa: văn phạm cấu trúc G là một hệ thống gồm 4 • Cho phép biểu diễn ngôn ngữ một cách tổng quát thành phần G(V, T, P, S) • Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn • V (variables): tập các biến (VD: A, B, C, :) ngữ • T (terminal): tập các ký hiệu kết thúc (V ∩ T = Ø) • Automata: cơ chế cho phép đoán nhận một chuỗi (VD: a, b, c, :, w, x, y, ...) bất kỳ có thuộc một ngôn ngữ L hay không • P (production): tập luật sinh, dạng α→β với α, β ∈ (V ∪ T)* • S (start): ký hiệu bắt đầu (S ⊂ V) 9 10 Định nghĩa văn phạm Phân cấp Chomsky trên văn phạm Dẫn xuất trực tiếp: nếu α→β là một luật sinh thì Bằng cách áp đặt một số quy tắc hạn chế trên các luật γ α δ ⇒ γ βδ sinh, Noam Chomsky đề nghị một hệ thống phân loại các văn phạm dựa vào tính chất của các luật sinh. Dẫn xuất gián tiếp: nếu các chuỗi α1, α2, ...., αm ∈ Σ* và α1 ⇒ α2, α2 ⇒ α3, ..., αm-1 ⇒ αm thì αm có thể được Loại 0 – Văn phạm không hạn chế (Unrestricted dẫn xuất từ α1 Grammar): không cần thỏa điều kiện ràng buộc nào trên tập các luật sinh α1 ⇒* αm Loại 1 – Văn phạm cảm ngữ cảnh (CSG – Context Ngôn ngữ L sinh bởi văn phạm G: Sensitive Grammar): nếu văn phạm G có các luật L (G) = {w | w ∈ T * và S ⇒* w} sinh dạng α→β và |β| ≥ |α| Loại 2 – Văn phạm phi ngữ cảnh (CFG – Context-Free Văn phạm tương đương: là 2 văn phạm sinh ra cùng Grammar): có luật sinh dạng A→α với A là một biến một ngôn ngữ (G1 tương đương G2 ⇔ L(G1)=L(G2) ) đơn và α là chuỗi các ký hiệu thuộc (V ∪ T)* 11 12 2
26/09/2011 Phân cấp Chomsky trên văn phạm CÂU HỎI VÀ BÀI TẬP CHƯƠNG 02 Loại 3 – Văn phạm chính quy (RG – Regular Grammar): có mọi luật sinh dạng tuyến tính phải hoặc tuyến tính trái. • Tuyến tính phải: A → wB hoặc A → w • Tuyến tính trái: A → Bw hoặc A → w Với A, B là các biến đơn, w là chuỗi ký hiệu kết thúc (có thể là rỗng) Nếu ký hiệu L0, L1, L2, L3 là các ngôn ngữ được sinh ra bởi văn phạm loại 0, 1, 2, 3, ta có: L3 ⊂ L2 ⊂ L1 ⊂ L0 13 Khoa KTMT Vũ Đức Lung 14 3
26/09/2011 Chương 3: Khái niệm Automat hữu hạn Automata hữu hạn & Biểu thức chính quy (Finite Automata) FA là tập các trạng thái hữu hạn với các qui tắc để chuyển Nội dung: đổi từ một trạng thái này sang trạng thái khác. • Khái niệm DFA & NFA Ứng dụng nguyên thủy của FA là mạch chuyển trạng thái tuần tự (mạch tuần tự), trong đó trạng thái là cài đặt một • Sự tương đương giữa DFA & NFA tập các bits trong các flip-flop. Ngày nay được ứng dụng rộng rãi. • Biểu thức chính quy Biểu diễn đơn giản nhất là “Đồ thị chuyển trạng thái” hay • Các tính chất của tập chính quy “sơ đồ dịch” 1 2 VD 1: Nhận biết chuỗi kết thúc “ing” Chuyển Automata thành Code Biểu diễn FA bằng sơ đồ dịch In C/C++, tạo đoạn code cho từng trạng thái. Code sẽ có dạng: Not i or g 1. Đọc ký tự nhập. 2. Tính toán để ra quyết định trạng thái kế. Not i 3. Nhảy đến đoạn code của trạng thái kế đó. Not i or n i 2: /* State “Saw i” */ nothing Saw i Saw in Saw ing c = getNextInput(); i n g if (c == ’n’) goto 3; Start else if (c == ’i’) goto 2; i else goto 1; 3: /* State ”Saw in” */ . . . 3 4 Biểu diễn FA bằng bảng truyền Phân loại FA Thí dụ: Cho NFA: Tập trạng thái S = {0, 1, 2, 3}; Σ = {a, b}; Trạng thái bắt đầu So = 0; Tập trạng thái kết thúc F = {3}. DFA Deterministic ∑ Finite Automata FA Bảng truyền (Finite Automata) NFA NFA nhận dạng (a|b)*abb Nondeterministic Finite Automata Biểu thức chính quy Khoa KTMT - UIT TS. Vũ Đức Lung 5 6 1
26/09/2011 Automata hữu hạn đơn định (DFA) Mở rộng hàm chuyển trạng thái Ví dụ 2: c 1. δ(q, ε) = q 1 Input 0 1 1 0 0 1 0 1 2. δ(q, wa) = δ( δ(q,w), a) với ∀ w, a Start q0 1 q1 0 0 Bộ điều khiển Ngôn ngữ được chấp nhận: a b L(M) = { x | δ( q0, x ) ∈ F } Trạng thái bắt đầu 0 0 1 q2 q3 Trạng thái kết thúc 1 Ngôn ngữ d x Ví dụ: chuỗi nhập w=110101 chính quy Phép chuyển trên nhãn x • δ(q0, 1) = q1 • δ(q0, 11) = δ(q1, 1) = q0 Q : tập hữu hạn các trạng thái (p, qD) • δ(q0, 110) = δ(q1, 10) = δ(q0, 0) = q2 Σ : bộ chữ cái nhập (a, b D ; w, x, y D) • δ(q0, 1101) = δ(q1, 101) = δ(q0, 01) = δ(q2, 1) = q3 M=(Q, Σ, δ, q0, F) • δ(q0, 11010) = D = δ(q3, 0) = q1 δ : hàm chuyển, ánh xạ: Q x Σ → Q • δ(q0, 110101) = D = δ(q1, 1) = q0 ∈ F q0 ∈ Q : trạng thái bắt đầu. F ⊆ Q : tập các trạng thái kết thúc. 7 8 Giải thuật hình thức Automata hữu hạn không đơn định (NFA) • Mục đích: kiểm tra một chuỗi nhập x có thuộc ngôn ngữ • Ví dụ: cho automata M (hình vẽ) và xét chuỗi nhập 01001 1 1 L(M) được chấp nhận bởi automata M. 0 0 • Input: chuỗi nhập x$ Start q0 0 q3 0 q4 • Output: câu trả lời ‘YES’ hoặc ‘NO’ • Giải thuật: 1 q1 q0 0 q0 1 q0 0 q0 0 q0 1 q0 q := q0 ; c := nextchar ; {c là ký hiệu nhập ñược ñọc tiếp theo} 1 0 1 0 0 1 While c $ do q3 q1 q3 q3 q1 begin q2 0 q := δ(q, c); 0 1 1 q4 q4 c := nextchar ; end Nhận xét: If (q in F) then write("YES") else write("NO"); • Ứng với một trạng thái và một ký tự nhập, có thể có không, một hoặc nhiều phép chuyển trạng thái. 9 10 • DFA là một trường hợp đặc biệt của NFA Định nghĩa NFA Ví dụ về NFA Q : tập hữu hạn các trạng thái. Ví dụ: xét chuỗi nhập w=01001 và NFA đã cho ở trên Σ : bộ chữ cái nhập. • M( {q0, q1, q2, q3, q4}, {0, 1}, δ, q0, {q2, q4} ) M=(Q, Σ, δ, q0, F) δ : hàm chuyển ánh xạ Q x Σ → 2Q q0 ∈ Q : trạng thái bắt đầu. • δ(q0, 0) = {q0,q3} δ Input F ⊆ Q : tập các trạng thái kết thúc. Trạng thái 0 1 • δ(q0, 01) = δ( δ(q0, 0), 1) Chú ý: khái niệm δ(q, a) là tập hợp tất cả các trạng thái p q0 {q0,q3} {q0,q1} = δ({q0, q3},1) = δ(q0, 1) sao cho có phép chuyển từ trạng thái q trên nhãn a. q1 Ø {q2} ∪ δ(q3, 1) = {q0, q1} q2 {q2} {q2} • δ(q0, 010) = {q0, q3} Hàm chuyển trạng thái mở rộng: q3 {q4} Ø • δ(q0, 0100) = {q0, q3, q4} • δ(q, ε) = {q} • δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà p∈δ(r, a) } q4 {q4} {q4} • δ(q0, 01001) = {q0, q1, q4} = δ( δ(q,w), a) Do q4 ∈ F nên w=01001 ∈ L(M) • δ(P, w) = ∪q∈P δ(q, w) với ∀P ⊆ Q 11 12 2
26/09/2011 NFA với ε- dịch chuyển (NFAεε) Sự tương đương giữa DFA & NFA Ví dụ: xây dựng NFA chấp nhận chuỗi 0*1*2* Định lý 1: Nếu L là tập được chấp nhận bởi một NFA thì tồn 0 1 2 tại một DFA chấp nhận L. Start 0, 1 1, 2 q0 q1 q2 Giả sử NFA M={Q, Σ, δ, q0, F} chấp nhận L 0, 1, 2 Ta xây dựng DFA M’={Q’, Σ, δ’, q0’, F’} chấp nhận L • Q’ = 2Q . Một phần tử trong Q’ được ký hiệu là [q0, q1, D, qi] với q0, q1, 0 1 2 D, qi ∈ Q • q0’ = [q0] Start ε ε q0 q1 q2 • F’ là tập hợp các trạng thái của Q’ có chứa ít nhất một trạng thái kết thúc trong tập F của M • Hàm chuyển δ’([q1, q2,..., qi], a) = [p1, p2,..., pj] nếu và chỉ nếu δ({q1, q2,..., qi }, a) = {p1, p2,..., pj} Định nghĩa: NFAεε M(Q, Σ, δ, q0, F) • δ : hàm chuyển ánh xạ Q x (Σ ∪ {εε}) → 2Q • Khái niệm δ(q, a) là tập hợp các trạng thái p sao cho có phép chuyển nhãn a từ q tới p, với a ∈ (Σ ∪ {ε}) 13 14 Chuyển NFA thành DFA Ví dụ về sự tương đương giữa DFA & NFA Ví dụ: NFA M ({q0, q1}, {0, 1}, δ, q0, {q1}) với hàm chuyển Xây dựng DFA tương đương cho NFA sau (NFA nhận dạng δ(q0,0) = {q0, q1}, δ(q0,1) = {q1}, δ(q1,0) = ∅, δ(q1,1) = {q0, q1} (a|b)*abb). Ta sẽ xây dựng DFA tương đương M’ (Q’, {0, 1}, δ’, [q0], F’) • Q’ = {∅∅ , [q0], [q1], [q0, q1]} • F’ = {[q1], [q0, q1]} • Hàm chuyển δ’ δ’(∅ ∅ , 0) = δ’(∅ ∅ , 1) = ∅ δ’([q0], 0) = [q0, q1] δ’([q0], 1) = [q1] δ’([q1], 0) = ∅ δ’([q1], 1) = [q0, q1] δ’([q0, q1], 0) = [q0, q1] δ’([q0, q1], 1) = [q0, q1] Xem VD 2.12, 2.13 trong [1] 15 16 Tìm các trạng thái cho DFA Xây dựng DFA từ NFA(εε) Các bước thực hiện: Tính ∈-closure(0)={0,1,2,4,7} = A //Những trạng thái trên NFA có • Bảng hàm chuyển từ “0” đi mà có sự truyền rỗng ∈ Tính ∈-closure(Move(A,a)) = ∈-closure(3,8) = {1,2,3,4,6,7,8}=B Ký hiệu nhập b Trạng thái Trong đó: Move(A,a) = (3,8) a b C • Tính ∈-closure(Move(A,b)) = ∈-closure(5) = {1,2,4,5,6,7}=C A B C b a b Lập lại các bước này cho tất cả các tập B,C,… cho đến khi không còn B B D Start a b tập nào C B C A B D E b a Kết quả: D B E a a A = {0,1,2,4,7} E B C B = {1,2,3,4,6,7,8} C = {1,2,4,5,6,7} • Ký hiệu bắt đầu: q0’ = A (↔ ε-CLOSURE(q0) ) D = {1,2,4,5,6,7,9} • Tập trạng thái kết thúc: F’ = {E} (vì trong E có chứa trạng E = {1,2,4,5,6,7,10} thái 10 ∈ F) 17 18 3
26/09/2011 Sự tương đương giữa NFAεε và NFA Sự tương đương giữa NFAεε và NFA 0 1 2 Định lý 2: nếu L được chấp nhận bởi một NFA có ε-dịch Ví dụ: Start q0 ε q1 ε q2 chuyển thì L cũng được chấp nhận bởi một NFA không có ε-dịch chuyển. Xây dựng NFA tương đương M’={Q, Σ, δ’, q0, F’} • Q = {q0, q1, q2} Giả sử: NFAεε M(Q, Σ, δ, q0, F) chấp nhận L • Σ = {0, 1, 2} Ta xây dựng: NFA M’={Q, Σ, δ’, q0, F’} • Trạng thái bắt đầu: q0 • F’ = {q0, q2} Với: • Hàm chuyển δ’ • F’ = F ∪ q0 nếu ε-CLOSURE(q0) chứa một trạng thái thuộc F. δ’ Inputs Ngược lại, F’ = F Trạng thái 0 1 2 • δ’(q, a) = δ*(q, a) 0 1 2 q0 {q0, q1, q2} {q1, q2} {q2} Start 0, 1 1, 2 q0 q1 q2 q1 ∅ {q1, q2} {q2} q2 ∅ ∅ {q2} 0, 1, 2 19 20 Biểu thức chính quy (RE) Biểu thức chính quy (RE) Vài ví dụ: Định nghĩa: cho Σ là một bộ chữ cái. BTCQ trên Σ là các tập • 00 : là biểu thức chính quy biểu diễn tập {00} • (0+1)* : tập hợp tất cả các chuỗi số 0 và số 1, kể cả chuỗi rỗng = {ε, 0, 1, hợp mà chúng mô tả được định nghĩa đệ quy như sau: 00, 01, 10, 11, 010, 011, 0010 ... } ● ∅ là BTCQ ký hiệu cho tập rỗng • (0+1)*011 : ký hiệu cho tất cả các chuỗi 0, 1 tận cùng bởi 011 = {011, ● ε là BTCQ ký hiệu cho tập {ε} 0011, 1011, 00011, 11011, ... } ● ∀ a ∈ Σ, a là BTCQ ký hiệu cho tập {a} • (0+1)*00(0+1)* : tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0 liên tiếp = ● Nếu r và s là các BTCQ ký hiệu cho các tập hợp R và S thì (r + s), (rs) {00, 000, 100, 0000, 0001, 1000, 1001, 011001, ... } và ( r*) là các BTCQ ký hiệu cho các tập hợp R ∪ S, RS và R* tương ứng • (0+ ε)(1+10)* : tất cả các chuỗi không có hai số 0 liên tiếp = {ε, 0, 01, 010, 1, 10, 01010, 0111, ... } Thứ tự ưu tiên: • 0*1*2* : {ε, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, ... } • 00*11*22* : tất cả các chuỗi trong tập 0*1*2* với ít nhất một ký hiệu 0, 1 Phép bao đóng > Phép nối kết > Phép hợp và 2 ↔ viết gọn thành 0+1+2+ Ví dụ: • Biểu thức ((0(1*)) + 1) có thể viết là 01*+1 21 22 Tính chất đại số của BTCQ Sự tương đương giữa NFAεε và BTCQ Phép hợp: Phép nối kết: Định lý 3: nếu r là BTCQ thì tồn tại một NFA với ε-dịch • r+∅=∅+r=r • rε = εr = r chuyển chấp nhận L(r) • r+r=r • r∅ = ∅r = ∅ Định lý 4: Nếu L được chấp nhận bởi một DFA, thì L được • r+s=s+r • (r + s) t = rt + st • (r + s) + t = r + (s + t) = r + s + t • r (s + t) = rs + rt ký hiệu bởi một BTCQ Phép bao đóng: Tổng hợp: Định lý 1 • ε* = ε • (r* + s*)* = (r*s*)* = (r + s)* DFA NFA • ∅* = ∅ • (rs)*r = r(sr)* • r*r* = r* • (r*s)* r* = (r + s)* • (r*)* = r* Định lý 4 Định lý 2 • r* = ε + r + r2 + D + rk + D • r* = ε + r+ RE NFAε • (ε + r)+ = (ε + r)* = r* Định lý 3 • r*r = r r* = r+ 23 24 4
26/09/2011 Từ biểu thức chính quy đến NFA Từ RE đến ε-NFA a Xây dựng NFA từ biểu thức chính quy Symbol a: Giải thuật : Xây dựng NFA từ biểu thức chính quy (Cấu trúcThompson’) ε: ε Nhập: Biểu thức chính quy r trên ∑. Xuất: NFA nhận dạng ngôn ngữ L(r). ∅: Khoa KTMT - UIT TS. Vũ Đức Lung 25 26 Từ RE đến ε-NFA Từ RE đến ε-NFA For E1 ε ε ε For E1 For E2 ε ε For E2 E1E2 E1 ∪E 2 27 28 Từ RE đến ε-NFA Phương pháp ε Quy tắc: ε ε For E ε E* 29 Khoa KTMT - UIT TS. Vũ Đức Lung 30 5
26/09/2011 Phương pháp Phương pháp Giả sử N(s) và N(t) là NFA cho biểu thức chính quy s và t. Với s|t xây dựng NFA hỗn hợp N(s|t) Khoa KTMT - UIT TS. Vũ Đức Lung 31 Khoa KTMT - UIT TS. Vũ Đức Lung 32 Phương pháp Automat hữu hạn Automat hữu hạn không tất định (NFA) – Cách vẽ NFA cơ bản Khoa KTMT - UIT TS. Vũ Đức Lung 33 Khoa KTMT - UIT TS. Vũ Đức Lung 34 Automat hữu hạn Ví dụ Automat hữu hạn không tất định (NFA) Dùng giải thuật để xây dựng NFA cho biểu thức chính quy Cách vẽ NFA cơ bản r = (a|b)*abb 35 36 6
26/09/2011 Mô phỏng NFA Giải thuật Nhập: NFA gọi là N, chuỗi nhập x. x được kết thúc bằng S= ∈-closure({So}) eof, N có trạng thái bắt đầu s0 và tập trạng thái kết thúc F. a = nextchar Xuất: Giải thuật trả lời đúng nếu N chấp nhận x, ngược lại While a eof then trả lời sai. Begin S = ∈-closure(move(s,a)) a = nextchar End if S ∩ F φ then write(đúng) Else write(sai) 37 38 Xây dựng DFA trực tiếp từ biểu thức chính Trạng thái quan trọng của NFA quy Tìm hiểu 2 giải thuật để tối ưu việc so trùng mẫu được xây dựng Trạng thái quan trọng là từ nó có sự truyền khác rỗng. Như từ biểu thức chính quy: vậy nếu hai tập trạng thái có cùng số trạng thái quan trọng thì chúng được đồng nhất. Xây dựng DFA trực tiếp từ biểu thức chính quy. NFA được xây dựng theo cấu trúc Thompson có trạng thái Tối thiểu trạng thái của DFA. kết thúc không có sự truyền ra, như vậy nó không phải là trạng thái quan trọng ( nhưng thực sự nó lại rất quan trọng). Để tránh tình trạng này người ta thêm ký hiệu # vào sau biểu thức chính quy, và trạng thái kết thúc có sự truyền trên ký hiệu #. Khi xây dựng tập con hoàn tất thì trạng thái nào có sự truyền trên # là trạng thái chấp nhận. 39 40 Xây dựng DFA trực tiếp từ biểu thức chính Biểu thức chính quy gia tố quy Biểu thức r# được gọi là biểu thức chính quy gia tố. Ký hiệu Xây dựng DFA trực tiếp từ biểu thức chính quy: # không thuộc tập các ký hiệu cơ bản của biểu thức chính Vẽ cây phân tích quy r. Tính các giá trị Nullable, First Post (FP), Last Post (LP). Biểu diễn biểu thức chính qui gia tố bằng cây phân tích, sao Lập bảng Follow Post (FLP) cho tên các lá là các ký hiệu cơ bản. Các nút trung gian là Tìm tập các trạng thái, bảng truyền các toán tử dạng: cat, or hoặc star. Vẽ DFA Tối thiểu trạng thái của DFA. 41 42 7
26/09/2011 Cây phân tích Cây phân tích Cách vẽ cây phân tích r = (a|ba)(a|b)*ba# Là cây có nút lá là các ký hiệu cơ bản của r#. Các nút là các toán tử. Các toán tử trên cây phân tích như: Toán tử kết nối Toán tử tuyển. Toán tử bao đóng truyền. 43 Khoa KTMT - UIT 44 Các quy tắc để tính ba hàm nullable, Cây phân tích firstpos, lastpos Cây phân tích r = (a|ba)(a|b)*ba# 45 46 Các quy tắc để tính ba hàm nullable, NULLABLE firstpos, lastpos NULLABLE: Quy tắc: r = (a|ba)(a|b)*ba# - Nốt lá là False (F) - Nốt (*) là True (T) - Nốt (|) là True (T) nếu 1 trong 2 nốt con là True (T) - Nốt (.) là True (T) nếu cả 2 nốt con đều True (T) FIRST POST (FP), LAST POST (LP): Quy tắc: - Bắt đầu đánh số cho các nốt lá theo thứ tự từ 1 lớn dần (tự đánh) - FP và LP của nốt lá bằng chính số của nó - Nốt (|): FP của nó bằng tổng hợp FP của 2 nốt con. LP cũng thế - Nốt (*): FP = FP nốt con. LP cũng thế - Nốt (.): o FP: Nếu (Nullable nốt con bên trái) = F thì (FP của nó) = (FP nốt con bên trái). Nếu (Nullable nốt con bên trái) = T thì (FP của nó) = tổng hợp (FP cả 2 nốt con) o LP: Nếu (Nullable nốt con bên phải) = F thì (LP của nó) = (LP nốt con bên phải). Nếu (Nullable nốt con bên phải) = T thì (LP của nó) = tổng hợp (LP cả 2 nốt con) 47 48 8
26/09/2011 FIRST POST (FP), LAST POST (LP) Các quy tắc tính hàm followpos(n) Quy tắc: - Lập bảng FLP bằng cách liệt kê các nốt lá theo hàng dọc (Số thứ tự đã đánh trước) - Chỉ xét các nốt (.) và (*), không xét nốt (|) - Cách xét: o Đối với (.): Đưa (tập FP nốt con bên phải) vào (từng giá trị LP của nốt con trái) trong bảng FLP o Đối với (*): Đưa (tập FP của chính nó) vào (từng giá trị LP của chính nó) trong bản FLP - Cứ xét hết các nốt cần xét và điền giá trị vào các dòng tương ứng trong bảng FLP 49 50 Bảng FLP Tìm tập các trạng thái Đặt [A] là trạng thái bắt đầu. [A] sẽ chứa FP của ROOT => [A] = {1,2} Xét [A] = {1,2}: Ở đây ta nhìn hình chỉ số các nốt lá và bảng FLP o 1 tương đương a => Ua =FLP(1) = {4,5,6} (Ra 1 tập khác ta đặt là {B}) o 2 tương đương b => Ub =FLP(2) = {3} (đặt là [C]) Xét {B} = {4,5,6}: o 4 tương đương a => Ua =FLP(4) = {4,5,6} (là {B}) o 5,6 tương đương b => Ub =FLP(5) U FLP(6) = {4,5,6,7} (đặt là [D]) 51 52 Bảng truyền VẼ DFA VẼ DFA theo các trạng thái ta có được (A, B, C, D, E): - A là trạng thái bắt đầu - Trạng thái nào chứa 8 sẽ là trạng thái kết thúc - Đường đi dựa vào dữ liệu ta đã xét trên kia cho từng trạng thái (đọc a, đọc b) 53 54 9
26/09/2011 Xây dựng DFA trực tiếp từ biểu thức chính Tối thiểu số trạng thái của DFA quy Khái niệm DFA đầy đủ, trạng thái chết d Xây dựng DFA trực tiếp từ biểu thức chính quy: Chuỗi w phân biệt trạng thái s với trạng thái t Vẽ cây phân tích Giải thuật 3.6: Tối thiểu trạng thái của DFA Tính các giá trị Nullable, First Post (FP), Last Post (LP). Nhập: DFA, gọi là M có S, Σ , s0, F. M là DFA đầy đủ. Lập bảng Follow Post (FLP) Xuất: DFA, gọi là M’ chấp nhận ngôn ngữ như M, với số trạng thái nhỏ nhất. Tìm tập các trạng thái, bảng truyền Phương pháp: Vẽ DFA 1. Tạo phần khởi đầu Π có 2 nhóm: các trạng thái kết thúc F, và các trạng thái không kết thúc S –F. Tối thiểu trạng thái của DFA. 2. Áp dụng thủ tục (mô phỏng 3.6) để tạo ∏ new 3. Nếu ∏ new = ∏ thì ∏ final = ∏ tiếp tục bước 4, ngược lại lặp lại bước 2, với ∏ = ∏ new 4. Chọn mỗi nhóm 1 trạng thái đại diện và đó là trạng thái của M’. 5. Nếu M’ có trạng thái chết d thì loại nó ra khỏi M’. Tất cả các sự truyền đến trạng thái d đều không xác định. 55 56 Tối thiểu số trạng thái của DFA Ví dụ đơn giản DFA Mô phỏng 3.6: Giải thuật tạo ∏ new for với mỗi nhóm G của ∏ do begin - Chia G thành các nhóm nhỏ hơn sao cho hai trạng thái s và t của G sẽ ở cùng một nhóm nhỏ hơn nếu và chỉ nếu các sự truyền trên tất cả các ký hiệu nhập a từ s và t đều đi đến các trạng thái kế tiếp ở trong cùng một nhóm của ∏ - Ta thay G bằng các nhóm nhỏ hơn vừa được tạo nên, cho chúng vào ∏ new end 57 58 Tối thiểu số trạng thái của DFA CÂU HỎI VÀ BÀI TẬP CHƯƠNG 03 Π={(E),(ABCD)} Xét (ABCD) trên sự truyền a – A → B : thuộc (ABCD) – B→B: – C→B: – D → E : không thuộc (ABCD) ⇒ tách D riêng Tương tự trên b Πnew = {(E), (ABC), (D)} Thông thường những trạng thái rút gọn được là có sự truyền đến cùng một trạng thái trên một ký hiệu nhập và đến chính mình trên ký hiệu nhập khác. Khoa KTMT - UIT TS. Vũ Đức Lung 59 Khoa KTMT Vũ Đức Lung 60 10
26/09/2011 Chương 04: NHẬN XÉT Văn phạm phi ngữ cảnh CFG là những ký hiệu cho việc mô tả ngôn ngữ (Context Free Grammar) CFG mạnh hơn FA hay RE, nhưng vẫn không thể mô tả mọi ngôn ngữ Nội dung: Thường được dùng để mô tả những cấu trúc lồng vào nhau • Văn phạm phi ngữ cảnh (CFG) Ý tưởng cơ bản là dùng những biến thay thế cho tập các chuỗi( • Giản lược văn phạm phi ngữ cảnh hay ngôn ngữ) Các biến này được định nghĩa hồi qui với các biến khác và các • Chuẩn hóa văn phạm phi ngữ cảnh định nghĩa này gọi là các qui tắc sinh, hay luật sinh • Các tính chất của văn phạm phi ngữ cảnh 1 2 Ví dụ: CFG for { 0n1n | n > 1} Văn phạm phi ngữ cảnh Định nghĩa: là hệ thống gồm 4 thành phần G(V, T, P, S) Luật sinh (Productions) có dạng: • V (Variables = nonterminals) : tập hữu hạn các biến (ký tự chưa kết S -> 01 thúc) S -> 0S1 • T (Terminals) : tập hữu hạn các ký tự kết thúc (V ∩ T = Ø) Chuỗi 01 là một ngôn ngữ • P (Productions) : tập hữu hạn các luật sinh dạng A → α (α∈ α∈ (V∪T)*) Phương pháp quy nạp (Induction): Nếu w thuộc ngôn ngữ thì • S (Start symbol) : ký hiệu bắt đầu của văn phạm 0w1 cũng thuộc ngôn ngữ. Quy ước: • V: chữ in hoa (A, B, C, ..); T: chữ in thường (a, b, c, .., w, x, y..) • α, β, γ, .. biểu diễn chuỗi ký hiệu kết thúc và biến 3 4 Ví dụ số nguyên không dấu Ví dụ: Formal CFG (Unsigned Integers) A formal CFG for { 0n1n | n > 1}. – Terminals = {0, 1}. – Variables = {S}. – Start symbol = S. – Productions = S -> 01 • Ký hiệu bắt đầu S -> 0S1 • Ký hiệu không kết thúc , • G=({S, A, B}, {a, b}, P, S) với P gồm các luật sinh: • Ký hiệu kết thúc 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 S → AB • Luật A → aA S → AB → A→a hay A → aAa → B → bB B → bBb B→b 5 6 1
26/09/2011 BNF (Backus- (Backus-Naur Form) Ví vụ một biểu thức Start symbol 1959, John Backus giới thiệu ALGOL 58 thuộc nhóm ACM-GAMM Non-terminals , , , , , 1960 Peter Naur cho ra phiên bản mới ALGOL 60 BNF là một ký hiệu tự nhiên mô tả cú pháp, là một siêu Terminals 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, / ngôn ngữ mô tả ngôn ngữ khác Các Grammar cho ngôn ngữ lập trình thường được viết Productions: dưới dạng BNF → | → | VD: ::= | → | () → + | − → ∗ | / 7 8 BNF mở rộng (Extended BNF) BNF vs EBNF Không làm tăng khả năng đặc tả của BNF, chỉ là cách biểu BNF: diễn gọn hơn -> + 1. Phần lựa chọn được đặt vào trong dấu [] | - -> if () [else )] | -> * 2. Đặt những phần tương tự trong RHS vào trong () và ngăn | / cách bởi | | -> (+ | -) const 3. Đặt những phần lập lại trong {} EBNF: -> letter {letter | digit} -> {(+ | -) } -> {(* | /) } 9 10 Sơ đồ cú pháp Dẫn xuất và ngôn ngữ (Syntax Diagrams) (Derivation and Language) Sơ đồ cú pháp của biểu thức Dẫn xuất: exp • Nếu A → β là luật sinh trong văn phạm G và α, γ là 2 chuỗi bất term kỳ, thì khi áp dụng luật sinh A → β vào chuỗi αAγγ ta sẽ thu được chuỗi αβγ : αAγ ⇒G αββγ • Giả sử: α1 ⇒G α2, α2 ⇒G α3, ..., αm-1 ⇒G αm, ta có: α1 ⇒* ⇒ G αm exp term_op term • Ta có: α ⇒* ⇒ G α với mọi chuỗi α • Thông thường, ta sẽ dùng ⇒ và ⇒* thay cho ⇒G và ⇒*G Ngôn ngữ sinh bởi CFG: cho CFG G(V, T, P, S) w ∈ T* và S ⇒*G w } L(G) = { w (chuỗi w gồm toàn ký hiệu kết thúc và được dẫn ra từ S) 11 12 2