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

Xây máy Turing cho ngôn ngữ L = {WW^R | W ∈ {0,1}}. Chuỗi w và nghịch đảo w^R. Ví dụ: w=10110, w^R=01101, chuỗi chấp nhận: 1011001101.

Phương pháp

1. Kiểm tra ký tự đầu: 0→thay bằng Y, 1→thay bằng X
2. Di chuyển đến cuối chuỗi, ký tự cuối phải khớp (0→Y, 1→X)
3. Quay về vị trí sau ký tự đã thay ở đầu, lặp lại
4. Mỗi lần thay cặp ký tự đối xứng từ 2 đầu
5. Vì w và w^R cùng độ dài, luôn thay cặp nth từ đầu và nth từ cuối

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

Giải thích trạng thái

• q0: trạng thái bắt đầu, đọc ký tự đầu, đánh dấu X/Y, chuyển sang q1
• q1: di chuyển phải qua 0,1,X,Y đến cuối
• q2: tại cuối, kiểm tra khớp, đánh dấu, chuyển sang q3
• q3: di chuyển trái quay về vị trí tiếp theo
• q4: kiểm tra hoàn tất, nếu chỉ còn X/Y → chấp nhận