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

Máy TuringPDA 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...
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 9 Chương 9 Máy TuringPDA 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ếtbị 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ôngqua 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ạnhnhấ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áymó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ằngbất kỳ quá trình tính toán nào thực hiện được bằng các máy tínhngày nay, đều có thể thực hiện được bằng máy Turing. Trang 286 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 9 Máy Turing9.1 Máy Turing chuẩn9.2 Kết hợp các máy Turing cho các công việc phức tạp9.3 Luận đề Turing Trang 287 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, Control unit − 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. − Input, Storage, Output Trang 288 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ệnhành của ôtômát và kí hiệu băng đang được đọc. Kết quả là mộttrạng thái mới của automat, một kí hiệu băng mới thay thế chokí hiệu đang được đọc trên băng và một sự di chuyển đầu đọcsang phải hoặc sang trái.Ví dụ δ(q0, a) = {q1, d, R} Trạng thái nội q0 Trạng thái nội q1 abc dbc Trang 289 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ư sauQ = {q0, q1}, Σ = {a, b}, Γ = {a, b, }, F = ∅, còn δ được địnhnghĩ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 q0 q1 q0 ab ab abTrường hợp này máy không dừng lại và rơi vào một vòng lặpvô tận (infinite loop) Trang 290 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ẩnCó 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épdi 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 đamộ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ấtkỳ 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 291 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 292 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 ...