Ở đây chúng ta sẽ xem cách tạo một máy Turing cho ngôn ngữ L ={0n1n2n | n ≥ n}. 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ự 0s, 1s và 2s. W là một chuỗi. Vì vậy, nếu w =000111222, 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 cách tiếp cận này. Đầu tiên thay một số 0 từ phía trước bằng x, sau đó tiếp tục di chuyển sang phải cho đến khi chúng ta nhận được một số 1 và thay thế số 1 này bằng y. Một lần nữa, tiếp tục di chuyển sang phải cho đến khi chúng ta nhận được một 2, thay thế nó bằng z và di chuyển sang trái. Bây giờ tiếp tục di chuyển sang trái cho đến khi chúng ta sẽ tìm thấy một dấu x. Khi chúng ta nhận được nó, hãy di chuyển sang phải, sau đó thực hiện theo quy trình tương tự như trên.
Một điều kiện xuất hiện khi chúng ta tìm thấy một x ngay sau đó là một y. Tại thời điểm này, chúng tôi tiếp tục đi đúng và tiếp tục kiểm tra xem tất cả các số 1 và 2 đã được chuyển đổi thành y và z hay chưa. Nếu không, thì chuỗi không được chấp nhận. Nếu chúng tôi đạt đến $ thì chuỗi được chấp nhận.
Sơ đồ chuyển đổi trạng thái
