Ở đây chúng ta sẽ xem cách tạo máy Turing cho ngôn ngữ L ={WW r | W thuộc về {0, 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 hai ký tự 0 và 1. W là một chuỗi và w r là đảo ngược của nó. Vì vậy, nếu w =10110, thì w r sẽ là 01101. Vì vậy, máy Turing sẽ chấp nhận chuỗi z =1011001101.
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng cách tiếp cận này. Trước tiên, hãy kiểm tra biểu tượng đầu tiên, nếu nó là 0 thì thay nó bằng y và nếu đó là 1 thì thay bằng x. Sau đó đi đến cuối chuỗi. Vì vậy, biểu tượng cuối cùng giống với biểu tượng đầu tiên. Chúng tôi cũng thay thế nó bằng x hoặc y tùy thuộc vào nó. Sau đó, một lần nữa quay trở lại vị trí bên cạnh biểu tượng thay thế từ đầu và lặp lại quy trình tương tự như đã đề cập ở trên. Chúng ta phải ghi nhớ rằng vì w r là đảo ngược của w cả hai sẽ có số ký hiệu bằng nhau. Mỗi khi thay thế một ký hiệu thứ n từ đầu chuỗi, hãy thay thế một ký hiệu thứ n tương ứng từ cuối.
Sơ đồ chuyển đổi trạng thái
