Bài giảng Toán giải tích - Chương 6: Automata đẩy xuống

Bài giảng "Toán giải tích - Chương 6: Automata đẩy xuống" cung cấp cho người đọc các kiến thức: Khái niệm về PDA, PDA đơn định và không đơn định, PDA chấp nhận chuỗi bằng Stack rỗng và PDA chấp nhận chuỗi bằng trạng thái kết thúc, sự tương đương giữa PDA và CFL. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán giải tích - Chương 6: Automata đẩy xuốngChương 6: Automata đẩy xuống (Push Down Automata) Nội dung: • Khái niệm về PDA • PDA đơn định và không đơn định • PDA chấp nhận chuỗi bằng Stack rỗng và PDA chấp nhận chuỗi bằng trạng thái kết thúc • Sự tương đương giữa PDA và CFL 1 PDATa đã biết: • Lớp ngôn ngữ chính quy được sinh ra từ văn phạm chính quy và được đoán nhận bởi automata hữu hạn • Lớp ngôn ngữ phi ngữ cảnh được sinh ra từ văn phạm phi ngữ cảnh → câu hỏi: CFL có thể được đoán nhận bởi một automata không? automata đó như thế nào?Mô tả: gồm các thành phần của một automata hữu hạn với sự bổ sung thêm một ngăn xếp làm việc (Stack) 0 1 1 0 0 1 0 1 Y Bộ điều khiển B R 2 PDAVí dụ: xét L = {wcwR | w  (0 + 1)*} được sinh ra từ CFG S → 0S0 | 1S1 | cTa xây dựng PDA như sau: • Bộ điều khiển có 2 trạng thái q1 và q2 • Stack có 3 ký hiệu: xanh (B), vàng (Y) và đỏ (R) • Quy tắc thao tác trên automata: 3 PDACác khái niệm: • Phân loại PDA: đơn định (DPDA) và không đơn định (NPDA) • Phép chuyển: có 2 kiểu ✔ Phụ thuộc ký hiệu nhập: với một trạng thái, một ký hiệu tại đỉnh Stack và một ký hiệu nhập, PDA lựa chọn trạng thái kế tiếp, thay thế ký hiệu trên Stack và di chuyển đầu đọc trên băng nhập. ✔ Không phụ thuộc ký hiệu nhập (ε – dịch chuyển): ký hiệu nhập không được dùng, đầu đọc không di chuyển. • Ngôn ngữ được chấp nhận bởi PDA ✔ Bởi Stack rỗng ✔ Bởi trạng thái kết thúc Một ngôn ngữ được chấp nhận bởi PDA khi và chỉ khi nó là một ngôn ngữ phi ngữ cảnh. 4 PDAĐịnh nghĩa: một PDA M là một hệ thống 7 thành phần M (Q, Σ, Γ, δ, q0, Z0, F) • Q : tập hữu hạn các trạng thái • Σ : bộ chữ cái nhập • Γ : bộ chữ cái Stack • δ : hàm chuyển Q x (Σ  {ε}) x Γ → tập con của Q x Γ* • q0 : trạng thái khởi đầu • Z0 : ký hiệu bắt đầu trên Stack • F  Q : tập các trạng thái kết thúc (nếu PDA chấp nhận chuỗi bằng Stack rỗng thì F = Ø) 5 PDAHàm chuyển δ: • Hàm chuyển phụ thuộc ký hiệu nhập δ(q, a, Z) = { (p1, γ1), (p2, γ2), ..., (pm, γm) } • Hàm chuyển không phụ thuộc ký hiệu nhập δ(q, ε, Z) = { (p1, γ1), (p2, γ2), ..., (pm, γm) }Ví dụ: PDA chấp nhận wcwR bằng Stack rỗng1) δ(q1, 0, R) = {(q1, BR)} 7) δ(q1, c, R) = {(q2, R)}2) δ(q1, 1, R) = {(q1, YR)} 8) δ(q1, c, B) = {(q2, B)}3) δ(q1, 0, B) = {(q1, BB)} 9) δ(q1, c, Y) = {(q2, Y)}4) δ(q1, 1, B) = {(q1, YB)} 10) δ(q2, 0, B) = {(q2, ε)}5) δ(q1, 0, Y) = {(q1, BY)} 11) δ(q2, 1, Y) = {(q2, ε)}6) δ(q1, 1, Y) = {(q1, YY)} 12) δ(q2, ε, R) = {(q2, ε)} 6 PDAHình thái (ID): dùng để ghi nhớ trạng thái và nội dung của Stack (q, aw, Zα) ⊢M (p, w, βα) nếu δ(q, a, Z) chứa (p, β)Ngôn ngữ chấp nhận bởi PDA: • Ngôn ngữ được chấp nhận bằng trạng thái kết thúc L (M) = {w | (q0, w, Z0) ⊢* (p, ε, γ) với p  F và γ  Γ*} • Ngôn ngữ được chấp nhận bởi Stack rỗng N (M) = {w | (q0, w, Z0) ⊢* (p, ε, ε) với p  Q}Ví dụ: PDA chấp nhận wcwR bằng Stack rỗng với chuỗi nhập001c100 (q1, 001c100, R) ⊢ (q1, 01c100, BR) ⊢ (q1, 1c100, BBR) ⊢ (q1, c100, YBBR) ⊢ (q2, 100, YBBR) ⊢ (q2, 00, BBR) ⊢ (q2, 0, BR) ⊢ (q2, ε, R) ⊢ (q2, ε, ε) : Chấp nhận 7 PDA không đơn định (NPDA)Ví dụ: thiết kế PDA chấp nhận {wwR | w  (0 + 1)*} bằng Stack rỗng • Không có ký hiệu c để biết thời điểm chuyển từ trạng thái q1 sang q2 • Bắt buộc phải đoán thử (khi thấy 2 ký hiệu liên tiếp giống nhau) ✔ Nếu ký hiệu thuộc chuỗi xuôi : giữ nguyên trạng thái q và push 1 vào Stack ✔ Nếu ký hiệu thuộc chuỗi ngược : chuyển sang trạng thái q và pop 2 khỏi Stack • M({q1, q2}, {0, 1}, {R, B, Y}, δ, q1, R, Ø): 1) δ(q1, 0, R) = {(q1, BR)} 6) δ(q1, 1, Y) = {(q1, YY),(q2, ε)} 2) δ(q1, 1, R) = {(q1,YR)} 7) δ(q2, 0, B) = {(q2, ε)} 3) δ(q1, 0, B) = {(q1, BB), (q2, ε)} 8) δ(q2, 1, Y) = {(q2, ε)} 4) δ(q1, 0, Y) = {(q1, BY)} 9) δ(q1, ε, R) = {(q2, ε)} 5) δ(q1, 1, B) = {( ...