Ở đây chúng ta sẽ xem cách tạo một máy Turing cho ngôn ngữ L ={AiBjCk | i * j =k; i, j, k ≥ 1}. Vì vậy, điều này đại diện cho một loại ngôn ngữ mà chúng ta sẽ chỉ sử dụng ba ký tự A, B và C. Chữ w là một chuỗi. Vì vậy, nếu w =AABBBBCCCCCCCC, Máy Turing sẽ chấp nhận nó.
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp này.
-
Đầu tiên thay A bằng x và di chuyển sang phải. Sau đó, bỏ qua tất cả các điểm A và di chuyển sang phải
-
Khi đầu tiếp cận đến điểm B đầu tiên, sau đó thay thế một đầu B bằng y, sau đó di chuyển sang phải bỏ qua tất cả các điểm B trung gian và tương ứng với đầu B đã thay thế bây giờ thay thế một chữ C bằng z và di chuyển sang trái.
-
Bây giờ di chuyển sang trái, bỏ qua tất cả z và B trong đường đi.
-
Khi con trỏ chạm đến y gần đây, sau đó di chuyển sang phải.
-
Nếu con trỏ đang trỏ vào B thì hãy lặp lại các bước từ 2 đến 4, ngược lại khi con trỏ hướng vào z thì di chuyển sang trái trong khi thay thế tất cả y thành B và bỏ qua tất cả A.
-
Khi con trỏ đến x gần đây nhất, hãy chuyển sang bước bên phải.
-
Nếu con trỏ vẫn đang trỏ đến A thì hãy lặp lại tất cả các bước trên, ngược lại khi đầu ở vị trí y thì di chuyển sang phải, bỏ qua tất cả y và z.
-
Khi đạt đến $ thì di chuyển sang trái. Chuỗi được chấp nhận.
Sơ đồ chuyển đổi trạng thái
