Bài giảng Lý thuyết Ôtômát và ngôn ngữ hình thức

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} Trang 268 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 8 Các tính chất của NNPNC „ Họ NNPNC chiếm một vị trí trung tâm trong hệ thống phân cấp các ngôn ngữ hình thức. „ Một mặt, NNPNC bao gồm các họ ngôn ngữ quan trọng nhưng bị giới hạn chẳng hạn như các NNPNC và PNCĐĐ. „ Mặt khác, có các họ ngôn ngữ khác rộng lớn hơn mà NNPNC chỉ là một trường hợp đặc biệt. „ Để nghiên cứu mối quan hệ giữa các họ ngôn ngữ và trình bày những cái giống nhau và khác nhau của chúng, chúng ta nghiên cứu các tính chất đặc trưng của các họ khác nhau. „ Như trong Chương 4, chúng ta xem xét tính đóng dưới nhiều phép toán khác nhau, các giải thuật để xác định tính thành viên, và cuối cùng là bổ đề bơm. Trang 269 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 8 Các tính chất của NNPNC 8.1 Hai bổ đề bơm 8.2 Tính đóng và các giải thuật quyết định cho NNPNC Trang 270 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bổ đề bơm cho NNPNC „ Định lý 8.1 „ Cho L là một NNPNC vô hạn, tồn tại một số nguyên dương m sao cho bất kỳ chuỗi w nào ∈ L với |w| ≥ m, w có thể được phân hoạch thành w = uvxyz (8.1) với |vxy| ≤ m (8.2) và |vy| ≥ 1 (8.3) sao cho uvixyiz ∈ L (8.4) ∀ i = 0, 1, 2, ... „ Định lý này được gọi là bổ đề bơm cho NNPNC. „ Chứng minh „ Xét ngôn ngữ L – {λ}. Đây là NNPNC ⇒ ∃ văn phạm có dạng chuẩn Chomsky G chấp nhận nó. Trang 271 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chứng minh „ Bổ đề „ Nếu cây dẫn xuất của một chuỗi w được sinh ra bởi một văn phạm Chomsky mà có chiều dài mọi con đường đi từ gốc tới lá nhỏ hơn hay bằng h thì |w| ≤ 2h-1. „ Bổ đề này có thể chứng minh bằng qui nạp dựa trên h. „ Trở lại chứng minh của định lý. Giả sử G có k biến (|V| = k). Chọn m = 2k. Lấy w bất kỳ ∈ L sao cho |w| ≥ m. Xét cây dẫn xuất T của w. „ Theo bổ đề trên suy ra T phải có ít nhất một con đường đi từ gốc tới lá có chiều dài ≥ k+1. S a B S A T1 T2 Trang 272 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chứng minh (tt) „ Xét một đường như vậy. Trên đường này có ≥ k+2 phần tử. Nếu không tính nốt lá là kí hiệu kết thúc thì có ≥ k+1 nốt là biến. „ Vì tập biến chỉ có k biến ⇒ ∃ hai nốt trùng vào một biến. Giả sử đó là biến A (hai lần xuất hiện kí hiệu là A1 và A2) u v x y zA2 S A1 Cây dẫn xuất T của w Trang 273 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chứng minh (tt) „ Trong cây trên, gọi u, v, x, y, z là các chuỗi có tính chất sau: S uA1z (1) A1 vA2y (2) A2 x (3) Và w = uvxyz. „ vxy là kết quả của cây có gốc là A1 mà mọi con đường của cây này có chiều dài ≤ (k +1)⇒ theo bổ đề trên |vxy|≤ 2k = m. Mặt khác vì văn phạm có dạng chuẩn Chomsky tức là không có luật sinh-đơn vị và luật sinh-λ nên từ (2) suy ra |vy|≥ 1. „ Từ (1), (2), (3) chúng ta có: S uAz uvAyz uviAyiz uvixyiz hay uvixyiz ∈ L ∀ i = 0, 1, 2, . . . „ Điều này kết thúc chứng minh. *⇒ *⇒ *⇒ *⇒ *⇒ *⇒ *⇒ Trang 274 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Bổ đề bơm này được dùng để chứng minh một ngôn ngữ là không PNC tương tự như ở Chương 4. „ Ví dụ „ Chứng minh ngôn ngữ L = {anbncn : n ≥ 0} là không PNC. „ Chứng minh „ Giả sử L là PNC ⇒ ∃ số nguyên dương m. Chọn w = ambmcm ∈ L. ∃ một phân hoạch của w thành bộ 5 w = uvxyz Vì |vxy| ≤ m nên vxy không chứa đồng thời cả 3 kí hiệu a, b, c. Chọn i = 2 ⇒ w2 = uv2xy2z sẽ chứa a, b, c với số lượng không bằng nhau ⇒ w2 ∉ L (><). Trang 275 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bài tập „ Ngôn ngữ nào sau đây PNC? Chứng minh. „ L1 = {anbjck: k = jn} „ L2 = {anbjck: k > n, k > j} „ L3 = {anbjck: n < j, n ≤ k ≤ j} „ L5 = { anbjanbj: n ≥ 0, j ≥ 0} „ L4 = {w: na(w) < nb(w) < nc(w)} „ L6 = { anbjakbl: n + j ≤ k + l} „ L7 = { anbjakbl: n ≤ k, j ≤ l} „ L8 = {anbncj: n ≤ j} Trang 276 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bổ đề bơm cho ngôn ngữ tuyến tính „ Định nghĩa 8.1 „ Một NNPNC L được gọi là tuyến tính nếu ∃ một VPPNC tuyến tính G sao cho L = L(G). „ Định lý 8.2 „ Cho L là một NN tuyến tính vô hạn, tồn tại một số nguyên dương m sao cho bất kỳ chuỗi w nào ∈ L với |w| ≥ m, w có thể được phân hoạch thành w = uvxyz với |uvyz| ≤ m (8.7) và |vy| ≥ 1 (8.8) sao cho uvixyiz ∈ L (8.9) ∀ i = 0, 1, 2, ... Trang 277 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chứng minh „ Gọi G là văn phạm tuyến tính mà không chứa luật sinh-đơn vị và luật sinh-λ. „ Gọi k = max {các chiều dài vế phải} ⇒ mỗi bước dẫn xuất chiều dài dạng câu tăng tối đa (k-1) kí hiệu ⇒ một chuỗi w dẫn xuất dài p bước thì |w| ≤ 1 + p(k-1) (1). „ Đặt |V|= n. Chọn m = 2 + n(k-1). Xét w bất kỳ ∈ L, |w|≥ m. (1)⇒ dẫn xuất của w có ≥ (n+1) bước ⇒ dẫn xuất có ≥ (n+1) dạng câu mà không phải là câu. Chú ý mỗi dạng câu có đúng một biến. „ Xét (n+1) dạng câu đầu tiên của dẫn xuất trên ⇒ ∃ hai biến của hai dạng câu nào đó trùng nhau, giả sử là biến A. Như vậy dẫn xuất của w phải có dạng: S uAz uvAyz uvxyz, (2) với u, v, x, y, z ∈ T*. *⇒ *⇒ *⇒ Trang 278 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chứng minh (tt) „ Xét dẫn xuất riêng phần S uAz uvAyz vì A được lặp lại trong (n + 1) dạng câu đầu tiên nên dãy này có≤ n bước dẫn xuất ⇒ |uvAyz|≤ 1 + n(k-1), ⇒ |uvyz|≤ n(k-1) < m. Mặt khác vì G không có luật sinh-đơn vị và luật sinh-λ nên ta có |vy|≥1. „ Từ (2) cũng suy ra: S uAz uvAyz uviAyiz uvixyiz ⇒ uvixyiz ∈ L ∀ i = 0, 1, 2, ... „ Chứng minh hoàn tất. *⇒*⇒ *⇒ *⇒ *⇒ *⇒ Trang 279 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ „ Chứng minh ngôn ngữ L = {w: na(w) = nb(w)} là không tuyến tính. „ Chứng minh „ Giả sử L là tuyến tính. Chọn w = amb2mam. Từ (8.7) ⇒ u, v, y, z phải chứa toàn a. Nếu bơm chuỗi này lên, chúng ta nhận được chuỗi am+kb2mam+l, với k ≥ 1 hoặc l ≥ 1, mà chuỗi này ∉ L (><) ⇒ L không phải là ngôn ngữ tuyến tính. Trang 280 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bài tập „ Ngôn ngữ nào sau đây PNC tuyến tính? Chứng minh. „ L1 = {anbnambm: n, m ≥ 0} „ L2 = { w: na(w) ≥ nb(w)} „ L3 = {anbj: j ≤ n ≤ 2j - 1} „ L4 = L(G) với G được cho như sau: E→ T | E + T T→ F | T * F F→ I | (E) I→ a | b | c Trang 281 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Tính đóng của NNPNC „ Định lý 8.3 „ Họ NNPNC là đóng dưới phép hội, kết nối, và bao đóng sao. „ Chứng minh „ Giả sử G1 = (V1, T1, S1, P1), G2 = (V2,