Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 7

Tài liệu tham khảo Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức trường đaị học Bách Khoa khoa Công nghệ thông tin - Chương 7 Ôtômát đẩy xuống.Cụ thể thì Vật lý khoa học nghiên cứu về các quy luật vận động của tự nhiên, từ thang vi mô (các hạt cấu tạo nên vật chất) cho đến thang vĩ mô (các hành tinh, thiên hà và vũ trụ). Trong tiếng Anh, từ vật lý (physics) bắt nguồn từ tiếng Hy Lạp φύσις (phusis) có nghĩa là tự nhiên và φυσικός (phusikos) là thuộc về tự nhiên....
Nội dung trích xuất từ tài liệu:
Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 7 Chương 7 Ôtômát đẩy xuốngCó hay không lớp ôtômát tương ứng với lớp NNPNC?Như đã biết, ôtômát hữu hạn không thể nhận biết tất cảNNPNC, chẳng hạn L = {anbn : n ≥ 0}, vì nó có một bộnhớ hữu hạn. Vì vậy chúng ta muốn có một máy mà đếmkhông giới hạn.Từ ví dụ ngôn ngữ {wwR}, chúng ta cần thêm khả nănglưu và so trùng một dãy kí hiệu trong thứ tự ngược lại.Điều này đề nghị chúng ta thử một stack như một cơ chếlưu trữ. Đó chính là lớp ôtômát đẩy xuống (PushDownAutomata - PDA) Trang 224 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 7 Ôtômát đẩy xuống7.1 PDA không đơn định7.2 NPDA và NNPNC7.3 PDA đơn định và NNPNC đơn định7.4 Văn phạm cho NNPNC đơn định Trang 225 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ôtômat đẩy xuống không đơn định Input file Stack Control unitMỗi di chuyển của đơn vị điều khiển đọc một kí hiệu nhập,trong cùng thời điểm đó thay đổi nội dung của stack.Mỗi di chuyển được xác định bằng kí hiệu nhập hiện tại, kí hiệuhiện tại trên đỉnh của stack. Kết quả là một trạng thái mới củađơn vị điều khiển và một sự thay đổi trên đỉnh của stack.Chúng ta sẽ chỉ nghiên cứu các PDA thuộc loại accepter. Trang 226 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Định nghĩa ôtômát đẩy xuốngĐịnh nghĩa 7.1 Một accepter đẩy xuống không đơn định (npda) được định nghĩa bằng bộ bảy M = (Q, Σ, Γ, δ, q0, z, F), trong đó Q là tập hữu hạn các trạng thái nội của đơn vị điều khiển, Σ là bảng chữ cái ngõ nhập (input alphabet), Γ là bảng chữ cái stack (stack alphabet), q0 ∈ Q là trạng thái khởi đầu của đơn vị điều khiển, z ∈ Γ là kí hiệu khởi đầu stack (stack start symbol), F ⊆ Q là tập các trạng thái kết thúc. Hàm chuyển trạng thái δ là một ánh xạ δ : Q × (Σ ∪ {λ}) × Γ → tập con hữu hạn của Q × Γ*, Trang 227 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ δ(q, a, b) = {(p, cd)} Input file a Stack Control unit c p qVí dụ d b Xét một npda với Q = {q0, q1, q2, qf}, Σ = {a, b}, Γ = {0, 1, z}, F = {qf}, Trang 228 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Nhận xétδ (q0, a, z) = {(q1,1z), (qf, λ)}, δ (q0, λ, z) = {(qf, λ)},δ (q1, a, 1) = {(q1, 11)}, δ (q1, b, 1) = {(q2, λ)},δ (q2, b, 1) = {(q2, λ)}, δ (q2, λ, z) = {(qf, λ)}.δ (q0, b, 0) không được định nghĩa tương đương với cấu hìnhchết mà ta đã học.δ (q1, a, 1) = {(q1, 11)} thêm một kí hiệu 1 vào stack khi a đượcđọc.δ (q2, b, 1) = {(q2, λ)} xóa một kí hiệu 1 khỏi stack khi b đượcđọc.L(M) = {anbn : n ≥ 0} ∪ {a} Trang 229 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Một số khái niệmHình trạng tức thời Là bộ ba (q, w, u), trong đó q là trạng thái của đơn vị điều khiển, w là phần chưa đọc của chuỗi nhập, còn u là nội dung của stack (với kí hiệu trái nhất là kí hiệu đỉnh của stack). |_Di chuyển, Một di chuyển từ một hình trạng tức thời này đến một hình trạng tức thời khác sẽ được kí hiệu bằng |_ . (q1, aw, bx) |_ (q2, w, yx) là có khả năng ⇔ (q2, y) ∈ δ(q1, a, b). |_* , |_+ , |_ M Dấu * chỉ ra có ≥ 0 bước di chuyển được thực hiện còn dấu + chỉ ra ≥ 1 bước di chuyển. Chữ M chỉ ra di chuyển của ôtômát nào. Trang 230 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ngôn ngữ được chấp nhận bởi một npdaĐịnh nghĩa 7.2 Cho M = (Q, Σ, Γ, δ, q0, z, F) là một npda. Ngôn ngữ được chấp nhận bởi M là tập L(M) = {w ∈ Σ*: (q0, w, z) |_* (qf, λ, u), qf ∈ F, u ∈ Γ*}.Ví dụ Xây dựng một npda cho ngôn ngữ L = {w ∈ {a, b}*: na(w) = nb(w)} Trang 231 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụXây dựng npda cho ngôn ngữ này như sau.M = ({q0, qf}, {a, b}, {0, 1, z}, δ, q0, z, {qf}). δ(q0, λ, z) = {(qf, z)}, δ(q0, a, z) = {(q0, 0z)}, δ(q0, b, z) = {(q0, 1z)}, δ(q0, a, 0) = {(q0, 00)}, δ(q0, b, 0) = {(q0, λ)}, δ(q0, a, 1) = {(q0, λ)}, δ(q0, b, 1) = {(q0, 11)},Trong qúa trình xử lý chuỗi baab, npda thực hiện các di chuyểnsau.(q0, baab, z) |_ (q0, aab, 1z) |_ (q0, ab, z) |_ (q0, b, 0z) |_ (q0, λ, z)|_ (qf, λ, z) Trang 232 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ (tt)Xây dựng npda cho ngôn ngữ L = {wwR: w ∈ {a, b}+}M = ({q0, q1, qf}, {a, b}, {a, b, z}, δ, q0, z, {qf}). δ(q0, λ, a) = {(q1, a)}, δ(q0, a, z) = {(q0, az)}, δ(q0, λ, b) = {(q1, b)}, δ(q0, b, z) = {(q0, bz)}, δ(q0, a, a) = {(q0, aa)}, δ(q0, b, a) = {(q0, ba)}, δ(q1, a, a) = {(q1, λ)}, δ(q0, a, b) = {(q0, ab)}, δ(q1, b, b) = {(q1, λ)}, δ(q0, b, b) = {(q0, bb)}. ...