Xây máy Turing cho ngôn ngữ L = {ww | w ∈ {0,1}}

Xây máy Turing cho L = {WW | W ∈ {0,1}}. Chuỗi w lặp 2 lần. Ví dụ: w=10110 → 1011010110.

Phương pháp

1. Tìm giữa chuỗi: Chuyển 0→X, 1→Y từ trái sang phải cho đến khi hết 0,1 → đến giữa
2. Khôi phục nửa đầu: Chuyển X,Y về 0,1 ở nửa trái. Nửa phải còn X,Y
3. So khớp: Từ đầu, 0→X, đi phải tìm X ở nửa sau → xóa (Blank). 1→Y, tìm Y → xóa
4. Lặp cho đến khi nửa trái hết X,Y và nửa phải hết (Blank)
5. Nếu một nửa xong mà nửa kia còn → từ chối

Sơ đồ chuyển trạng thái