Bài giảng môn Lý thuyết ôtômát và NNHT - Hồ Văn Quân
Tóm tắt Bài giảng môn Lý thuyết ôtômát và NNHT - Hồ Văn Quân: ...trạng thái kết thúc nào đó của ĐTCTT tổng quát (ĐTCTTTQ). Trang 113 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Đồ thị chuyển trạng thái tổng quát ? Hình bên biểu diễn một ĐTCTTTQ. ? NN được chấp nhận bởi nó là L(a*(a + b)c*) ? Nhận xét ? ĐTCTT của một nfa bất kỳ có thể được xem là Đ...Dạng câu Chuỗi nhập aabbbba•aabbbba•Saabbbb•aSaabbbb•BSaabbb•bBS aabbbba•aabbbba•aabbbb•aaabbbb•aaabbb•ba 392 aabbb•Saabb•bSaab•bbSaab•AbSaaa•bAbS aabbb•baaabb•bbaaab•bbbaaab•bbbaaa•bbbb 66 a•aAAbS a•abbbba 4 aa•AAbSa•AbS•aAbS•S aa•bbbbaa•abbbba•aabbbba•aabbbba 1Khởi đầu S→ aAbS | bB... 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 ...
P2 ∪ {S4→ S1S2}) sẽ có L(G4) = L(G1)L(G2). Văn phạm G5 = (V1 ∪ {S5}, T1, S5, P1 ∪ {S5→ S1S5 | λ}) sẽ có L(G5) = L(G1)*. Trang 282 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Tính đóng của NNPNC (tt) ? Định lý 8.4 ? Họ NNPNC không đóng dưới phép giao và bù. ? Chứng minh ? Hai ngôn ngữ {anbncm: n, m ≥ 0} và {anbmcm: n, m ≥ 0} là phi ngữ cảnh, tuy nhiên giao của chúng là ngôn ngữ {anbncn: n ≥ 0} lại không phi ngữ cảnh, nên họ NNPNC không đóng dưới phép giao. ? Dựa vào luật Morgan suy ra họ NNPNC cũng không đóng dưới phép bù. Vì nếu đóng đối với phép bù thì dựa vào tính đóng đối với phép hội suy ra tính đóng dưới phép giao theo luật Morgan. Trang 283 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Tính đóng của NNPNC (tt) ? Định lý 8.5 ? Cho L1 là một NNPNC và L2 là một NNCQ, thì L1 ∩ L2 là phi ngữ cảnh. Chúng ta nói rằng họ NNPNC là đóng dưới phép giao chính qui. ? Chứng minh ? Cho M1 = (Q, Σ, Γ, δ1, q0, z, F1) là npda chấp nhận L1 vàM2 = (P, Σ, δ2, p0, F2) là dfa chấp nhận L2. ? Xây dựng một npda M’= (Q’, Σ, Γ, δ’, q’0, z, F’) mô phỏng hoạt động song song của M1 và M2 Q’ = Q × P, q’0 = (q0, p0), F’ = F1 × F2, ((qk, pl), x) ∈ δ’((qi, pj), a, b), ⇔ (qk, x) ∈ δ1(qi, a, b), và δ2(pj, a) = pl, Trang 284 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Tính đóng của NNPNC (tt) ? Nếu a = λ, thì pj = pl. ? Bằng qui nạp chứng minh rằng δ’*((q0, p0), w, z) |-*M’ ((qr, ps), x), với qr ∈ F1 và ps ∈ F2⇔ δ1*(q0, w, z) |-*M1 (qr, x), còn δ2*(p0, w) = ps. ? Vì vậy L(M’) = L(M1) ∩ L(M2) (điều phải chứng minh) ? Ví dụ ? Ngôn ngữ L = { w ∈ {a, b}*: na(w) = nb(w), na(w) chẵn} là phi ngữ cảnh. Trang 285 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Một vài tính chất khả quyết định của NNPNC ? Định lý 8.6 ? Cho một VPPNC G = (V, T, S, P), thì tồn tại một giải thuật để quyết định L(G) có trống hay không. ? Định lý 8.7 ? Cho một VPPNC G = (V, T, S, P), thì tồn tại một giải thuật để quyết định L(G) có vô hạn hay không. Trang 286 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 9 Máy Turing ? PDA về một mặt nào đó mạnh hơn rất nhiều FSA. ? NNPNC-PDA vẫn còn giới hạn. Bên ngoài nó là gì? ? FSA và PDA khác nhau ở bản chất của bộ lưu trữ tạm thời. ? Nếu PDA dùng hai, ba stack, một hàng (queue), hay một thiết bị lưu trữ khác nào đó thì sức mạnh sẽ thế nào? ? Mỗi thiết bị lưu trữ định nghĩa một loại ôtômát mới và thông qua nó một họ ngôn ngữ mới? ? Ôtômát có thể được mở rộng đến chừng nào? Khả năng mạnh nhất có thể của ôtômát? Những giới hạn của việc tính toán? ? Máy Turing ra đời và khái niệm về sự tính toán có tính máy móc hay giải thuật (mechanical or algorithmic computation). ? Máy Turing là khá thô sơ, nhưng đủ sức để bao trùm các quá trình rất phức tạp và luận đề Turing (Turing thesis) cho rằng bất kỳ quá trình tính toán nào thực hiện được bằng các máy tính ngày nay, đều có thể thực hiện được bằng máy Turing. Trang 287 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 9 Máy Turing 9.1 Máy Turing chuẩn 9.2 Kết hợp các máy Turing cho các công việc phức tạp 9.3 Luận đề Turing Trang 288 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Máy Turing chuẩn ? Định nghĩa 9.1 ? Một máy Turing M được định nghĩa bằng bộ bảy M = (Q, Σ, Γ, δ, q0, , F), − Q là tập hữu hạn các trạng thái nội, − Σ là tập hữu hạn các kí hiệu được gọi là bảng chữ cái ngõ nhập, − Γ là tập hữu hạn các kí hiệu được gọi là bảng chữ cái băng, − δ là hàm chuyển trạng thái, − ∈ Γ là một kí hiệu đặc biệt, gọi là khoảng trắng (blank), − q0 ∈ Q là trạng thái khởi đầu, − F ⊆ Q là tập các trạng thái kết thúc. Control unit Input, Storage, Output Trang 289 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Máy Turing chuẩn (tt) ? Trong định nghĩa chúng ta giả thiết rằng Σ ⊆ Γ - {}. ? Hàm δ được định nghĩa như sau δ: Q × Γ → Q × Γ × {L, R} ? Nó được diễn dịch như sau: Các đối số của δ là trạng thái hiện hành của ôtômát và kí hiệu băng đang được đọc. Kết quả là một trạng thái mới của automat, một kí hiệu băng mới thay thế cho kí hiệu đang được đọc trên băng và một sự di chuyển đầu đọc sang phải hoặc sang trái. ? Ví dụ δ(q0, a) = {q1, d, R} a b c d b c Trạng thái nội q0 Trạng thái nội q1 Trang 290 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ ? Xét một máy Turing được định nghĩa như sau ? Q = {q0, q1}, Σ = {a, b}, Γ = {a, b, }, F = ∅, còn δ được định nghĩa δ(q0, a) = (q1, a, R) δ(q1, a) = (q0, a, L)δ(q0, b) = (q1, b, R) δ(q1, b) = (q0, b, L)δ(q0, ) = (q1, , R) δ(q1, ) = (q0, , L) ? Xét hoạt động của M trong trường hợp sau ? Trường hợp này máy không dừng lại và rơi vào một vòng lặp vô tận (infinite loop) a b a b q0 q1 a b q0 Trang 291 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Các đặc điểm của máy Turing chuẩn ? Có nhiều mô hình khác nhau của máy Turing. ? Sau đây là một số đặc điểm của máy Turing chuẩn. ? Máy Turing có một băng không giới hạn cả hai đầu, cho phép di chuyển một số bước tùy ý về bên trái và phải. ? Máy Turing là đơn định trong ngữ cảnh là δ định nghĩa tối đa một chuyển trạng thái cho một cấu hình. ? Không có một băng nhập (input file) riêng biệt. Chúng ta giả thiết là vào thời điểm khởi đầu băng chứa một nội dung cụ thể. Một vài trong số này có thể được xem là chuỗi nhập (input). Tương tự không có một băng xuất (output file) riêng biệt. Bất kỳ khi nào máy dừng, một vài hay tất cả nội dung của băng có thể được xem là kết quả xuất (output). Trang 292 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Hình trạng tức thời ? Định nghĩa 9.2 ? Cho M = (Q, Σ, Γ, δ, q0, , F) là một máy Turing, thì một chuỗi a1a2 ... ak-1q1akak+1 ... an bất kỳ với ai ∈ Σ và q1∈ Q, là một hình trạng tức thời của M (gọi tắt là hình trạng). ? Một di chuyển a1a2 ... ak-1q1akak+1 ... an a1a2 ... ak-1bq2ak+1 ...an là có thể nếu và chỉ nếu δ( q1, ak) = (q2, b, R). ? Một di chuyển a1a2 ... ak-1q1akak+1 ... an a1a2 ... q2ak-1bak+1 ...an là có thể nếu và chỉ nếu δ( q1, ak) = (q2, b, L). _| _| Trang 293 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Hình trạng tức thời (tt) ? M được gọi là dừng sau khi bắt đầu từ một cấu hình khởi đầu nào đó x1qix2 nếu x1qix2 y1qjay2 với bất kỳ qj và a, mà đối với nó δ(qj, a) không được định nghĩa. ? Dãy cấu hình dẫn tới một trạng thái dừng sẽ được gọi là một sự tính toán (computation). ? Ví dụ trong slide 290 trình bày khả năng rằng một máy Turing có thể không bao giờ dừng, thi hành trong một vòng lặp vô tận và từ đó nó không thể thoát. ? Trường hợp này đóng một vai trò cơ bản trong thảo luận về máy Turing, và được kí hiệu là x1qx2 ∞ để chỉ ra rằng, bắt đầu từ cấu hình khởi đầu x1qx2, máy không bao giờ dừng. *_| *_| Trang 294 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Máy Turing như một bộ chấp nhận ngôn ngữ ? Định nghĩa 9.3 ? Cho M = (Q, Σ, Γ, δ, q0, , F) là một máy Turing, thì ngôn ngữ được chấp nhận bởi M là L(M) = {w ∈ Σ+: q0w x1qfx2 và dừng, đối với một qf nào đó∈ F, x1, x2 ∈ Γ*}. ? Định nghĩa này chỉ ra rằng chuỗi nhập w được viết trên băng với các khoảng trắng chặn ở hai đầu. Đây cũng là lý do các khoảng trắng bị loại ra khỏi bảng chữ cái ngõ nhập Σ. ? Điều này đảm bảo chuỗi nhập được giới hạn trong một vùng rõ ràng của băng được bao bọc hai đầu bởi các kí hiệu trắng. ? Không có qui ước này, máy không thể giới hạn vùng trong đó nó tìm kiếm chuỗi nhập. ? Định nghĩa trên không nói rõ khi nào thì w ∉ L(M). Điều này đúng khi một trong hai trường hợp sau xảy ra *_| Trang 295 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ (1) Máy dừng lại ở một trạng thái không kết thúc. (2) Máy đi vào một vòng lặp vô tận và không bao giờ dừng. ? Ví dụ ? Cho Σ = {a, b}, thiết kế máy Turing chấp nhận L = {anbn: n≥1}. ? Ý tưởng thiết kế là đọc một a thay bằng một x, đi kiếm một b thay bằng một y. Cứ như vậy cho đến khi không còn đồng thời a và b để thay thì dừng và chấp nhận chuỗi, các trường hợp khác thì không chấp nhận. Máy Turing kết quả như sau. Q = {q0, q1, q2, q3, qf }, F = {qf}, Σ = {a, b}, Γ = {a, b, x, y, }δ(q0, a) = {q1, x, R} δ(q2, y) = {q2, y, L} δ(q0, y) = {q3, y, R}δ(q1, a) = {q1, a, R} δ(q2, a) = {q2, a, L} δ(q3, y) = {q3, y, R}δ(q1, y) = {q1, y, R} δ(q2, x) = {q0, x, R} δ(q3, ) = {qf, , R}δ(q1, b) = {q2, y, L} Trang 296 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ q0aaabbb xq1aabbb xaq1abbb xaaq1bbb xaq2aybb xq2aaybb q2xaaybb xq0aaybb xxq1aybb xxaq1ybb xxayq1bb xxaq2yyb xxq2ayyb xq2xayyb xxq0ayyb xxxq1yyb xxxyq1yb xxxyyq1b xxxyyq1b xxxyq2yy xxxq2yyy xxq2xyyy xxxq0yyy xxxyq3yy xxxyyq3y xxxyyyq3 xxxyyyqf (chấp nhận) q0aaabb xq1aabb xaq1abb xaaq1bb xaq2ayb xq2aaybq2 xaayb xq0aayb xxq1ayb xxaq1yb xxayq1b xxaq2yy xxq2ayy xq2xayy xxq0ayy xxxq1yy xxxyq1y xxxyyq1 (dừng) _| _| _| _|_| _| _| _| _| _| _|_| _| _| _| _| _| _|_| _| _| _| _| _|_| _| _| _| _| _|_| _| _| _| _| _| _| _| _| _| _| _| _| Trang 297 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Máy Turing như là transducer ? Máy Turing không chỉ được quan tâm như là một bộ chấp nhận ngôn ngữ mà trong tổng quát còn cung cấp một mô hình trừu tượng đơn giản của một máy tính số. ? Vì mục đích chính của một máy tính là biến đổi input thành output, nó hoạt động như một transducer. ? Hãy thử mô hình hóa máy tính bằng cách dùng máy Turing. ? Input của một sự tính toán là tất cả các kí hiệu không trắng trên băng tại thời điểm khởi đầu. Tại kết thúc của sự tính toán, output sẽ là bất kì cái gì có trên băng. ? Vậy có thể xem một máy Turing M như là một sự hiện thực của một hàm f được định nghĩa bởi = f(w) trong đó q0w M qf với qf là một trạng thái kết thúc nào đó. ∧w *_| ∧w Trang 298 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Máy Turing như là transducer (tt) ? Định nghĩa 9.4 ? Một hàm f với miền xác định D được gọi là khả tính toán- Turing hay đơn giản là khả tính toán nếu tồn tại một máy Turing nào đó M = (Q, Σ, Γ, δ, q0, , F) sao cho q0w M qf f(w), qf ∈ F, ∀ w ∈ D. ? Ví dụ ? Cho x, y nguyên dương, thiết kế máy Turing tính x + y. ? Chúng ta đầu tiên chọn qui ước để biểu diễn số nguyên dương. ? Ta đã biết cách biểu diễn số nguyên dương bằng chuỗi nhị phân và cách cộng hai số nhị phân, tuy nhiên để ứng dụng điều đó vào trong trường hợp này thì hơi phức tạp một chút. ? Vậy để đơn giản hơn ta biểu diễn số nguyên dương x bằng chuỗi w(x) các số 1 có chiều dài bằng x. ∧w *_| Trang 299 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ví dụ ? Chúng ta cũng phải quyết định các số x và y vào lúc ban đầu được đặt như thế nào trên băng và tổng của chúng xuất hiện như thế nào lúc kết thúc sự tính toán. ? Chúng ta giả thiết rằng w(x) và w(y) được phân cách bằng một kí hiệu 0, với đầu đọc ở trên kí tự trái cùng của w(x). Sau khi tính toán, w(x + y) sẽ ở trên băng và được theo sau bởi một kí tự 0, và đầu đọc sẽ được đặt trên kí tự trái cùng của kết quả. ? Chúng ta vì vậy muốn thiết kế một máy Turing để thực hiện sự tính toán (trong đó qf là một trạng thái kết thúc) q0w(x)0w(y) qf w(x + y)0, Q = {q0, q1, q2, q3, qf,}, F = {qf}δ(q0, 1) = (q0, 1, R) δ(q0, 0) = (q1, 1, R) δ(q1, 1) = (q1, 1, R)δ(q1, ) = (q2, , L) δ(q2, 1) = (q3, 0, L) δ(q3, 1) = (q3, 1, L)δ(q3, ) = (qf, , R) *_| Trang 300 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Kết hợp các máy Turing cho các công việc phức tạp ? Chúng ta đã thấy máy Turing có thể thực hiện được các phép toán cơ bản và quan trọng những cái mà có trong tất cả các máy tính. ? Vì trong các máy tính số, các phép toán cơ bản như vậy là các thành phần cơ bản cho các lệnh phức tạp hơn, vì vậy chúng ta ở đây cũng sẽ trình bày máy Turing có khả năng kết hợp các phép toán này lại với nhau. ? Ví dụ ? Thiết kế một máy Turing tính toán hàm sau f(x, y) = x + y nếu x ≥ y = 0 nếu x < y ? Ta xây dựng mô hình tính toán cho nó như sau Trang 301 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Kết hợp các máy Turing cho các công việc phức tạp (tt) ? Chúng ta sẽ xây dựng bộ so sánh C mà sau khi thực hiện xong có kết quả như sau: qC,0w(x)0w(y) qA,0w(x)0w(y), nếu x ≥ y qC,0w(x)0w(y) qE,0w(x)0w(y), nếu x < y trong đó qC,0, qA,0 và qE,0 lần lượt là trạng thái khởi đầu của bộ so sánh, bộ cộng và bộ xóa. Bộ so sánh C Bộ cộng A Bộ xóa E x, y x + y 0 x ≥ y x < y f (x, y) *_| *_| Trang 302 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Bài tập ? Nếu chúng ta xây dựng được các bộ so sánh, bộ cộng và bộ xóa thì với mô hình kết hợp như trên chúng ta có thể xây dựng được hàm tính toán được yêu cầu. ? Xây dựng máy Turing thực hiện các phép toán sau ? Hàm f(x, y) trong slide trên ? Phép AND, OR, XOR ? Phép cộng hai số nhị phân Trang 303 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Luận đề Turing ? Máy Turing có thể được xây dựng từ các phần đơn giản hơn, tuy nhiên khá cồng kềnh cho dù phải thực hiện các phép toán đơn giản. Điều này là vì “tập lệnh” của một máy Turing là quá đơn giản và hạn chế. ? Vậy máy Turing có sức mạnh đến đâu và như thế nào trong sự so sánh với sức mạnh của máy tính ngày nay? ? Mặc dầu với cơ chế đơn giản nhưng máy Turing có thể giải quyết được các bài toán phức tạp mà máy tính ngày nay giải quyết được. ? Để chứng minh điều này người ta đã chọn ra một máy tính điển hình, sau đó xây dựng một máy Turing thực hiện được tất cả các lệnh trong tập lệnh của máy tính (tập lệnh của CPU). ? Tuy làm được điều này nhưng đó cũng chưa phải là một chứng minh chặt chẽ để chứng tỏ máy Turing có sức mạnh ngang bằng với các máy tính ngày nay. Trang 304 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Luận đề Turing (tt) ? Tuy nhiên cũng không ai đưa ra được phản chứng chứng minh rằng máy Turing không mạnh bằng với máy tính ngày nay. ? Cuối cùng, với khá nhiều bằng chứng mạnh mẽ tuy chưa đủ là một chứng minh chặt chẽ, chúng ta chấp nhận luận đề Turing sau như là một định nghĩa của một “sự tính toán cơ học” ? Luận đề Turing ? Bất kỳ cái gì có thể được thực hiện trên bất kỳ máy tính số đang tồn tại nào đều có thể được thực hiện bởi một máy Turing. ? Không ai có thể đưa ra một bài toán, có thể giải quyết được bằng những gì mà một cách trực quan chúng ta xem là một giải thuật, mà đối với nó không tồn tại máy Turing nào giải quyết được. ? Các mô hình thay thế khác có thể được đưa ra cho sự tính toán cơ học nhưng không có cái nào trong số chúng là mạnh hơn mô hình máy Turing. Trang 305 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Giải thuật ? Luận đề trên đóng một vai trò quan trọng trong khoa học máy tính cũng giống như vai trò của các định luật cơ bản trong vật lý và hóa học. ? Bằng việc chấp nhận luận đề Turing, chúng ta sẵn sàng để định nghĩa chính xác khái niệm giải thuật, cái mà là khá cơ bản trong khoa học máy tính. ? Định nghĩa 9.5 ? Một giải thuật cho một hàm f: D→ R là một máy Turing M sao cho cho một chuỗi nhập d ∈ D trên băng nhập, cuối cùng M dừng với kết quả f(d) ∈ R trên băng. Một cách cụ thể là: q0d M qf f(d), qf ∈ F, ∀ d ∈ D.*_| Trang 306 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 10 Phụ lục 10.1 Một số định nghĩa 10.2 Tổng kết các đối tượng đã học 10.3 Mối quan hệ giữa các đối tượng 10.4 Sự phân cấp các lớp ngôn ngữ hình thức theo Chomsky 10.5 Một số giải thuật quan trọng khác Trang 307 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Máy Turing không đơn định ? Định nghĩa 10.6 ? Là máy Turing mà trong đó hàm δ được định nghĩa như sau: δ: Q × Σ→ 2Q × Σ× {L, R} ? Định lý 10.5 ? Lớp máy Turing không đơn định tương đương với lớp máy Turing chuẩn. ? Định lý 10.6 ? Tập tất cả các máy Turing là vô hạn đếm được. Trang 308 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ôtômát ràng buộc tuyến tính ? Định nghĩa 10.7 ? Một ôtômát ràng buộc tuyến tính (Linear Bounded Automat - LBA) là một máy Turing không đơn định M = (Q, Σ, Γ, δ, q0, , F), như trong Định nghĩa 10.6, ngoại trừ bị giới hạn rằng Σ phải chứa hai kí tự đặc biệt [ và ], sao cho δ(qi, [) có thể chứa chỉ một phần tử dạng (qj,[, R) và δ(qi, ]) có thể chứa chỉ một phần tử dạng (qj,], L). ? Bằng lời, khi đầu đọc chạm đến dấu móc vuông ở một trong hai đầu nó phải giữ lại và đồng thời không thể vượt ra vùng nằm giữa hai dấu móc vuông. ? Trong trường hợp này chúng ta nói đầu đọc bị giới hạn giữa hai dấu móc vuông hai đầu. Trang 309 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ôtômát ràng buộc tuyến tính (tt) ? Định nghĩa 10.7 ? Một chuỗi được chấp nhận bởi một ôtômát ràng buộc tuyến tính nếu có một dãy chuyển hình trạng có thể q0[w] [x1qfx2] với một qf nào đó ∈ F, x1, x2 ∈ Σ*. Ngôn ngữ được chấp nhận bởi lba là tập tất cả các chuỗi được chấp nhận bởi lba. ? Ví dụ ? Ngôn ngữ L = {anbncn: n ≥ 0} là một ngôn ngữ ràng buộc tuyến tính vì chúng ta có thể xây dựng được một lba chấp nhận đúng nó. *_| Trang 310 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Ngôn ngữ khả liệt kê đệ qui, đệ qui ? Định nghĩa 10.8 ? Một ngôn ngữ L được gọi là khả liệt kê đệ qui nếu tồn tại một máy Turing M chấp nhận nó. ? Từ định nghĩa này cũng dễ dàng suy ra được mọi ngôn ngữ mà đối với nó tồn tại một thủ tục liệt kê (các phần tử của nó) thì khả liệt kê đệ qui. ? Định nghĩa 10.9 ? Một ngôn ngữ L trên Σ được gọi là đệ qui nếu tồn tại một máy Turing M chấp nhận nó và dừng đối với w ∈ Σ+. Hay nói cách khác một ngôn ngữ là đệ qui nếu và chỉ nếu tồn tại một giải thuật thành viên cho nó. *_| Trang 311 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Văn phạm ? Định nghĩa 10 ? Một văn phạm mà mọi luật sinh không cần thõa bất kỳ ràng buộc nào tức là có dạng α → β trong đó α ∈ (V ∪ T)*V(V ∪ T)*, β ∈ (V ∪ T)* thì được gọi là văn phạm loại 0 hay là văn phạm không hạn chế. ? Một văn phạm mà mọi luật sinh có dạng chiều dài vế trái nhỏ hơn hoặc bằng chiều dài vế phải tức là có dạng α → β trong đó α ∈ (V ∪ T)*V(V ∪ T)*, β ∈ (V ∪ T)* và |α| ≤ |β| thì được gọi là văn phạm loại 1 hay văn phạm cảm ngữ cảnh. ? Văn phạm phi ngữ cảnh còn được gọi là văn phạm loại 2. ? Văn phạm chính qui còn được gọi là văn phạm loại 3. Trang 312 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Tổng kết các lớp đối tượng LRERecusively EnumerableKhả liệt kê đệ qui LRECRecusiveĐệ qui LCSContext-SensitiveCảm ngữ cảnh LCFContext-FreePhi ngữ cảnh LDCFDeterministic Context-FreePhi ngữ cảnh đơn định LLINLinearTuyến tính LREGRegularChính qui Kí hiệuCác lớp ngôn ngữ Trang 313 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Tổng kết các lớp đối tượng (tt) GURUnRestrictedKhông hạn chế ≡ Loại 0 GCSContext-SensitiveCảm ngữ cảnh ≡ Loại 1 GCFContext-FreePhi ngữ cảnh ≡ Loại 2 GLL và GLRLL(k) và LR(k)Phi ngữ cảnh đơn định: điển hình là LL(k) và LR(k) GLINLinearTuyến tính GREG ≡ GR-LIN và GL-LIN Regular ≡ Right- Linear và Left-Linear Chính qui ≡ Tuyến tính-phải và tuyến tính-trái ≡ Loại 3 Kí hiệuCác lớp văn phạm Trang 314 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Tổng kết các lớp đối tượng (tt) TMTuring MachineMáy Turing LBALinear BoundedRàng buộc tuyến tính NPDANondeterministic Push DownĐẩy xuống không đơn định DPDADeterministic Push Down Đẩy xuống đơn định FSA (nfa, dfa)Finite StateHữu hạn Kí hiệuCác lớp ôtômát Trang 315 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Mối quan hệ giữa các lớp đối tượng ? Dấu ≡ có nghĩa là theo định nghĩa, còn dấu = có nghĩa là tương đương, dấu ⊃ có nghĩa là tập cha (không bằng), dấu ⊂ có nghĩa là tập con (không bằng). TMGURLRE ⊂ TM⊂ GURLREC LBAGCSLCS NPDAGCFLCF DPDA⊃ LL(k) và LR(k)LDCF ⊂ NPDAGLINLLIN FSA ≡ DFA = NFAGREC ≡ GL-LIN và GR-LINLREG ÔtômátVăn phạmNgôn ngữ Trang 316 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Phân cấp ngôn ngữ theo Chomsky LREG LCF LCS LRE Sơ đồ phân cấp đơn giản LREG LDCF LCF LCS LREC LRE Sơ đồ phân cấp chi tiếtLREGLLIN LCF LDCF Sơ đồ phân cấp trong lớp PNC
File đính kèm:
- bai_giang_mon_ly_thuyet_otomat_va_nnht_ho_van_quan.pdf