intTypePromotion=3

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

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:0

0
112
lượt xem
29
download

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

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

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....

Chủ đề:
Lưu

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

  1. Chương 7 Ôtômát đẩy xuống Có 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à đếm không giới hạn. Từ ví dụ ngôn ngữ {wwR}, chúng ta cần thêm khả năng lư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 (PushDown Automata - PDA) Trang 224 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  2. Chương 7 Ôtômát đẩy xuống 7.1 PDA không đơn định 7.2 NPDA và NNPNC 7.3 PDA đơn định và NNPNC đơn định 7.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
  3. Ôtômat đẩy xuống không đơn định Input file Stack Control unit Mỗ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ệu hiệ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
  4. Đị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
  5. Ví dụ δ(q, a, b) = {(p, cd)} Input file a Stack Control unit c p q Ví 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
  6. 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ình chế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
  7. Một số khái niệm Hì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
  8. 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
  9. 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ển sau. (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
  10. 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)}. δ(q1, λ, z) = {(qf, z)}. Trang 233 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  11. Ví dụ (tt) Dãy chuyển hình trạng để chấp nhận chuỗi abba là. (q0, abba, z) |_ (q0, bba, az) |_ (q0, ba, baz) |_ (q1, ba, baz) |_ (q1, a, az) |_ (q1, λ, z) |_ (qf, λ, z). Npda cải tiến δ(q0, a, z) = {(q0, aa)}, δ(q1, a, a) = {(q1, λ)}, δ(q0, b, z) = {(q0, bz)}, δ(q1, b, b) = {(q1, λ)}, δ(q0, a, a) = {(q0, aa), (q1, λ)}, δ(q1, λ, z) = {(qf, z)}. δ(q0, b, a) = {(q0, ba)}, δ(q0, a, b) = {(q0, ab)}, δ(q0, b, b) = {(q0, bb), (q1, λ)}. Trang 234 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  12. Bài tập Dãy chuyển hình trạng để chấp nhận chuỗi abba là. (q0, abba, z) |_ (q0, bba, az) |_ (q0, ba, baz) |_ (q1, a, az) |_ (q1, λ, z) |_ (qf, λ, z). Xây dựng npda cho các ngôn ngữ sau L1 = {anbmcn+m: n, m ≥ 0} L2 = {anbn+mcm: n, m ≥ 1} L3 = {anbm: 2n ≤ m ≤ 3n} L4 = {w: na(w) = nb(w) + 2} L5 = {w: na(w) = 2nb(w)} L6 = {w: 2nb(w) ≤ na(w) ≤ 3nb(w)} Trang 235 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  13. Ôtômát đẩy xuống cho NNPNC Chúng ta xây dựng một npda mà có thể thực hiện được (mô phỏng) một DXTN của một chuỗi bất kỳ trong ngôn ngữ. Giả thiết ngôn ngữ được sinh ra bởi một văn phạm có dạng chuẩn Greibach. Pda sắp xây dựng sẽ biểu diễn sự dẫn xuất bằng cách như sau. Giữ các biến trong phần bên phải của dạng câu trên stack của nó, còn phần bên trái, chuỗi chứa các kí hiệu kết thúc, là giống với phần chuỗi đã được đọc ở ngõ nhập. Chúng ta bắt đầu bằng việc đặt kí hiệu khởi đầu lên stack. Để mô phỏng việc áp dụng luật sinh A → ax, chúng ta phải có biến A trên đỉnh stack và kí hiệu kết thúc a là kí hiệu nhập. Biến trên đỉnh stack được loại bỏ và thay thế bằng chuỗi biến x. Trang 236 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  14. Ví dụ Xây dựng npda cho ngôn ngữ được sinh ra bởi văn phạm sau. S → aSbb | a. Đầu tiên ta biến đổi văn phạm này sang dạng chuẩn Greibach, thành văn phạm là: S → aSA | a, A → bB, B → b. Automat tương ứng sẽ có ba trạng thái {q0, q1, qf}, với trạng thái khởi đầu là q0 và trạng thái kết thúc là qf. Đầu tiên, ở trạng thái khởi đầu biến S được đặt trên stack bằng δ(q0, λ, z) = {(q1, Sz)} Trang 237 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  15. Ví dụ (tt) Các luật sinh S → aSA | a được mô phỏng thành δ(q1, a, S) = {(q1, SA), (q1, λ)} Bằng kiểu tương tự, các luật sinh khác được mô phỏng bằng δ(q1, b, A) = {(q1, B)}, δ(q1, b, B) = {(q1, λ)} Sự xuất hiện kí hiệu khởi đầu stack trên đỉnh stack báo hiệu sự hoàn tất của dẫn xuất và PDA sẽ được đặt vào trong trạng thái kết thúc của nó bằng chuyển trạng thái δ(q1, λ, z) = {(qf, λ)}. Trang 238 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  16. Ví dụ (tt) Input file Input file S → aSA | a, A → bB, aabb# aabb# Stack B → b. Control unit •S ⇒ a•SA S q0 A B S ⇒ aa•A f 1 z ⇒ aab•B ⇒ aabb• Trang 239 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  17. Định lý Định lý 7.1 Đối với một NNPNC bất kỳ không chứa λ, tồn tại một npda M sao cho L = L(M). Thủ tục: GGreibach-to-npda Input: G = (V, T, S, P) có dạng chuẩn Greibach Output: npda M = (Q, Σ, Γ, δ, q0, z, F) sao cho L(M) = L(G). B1 M = ({q0, q1, qf}, T, V ∪ {z}, δ, q0, z, {qf}), z ∉ V. B2 δ(q0, λ, z) = {(q1, Sz)} B3 δ(q1, a, A) ∋ {(q1, u)} ⇔ P có luật sinh A → au B4 δ(q1, λ, z) = {(qf, z)} Trang 240 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  18. Ví dụ δ(q0, λ, z) = {(q1, Sz)}, S → aA, δ(q1, a, S) = {(q1, A)}, A → aABC | bB | a, δ(q1, a, A) = {(q1, ABC), (q1, λ)}, B → b, δ(q1, b, A) = {(q1, B)}, C → c. δ(q1, b, B) = {(q1, λ)}, δ(q1, c, C) = {(q1, λ)}, δ(q1, λ, z) = {(qf, z)}. w = aaabc (q0, aaabc, z) |_ (q1, aaabc, Sz) •S |_ (q1, aabc, Az) ⇒ a•A |_ (q1, abc, ABCz) ⇒ aa•ABC |_ (q1, bc, BCz) ⇒ aaa•BC |_ (q1, c, Cz) ⇒ aaab•C |_ (q1, λ, z) ⇒ aaabc• |_ (qf, λ, z). Trang 241 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  19. Thủ tục G-to-npda cải tiến Thủ tục: G-to-npda Input: G = (V, T, S, P) có dạng tùy ý Output: npda M = (Q, Σ, Γ, δ, q0, z, F) sao cho L(M) = L(G). B1 M = ({q0, q1, qf}, T, V ∪ T ∪ {z}, δ, q0, z, {qf}), z ∉ V. B2 δ(q0, λ, z) = {(q1, Sz)} B3 δ(q1, a, A) ∋ {(q1, u)} ⇔ P có luật sinh A → au, a ∈ T B4 δ(q1, λ, A) ∋ {(q1, u)} ⇔ P có luật sinh A → u và u không có kí hiệu kết thúc đi đầu. B5 δ(q1, a, a) = (q1, λ) với a ∈ T và a xuất hiện trong một vế phải luật sinh nào đó mà không phải ở vị trí khởi đầu. B6 δ(q1, λ, z) = {(qf, z)} Trang 242 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  20. S → aA | bBbS | AB, A → aB | bBaA, Ví dụ B → aBbB | SB | λ δ(q0, λ, z) = {(q1, Sz)}, (q0, baabaa, z) w = baabaa |_(q1, baabaa, Sz) δ(q1, a, S) = {(q1, A)}, •S |_(q1, aabaa, BbSz) δ(q1, b, S) = {(q1, BbS)}, ⇒ b•BbS |_(q1, aabaa, SBbSz) δ(q1, λ, S) = {(q1, AB)}, ⇒ b•SBbS |_(q1, abaa, ABbSz) δ(q1, a, A) = {(q1, B)}, ⇒ ba•ABbS |_(q1, baa, BBbSz) δ(q1, b, A) = {(q1, BaA)}, ⇒ |_(q1, baa, BbSz) δ(q1, a, B) = {(q1, BbB)}, baa•BBbS |_(q1, baa, bSz) δ(q1, λ, B) = {(q1, SB), (q1, λ)}, ⇒ baa•BbS |_ (q1, aa, Sz) δ(q1, a, a) = {(q1, λ)}, ⇒ baab•S |_ (q1, a, Az) δ(q1, b, b) = {(q1, λ)}, ⇒ baaba•A |_ (q1, λ, Bz) δ(q1, λ, z) = {(qf, z)}. ⇒ baabaa•B |_ (q1, λ, z) ⇒ baabaa• |_ (qf, λ, z). Trang 243 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản