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)
44 trang |
Chia sẻ: tlsuongmuoi | Lượt xem: 2632 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Ôtômát đẩy xuống, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Trang 224
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
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 225
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
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 226
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ôtômat đẩy xuống không đơn định
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.
Control unit
Stack
Input file
Trang 227
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 228
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ
δ(q, a, b) = {(p, cd)}
Ví dụ
Xét một npda với
Q = {q0, q1, q2, qf},
Σ = {a, b},
Γ = {0, 1, z},
F = {qf},
Stack
a
b
c
d
Input file
Control unit
qp
Trang 229
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ì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 230
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
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).
, ,
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.
_|
_|
_|
*_| +_|
M
_|
Trang 231
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ởiM 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 232
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ển
sau.
(q0, baab, z) (q0, aab, 1z) (q0, ab, z) (q0, b, 0z) (q0, λ, z)
(qf, λ, z)
_| _| _| _|
_|
Trang 233
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, z) = {(q0, az)},δ(q0, b, z) = {(q0, bz)},δ(q0, a, a) = {(q0, aa)},δ(q0, b, a) = {(q0, ba)},δ(q0, a, b) = {(q0, ab)},δ(q0, b, b) = {(q0, bb)}.
δ(q0, λ, a) = {(q1, a)},δ(q0, λ, b) = {(q1, b)},
δ(q1, a, a) = {(q1, λ)},δ(q1, b, b) = {(q1, λ)},
δ(q1, λ, z) = {(qf, z)}.
Trang 234
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
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 235
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
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 236
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ô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 237
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ữ đượ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 238
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
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 239
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
Stacka
z
Input file
Control unit
q01
a bba
Input file
a bb
•S ⇒ a•SA
⇒ aa•A
⇒ aab•B
⇒ aabb•
S
S
A
##
Bf
S → aSA | a,
A → bB,
B → b.
Trang 240
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Đị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 241
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ
S→ aA,
A→ aABC | bB | a,
B→ b,
C→ c.
δ(q0, λ, z) = {(q1, Sz)},δ(q1, a, S) = {(q1, A)},δ(q1, a, A) = {(q1, ABC), (q1, λ)},δ(q1, b, A) = {(q1, B)},δ(q1, b, B) = {(q1, λ)},δ(q1, c, C) = {(q1, λ)},δ(q1, λ, z) = {(qf, z)}. w = aaabc
•S
⇒ a•A
⇒ aa•ABC
⇒ aaa•BC
⇒ aaab•C
⇒ aaabc•
(q0, aaabc, z) (q1, aaabc, Sz)
(q1, aabc, Az)
(q1, abc, ABCz)
(q1, bc, BCz)
(q1, c, Cz)
(q1, λ, z)
(qf, λ, z).
_|
_|
_|
_|
_|
_|
_|
Trang 242
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
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 243
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ
S → aA | bBbS | AB,
A → aB | bBaA,
B → aBbB | SB | λ
δ(q0, λ, z) = {(q1, Sz)},δ(q1, a, S) = {(q1, A)},δ(q1, b, S) = {(q1, BbS)},δ(q1, λ, S) = {(q1, AB)},δ(q1, a, A) = {(q1, B)},δ(q1, b, A) = {(q1, BaA)},δ(q1, a, B) = {(q1, BbB)},δ(q1, λ, B) = {(q1, SB), (q1, λ)},δ(q1, a, a) = {(q1, λ)},δ(q1, b, b) = {(q1, λ)},δ(q1, λ, z) = {(qf, z)}.
w = baabaa
•S
⇒ b•BbS
⇒ b•SBbS
⇒ ba•ABbS
⇒
baa•BBbS
⇒ baa•BbS
⇒ baab•S
⇒ baaba•A
⇒ baabaa•B
⇒ baabaa•
(q0, baabaa, z)
(q1, baabaa, Sz)
(q1, aabaa, BbSz)
(q1, aabaa, SBbSz)
(q1, abaa, ABbSz)
(q1, baa, BBbSz)
(q1, baa, BbSz)
(q1, baa, bSz)
(q1, aa, Sz)
(q1, a, Az)
(q1, λ, Bz)
(q1, λ, z)
(qf, λ, z).
_|
_|
_|
_|
_|
_|
_|
_|
_|
_|
_|
_|
Trang 244
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
VPPNC cho ôtômát đẩy xuống
Quá trình này ngược với quá trình trong Định lý 7.1, tức là xây
dựng văn phạm mô phỏng sự di chuyển của pda.
Phần biến của dạng câu phản ánh nội dung stack, phần chuỗi
nhập đã được xử lý chính là phần chuỗi kí hiệu kết thúc làm
tiếp đầu ngữ của dạng câu.
Bổ đề
∀ npda ∃ npda tương đương thõa 2 điều kiện
(1) Chỉ có một trạng thái kết thúc và npda chỉ ở trong trạng thái
này ⇔ stack là trống.
(2) Mọi chuyển trạng thái có dạng δ(qi, a, A) = {c1, c2, ...,
cn}, trong đó
ci = (qj, λ), (7.5) hoặc
ci = (qj, BC) (7.6)
Tức là, một di chuyển
hoặc tăng hoặc giảm nội
dung stack một kí hiệu.
Trang 245
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
VPPNC cho ôtômát đẩy xuống (tt)
Chúng ta muốn dạng câu chỉ ra nội dung của stack.
Cấu hình của một npda còn liên quan đến trạng thái nội của
ôtômát nên nó phải được ghi nhớ trong dạng câu.
Lấy (qiAqj) làm các biến cho văn phạm, với diễn dịch
(qiAqj) w nếu và chỉ nếu npda “xóa” A khỏi stack và đi từ
trạng thái qi đến qj trong khi đọc ngõ nhập chuỗi w.
“Xóa” ở đây có nghĩa là A và các kết quả sau nó biến mất khỏi
stack, và kí hiệu ngay bên dưới A sẽ trở thành đỉnh stack.
Ví dụ
δ(qi, a, A) = (qj, λ) (qiAqj) → a
δ(qi, a, A) = (qj, BC) (qiAqk) → a(qjBql)(qlCqk)
*⇒
Trang 246
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
VPPNC cho ôtômát đẩy xuống (tt)
trong đó qk và ql lấy mọi giá trị có thể trong Q.
Khi vét cạn có thể có một vài qk không thể đạt tới được từ qi
trong khi xóa A cũng như có thể có một vài ql không thể đạt tới
được từ qj trong khi xóa B.
Trong trường hợp đó các biến (qiAqk) và (qjbql) sẽ là vô dụng.
Những biến này sẽ được loại bỏ bằng giải thuật loại bỏ các biến
vô dụng đã học.
Biến (q0zqf) sẽ là biến khởi đầu, trong đó qf là trạng thái kết
thúc đơn của npda.
Trang 247
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ
Xây dựng VPPNC cho npda sau (q0 khởi đầu, q2 kết thúc)
δ(q0, a, z) = {(q0, Az)},
δ(q0, a, A) = {(q0, A)},
δ(q0, b, A) = {(q1, λ)},
δ(q1, λ, z) = {(q2, λ)}.
Biến đổi nó thành npda tương đương thõa 2 điều kiện.
δ(q0, a, z) = {(q0, Az)}, (1)
δ(q0, a, A) = {(q3, λ)}, (2)
δ(q3, λ, z) = {(q0, Az)}, (3)
δ(q0, b, A) = {(q1, λ)}, (4)
δ(q1, λ, z) = {(q2, λ)}. (5)
L = {anb : n ≥ 1}
Trang 248
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
Ba chuyển trạng thái (2), (4), (5) có dạng (7.5) nên có các luật
sinh tương ứng với nó là
δ(q0, a, A) = {(q3, λ)}, (2) (q0Aq3) → a (6)
δ(q0, b, A) = {(q1, λ)}, (4) (q0Aq1) → b (7)
δ(q1, λ, z) = {(q2, λ)}. (5) (q1zq2) → λ (8).
Trang 249
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
δ(q0, a, z) = {(q0, Az)} được mô phỏng thành
(q0zq0) → a(q0Aq0)(q0zq0) | a(q0Aq1)(q1zq0) | a(q0Aq2)(q2zq0) |
a(q0Aq3)(q3zq0),
(q0zq1) → a(q0Aq0)(q0zq1) | a(q0Aq1)(q1zq1) | a(q0Aq2)(q2zq1) |
a(q0Aq3)(q3zq1),
(q0zq2) → a(q0Aq0)(q0zq2) | a(q0Aq1)(q1zq2) | a(q0Aq2)(q2zq2) |
a(q0Aq3)(q3zq2),
(q0zq3) → a(q0Aq0)(q0zq3) | a(q0Aq1)(q1zq3) | a(q0Aq2)(q2zq3) |
a(q0Aq3)(q3zq3),
Trang 250
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
Chuyển trạng thái δ(q3, λ, z) = {(q0, Az)} có thể được mô phỏng
bằng tập luật sinh sau
(q3zq0) → (q0Aq0)(q0zq0) | (q0Aq1)(q1zq0) | (q0Aq2)(q2zq0) |
(q0Aq3)(q3zq0),
(q3zq1) → (q0Aq0)(q0zq1) | (q0Aq1)(q1zq1) | (q0Aq2)(q2zq1) |
(q0Aq3)(q3zq1),
(q3zq2) → (q0Aq0)(q0zq2) | (q0Aq1)(q1zq2) | (q0Aq2)(q2zq2) |
(q0Aq3)(q3zq2),
(q3zq3) → (q0Aq0)(q0zq3) | (q0Aq1)(q1zq3) | (q0Aq2)(q2zq3) |
(q0Aq3)(q3zq3),
Trang 251
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
Biến khởi đầu của văn phạm là (q0zq2).
Loại bỏ biến vô dụng
(q0zq0) → a(q0Aq0)(q0zq0) | a(q0Aq1)(q1zq0) | a(q0Aq2)(q2zq0) |
a(q0Aq3)(q3zq0),
(q0zq1) → a(q0Aq0)(q0zq1) | a(q0Aq1)(q1zq1) | a(q0Aq2)(q2zq1) |
a(q0Aq3)(q3zq1),
(q0zq2) → a(q0Aq0)(q0zq2) | a(q0Aq1)(q1zq2) | a(q0Aq2)(q2zq2) |
a(q0Aq3)(q3zq2),
(q0zq3) → a(q0Aq0)(q0zq3) | a(q0Aq1)(q1zq3) | a(q0Aq2)(q2zq3) |
a(q0Aq3)(q3zq3),
(q0Aq3) → a (6)
(q0Aq1) → b (7)
(q1zq2) → λ (8)
Trang 252
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
(q3zq0) → (q0Aq0)(q0zq0) | (q0Aq1)(q1zq0) | (q0Aq2)(q2zq0) |
(q0Aq3)(q3zq0),
(q3zq1) → (q0Aq0)(q0zq1) | (q0Aq1)(q1zq1) | (q0Aq2)(q2zq1) |
(q0Aq3)(q3zq1),
(q3zq2) → (q0Aq0)(q0zq2) | (q0Aq1)(q1zq2) | (q0Aq2)(q2zq2) |
(q0Aq3)(q3zq2),
(q3zq3) → (q0Aq0)(q0zq3) | (q0Aq1)(q1zq3) | (q0Aq2)(q2zq3) |
(q0Aq3)(q3zq3),
(q0Aq3) → a (6)
(q0Aq1) → b (7)
(q1zq2) → λ (8)
Trang 253
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
(q0, aab, z) (q0, ab, Az) (q0zq2) ⇒ a(q0Aq3)(q3zq2)
(q3, b, z) ⇒ aa(q3zq2)
(q0, b, Az) ⇒ aa(q0Aq1)(q1zq2)
(q1, λ, z) ⇒ aab(q1zq2)
(q2, λ, λ) ⇒ aab
Phân tích chuỗi aab
_|
_|
_|
_|
_|
Npda
δ(q0, a, z) = {(q0, Az)},δ(q0, a, A)= {(q3, λ)},δ(q3, λ, z) = {(q0, Az)},δ(q0, b, A)= {(q1, λ)},δ(q1, λ, z) = {(q2, λ)}.
Văn phạm kết quả
(q0zq2) → a(q0Aq1)(q1zq2) | a(q0Aq3)(q3zq2),
(q3zq2) → (q0Aq1)(q1zq2) | (q0Aq3)(q3zq2),
(q0Aq3) → a,
(q0Aq1) → b,
(q1zq2) → λ,
Trang 254
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
Định lý 7.2
Nếu L = L(M) đối với một npda M nào đó, thì L là NNPNC.
S → aBC | aAX,
X→ BC | AX,
A→ a,
B→ b,
C→ λ,
S → ab | aaX,
X → b | aX, L = {anb : n ≥ 1}
Rút gọn văn phạm
(q0zq2) → a(q0Aq1)(q1zq2) | a(q0Aq3)(q3zq2),
(q3zq2) → (q0Aq1)(q1zq2) | (q0Aq3)(q3zq2),
(q0Aq3) → a,
(q0Aq1) → b,
(q1zq2) → λ,
Trang 255
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
PDA đơn định và NNPNC đơn định
Định nghĩa 7.3
Một ôtômát đẩy xuống M = (Q, Σ, Γ, δ, q0, z, F) được gọi là
đơn định nếu nó là một ôtômát được định nghĩa như trong
Định nghĩa 7.1, nhưng phải chịu sự giới hạn rằng, đối ∀ trạng
thái q ∈ Q, kí hiệu a ∈ Σ ∪ {λ}, và b ∈ Γ,
(1) δ(q, a, b) chứa tối đa một phần tử,
(2) Nếu δ(q, λ, b) ≠ ∅, thì δ(q, c, b) phải = ∅ ∀ c ∈ Σ.
Định nghĩa 7.4
Một ngôn ngữ L được gọi là NNPNC đơn định nếu và chỉ nếu
tồn tại một dpda M sao cho L = L(M).
Trang 256
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ
Ngôn ngữ L = {anbn: n ≥ 0} là PNCĐĐ. Vì nó được chấp nhận
bởi dpda sau
M = ({q0f, q1, q2}, {a, b}, {z, a}, δ, q0f, z, {q0f}) với
δ(q0f, a, z) = {(q1, az)},
δ(q1, a, a) = {(q1, aa)},
δ(q1, b, a) = {(q2, λ)},
δ(q2, b, a) = {(q2, λ)},
δ(q2, λ, z) = {(q0f, λ)}.
Trang 257
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ (tt)
Cách 2 (với # là kí hiệu kết thúc chuỗi – eof)
M = ({q0, q1, qf}, {a, b}, {z, 1}, δ, q0, z, {qf}) với
δ(q0, #, z) = {(qf, λ)},
δ(q0, a, z) = {(q0, 1z)},
δ(q0, a, 1) = {(q0, 11)},
δ(q0, b, 1) = {(q1, λ)},
δ(q1, b, 1) = {(q1, λ)},
δ(q1, #, z) = {(qf, λ)}.
Trang 258
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Bài tập
Xây dựng dpda 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 259
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Dpda và Npda
Dpda là một lớp con thực sự của npda
L1 = {anbn : n ≥ 0} và L2 = {anb2n : n ≥ 0} là các NNPNC và L =
L1 ∪ L2 cũng là NNPNC.
L sẽ được chứng minh không phải là NNPNC đơn định.
Chứng minh
Trước hết chúng ta sử dụng một kết quả trong Chương 8 là rằng
ngôn ngữ L0 = {anbncn : n ≥ 0} là không phi ngữ cảnh.
Giả sử L là NNPNC đơn định, gọi M = (Q, Σ, Γ, δ, q0, z, F) là
dpda của L với Q = {q0, q1, ..., qn}
Trang 260
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Dpda và Npda (tt)
Xét
M’ = (Q’, Σ, Γ, δ ∪ δ’, q0 , z, F’)
Q’ = Q ∪ {q0’, q1’, ..., qn’},
F’ = F ∪ {qi’ : qi ∈ F},
δ’(qf, λ, s) = {(qf’, s)} ∀ qf ∈ F, s ∈ Γ, và
δ’(qi’, c, s) = {(qj’, u)} ∀ δ(qi, b, s) ={(qj, u)},
anbn
cn
bn
λ λ
Đơn vị điều khiển của M
Phần thêm vào
Trang 261
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Dpda và Npda (tt)
Để M chấp nhận anbn chúng ta phải có
(q0, anbn, z) * (qi, λ, u) , với qi ∈ F.
Bởi M là đơn định, nó cũng phải đúng rằng
(q0, anb2n, z) * (qi, bn, u),
vậy để nó chấp nhận anb2n phải có
(qi, bn, u) * (qj, λ, u1),
với một qj nào đó ∈ F. Nhưng theo cách xây dựng ta có
(qi’, cn, u) * (qj’, λ, u1),
như vậy M’ sẽ chấp nhận anbncn.
Không có chuỗi nào khác hơn những chuỗi trong L’ là được
chấp nhận bởi M’.
Suy ra {anbncn} là PNC (><). Vậy L PNC không đơn định.
M
_|
M
_|
M
_|
M
_|
Trang 262
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Văn phạm cho các NNPNC đơn định
NNPNCĐĐ cho phép PTCP một cách hiệu quả, bằng cách xem
dpda như là một thiết bị phân tích.
Tính đơn định suy ra việc xử lý chuỗi nhập trong thời gian
tuyến tính với chiều dài chuỗi nhập.
Những loại văn phạm nào thích hợp cho việc mô tả các
NNPNCĐĐ và cho phép PTCP thời gian tuyến tính.
Giả sử chúng ta đang phân tích từ trên xuống, đang thử tìm
DXTN của một câu cụ thể.
Chuỗi nhập w a1 a2 a3 a4 . . . an
Dạng câu a1 a2 a3 A . . .
Phần đã được Phần còn chưa được
so trùng so trùng
Trang 263
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Văn phạm cho các NNPNC đơn định (tt)
Quét chuỗi nhập w từ trái sang phải, trong khi phát triển dạng
câu mà chuỗi kí hiệu kết thúc tiếp đầu ngữ của nó so trùng với
tiếp đầu ngữ của chuỗi w cho đến kí hiệu được quét hiện tại.
Để tiếp tục so trùng các kí hiệu kế tiếp, chúng ta muốn biết
chính xác luật sinh nào là được áp dụng tại mỗi bước để tránh
backtracking và cho phép PTCP hiệu quả.
Có hay không loại văn phạm cho phép làm điều này?
Với VPPNC tổng quát, điều này là không thể, nhưng nếu dạng
của văn phạm được hạn chế hơn, có thể thực hiện được mục
đích của chúng ta.
Văn phạm-s là một ví dụ nhưng khả năng biểu diễn ngôn ngữ
của nó còn hạn chế.
Trang 264
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Văn phạm LL(k)
Định nghĩa 7.5
Cho G = (V, T, S, P) là một VPPNC. Nếu đối với mọi cặp dẫn
xuất trái nhất
S w1Ax1⇒ w1y1x1 w1w2,
S w1Ax2⇒ w1y2x2 w1w3,
với w1, w2, w3 ∈ T*, sự bằng nhau của k kí hiệu trái nhất của w2
và w3 (nếu có) ⇒ y1 = y2, thì G được gọi là một VPLL(k).
Điều này có nghĩa là nếu nhìn trước k kí hiệu ngõ nhập thì chỉ
có tối đa một luật sinh là đúng đắn nhất.
Ví dụ
Văn phạm bên là thuộc loại LL(1)
*⇒ *⇒
*⇒ *⇒
S → aX | bS, (1, 2)
X → b | aS, (3, 4)
Trang 265
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Văn phạm LL(k)
Bảng PTCP
Ví dụ
Các văn phạm sau đây thuộc họ LL(k) không? Nếu có k = ?
S → aSbS | bSaS | λ, (1, 2, 3)
S → aX | bS, (1, 2)
X → b | aS, (3, 4)
34X
21S
#ba
S → aS | AB, (1, 2)
A → bA | b, (3, 4)
B → aS | b, (5, 6)
Trang 266
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Văn phạm LL(k)
Văn phạm LL(k) cho phép PTCP đơn định nếu nhìn trước k kí
hiệu.
Văn phạm LL là một chủ đề quan trọng trong việc nghiên cứu
các trình biên dịch.
Một số NNLT có thể được định nghĩa bằng các văn phạm LL,
và nhiều trình biên dịch đã được viết bằng cách sử dụng các bộ
PTCP LL.
Nhưng văn phạm LL là không đủ tổng quát để giải quyết các
NNPNCĐĐ. Vì vậy, có một mối quan tâm đến các loại văn
phạm khác, văn phạm đơn định tổng quát hơn.
Đó là văn phạm LR, cái mà cho phép PTCP hiệu quả, và xây
dựng cây dẫn xuất từ dưới lên.
Trang 267
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Bài tập
Xây dựng văn phạm LL(k) cho các ngôn ngữ sau
L1 = {anbn: n ≥ 0}
L2 = {w ∈ {a , b}*: na(w) = nb(w)}
L3 = {w ∈ {a , b}*: na(w) = nb(w), na(v) ≥ nb(v) với v là một tiếp
đầu ngữ bất kỳ của w}
Các file đính kèm theo tài liệu này:
- Ôtômát đẩy xuống.pdf