Máy Turing − Máy Turing là thiết bị dùng để chấp nhận các từ của ngôn ngữ được tạo bởi ngữ pháp loại 0. Máy Turing (TM) là một mô hình toán học bao gồm một dải vô hạn chia thành ô mà trên đó đầu vào được đưa. Nó bao gồm một đầu đọc đọc dải đầu vào. Thanh ghi trạng thái lưu trạng thái của máy Turing. Sau khi đọc một ký hiệu đầu vào, nó được thay thế bằng ký hiệu khác, trạng thái nội bộ thay đổi, và nó di chuyển từ ô này sang ô bên phải hoặc trái. Nếu TM đạt trạng thái cuối, chuỗi đầu vào được chấp nhận, ngược lại bị từ chối.
Một TM có thể được mô tả chính thức như một 7-tuple (Q, X, Σ, δ, q0, B, F) trong đó:
- Q là tập hữu hạn các trạng thái
- X là bảng chữ cái dải
- Σ là bảng chữ cái đầu vào
- δ là hàm chuyển trạng thái; δ: Q × X → Q × X × {Left_shift, Right_shift}.
- q0 là trạng thái ban đầu
- B là ký hiệu trống
- F là tập các trạng thái cuối
Mục tiêu của chúng ta là xây dựng một máy Turing TM chấp nhận ngôn ngữ:
L = a^n b^m a^(n+m) với n,m ≥ 1
Hãy lấy ví dụ các từ TM có thể chấp nhận:
- abaa, n=1,m=1
- aabaaa, n=2,m=1
- abbaaa, n=1,m=2
- aaabaaaa, n=3,m=1
Tức là n lần a theo sau m lần b theo sau n+m lần a nữa. n,m ≥ 1.
Số lượng a nhỏ nhất luôn là 3 và b là 1. Khi cả n=m=1.
Phương pháp tóm tắt như sau:
Máy đầu tiên chấp nhận tất cả n ký tự a theo sau tất cả m ký tự b. Sau đó khi gặp thêm các ký tự a, nó bắt đầu xóa các ký tự b và a trước đó. Cuối cùng khi không còn ký tự a mới đến và đầu đọc đến ký tự đầu vào đầu tiên, nghĩa là tất cả ký tự đã được xử lý đúng. Hãy theo dõi từng bước cho chuỗi đầu vào:
Chuyển trạng thái từ q0
- δ(q0, a) → (q1, x, R). Tại trạng thái q0 nếu ký tự đọc là a thì chuyển sang trạng thái q1, biến thành x và di chuyển phải sang ký tự tiếp theo trong chuỗi. Ví dụ: aabaaa → xabaaa (ký tự đầu tiên thành x, đầu đọc dịch phải sang a tiếp theo).
- δ(q0, b) → (q3, x, R). Tại trạng thái q0 nếu ký tự đọc là b thì chuyển sang trạng thái q3, biến thành x và di chuyển phải. Ví dụ: babaaa... → xabaaa... (ký tự đầu tiên thành x, đầu đọc dịch phải sang a tiếp theo).
Ở đây x dùng để biểu diễn ký tự đầu tiên.
Chuyển trạng thái từ q1
- δ(q1, a) → (q1, a, R). Tại q1 nếu đọc a thì ở lại q1, di chuyển phải sang ký tự tiếp theo. Ví dụ: xaabaaa... → xaabaaa... (với các a còn lại không làm gì và dịch phải).
- δ(q1, b) → (q2, b, R). Tại q1 nếu đọc b thì ở lại q1, dịch phải sang ký tự tiếp theo. Ví dụ: xaabaaa... → xaabaaa... (với các b còn lại không làm gì và dịch phải).
Chuyển trạng thái từ q2
- δ(q2, b) → (q2, b, R). Tại q2 nếu đọc b thì ở lại q2, dịch phải. Ví dụ: xaabbbaaa... → xaabbbaaa... (với các b còn lại không làm gì và dịch phải).
- δ(q2, z) → (q2, z, R). Tại q2 nếu đọc z thì ở lại q2, dịch phải. Ví dụ: xaabaazz... → xaabaazz... (với các z còn lại không làm gì và dịch phải).
- δ(q2, a) → (q3, z, L). Tại q2 nếu đọc a, biến thành z rồi chuyển sang q3, dịch trái sang ký tự trước. Ví dụ: xaabaazz... → xaabazzz... (với a thay bằng z và dịch trái).
Chuyển trạng thái từ q3
- δ(q3, z) → (q3, z, L). Tại q3 nếu đọc z thì ở lại q3, dịch trái. Ví dụ: xaabzzzz... → xaabzzzzz... (với z không làm gì và dịch trái).
- δ(q3, b) → (q2, z, R). Tại q2 nếu đọc b thì biến thành z và chuyển sang q2, dịch phải. Thay thế tất cả b. Ví dụ: xaabzzzz... → xaazzzzz... (với b thay bằng z và dịch phải).
- δ(q3, a) → (q2, z, R). Tại q2 nếu đọc a thì biến thành z và chuyển sang q3, dịch phải. Thay thế tất cả a. Ví dụ: xaazzzz... → xaazzzzz... (với a thay bằng z và dịch phải).
- δ(q3, x) → (q4, z, R). Tại q2 nếu đọc x biến thành z rồi chuyển sang q3, dịch phải. Ký hiệu đầu tiên được đạt đến. Ví dụ: xzzzzzzz... → zzzzzzzz... (với x thay bằng z và dịch phải).
Chuyển trạng thái từ q4
- δ(q4, z) → (q4, z, R). Tại q4 nếu đọc z thì ở lại q4, dịch phải. Tất cả ký tự là z. Ví dụ: zzzzzzzz... → zzzzzzzz... (với tất cả z không làm gì và dịch phải).
- δ(q4, $) → (qf, $, R). Tại q4 nếu không còn ký tự, đạt cuối. Chuyển sang trạng thái cuối qf. Nghĩa là chuỗi được chấp nhận. Ví dụ: zzzzzzzz$ → zzzzzzzz (với cuối chuỗi $ không làm gì và chuyển trạng thái cuối).
Sơ đồ máy Turing:
Ví dụ chạy
Đầu vào
aabaaa q0: aabaaa → q1: xabaaa → q1: xabaaa → q2: xabaaa → q3: xabzaa → q2: xazzaa q2: xazzaa → q3: xazzza → q3: xazzza → q3: xazzza → q2: xzzzzza → q2: xzzzzza q2: xzzzzza → q2: xzzzzza → q2: xzzzzza → q2: xzzzzzz → q3: xzzzzzz...... q3: xzzzzzz → q3: xzzzzzz → q4: zzzzzzz → q4: zzzzzzz...... q4: xzzzzzz$ → qf: xzzzzzz$
Đạt qf nghĩa là aabaaa được chấp nhận.