เราจะมาดูวิธีการสร้างเครื่องทัวริงสำหรับภาษา L ={AiBjCk | ผม * j =k; ผม, เจ, k ≥ 1}. นี่จึงเป็นตัวแทนของภาษาที่เราจะใช้อักขระ A, B และ C เพียงสามตัวเท่านั้น w คือสตริง ดังนั้นถ้า w =AABBBBCCCCCCCC เครื่องทัวริงจะยอมรับมัน
เราจะใช้วิธีนี้เพื่อแก้ปัญหานี้
-
ก่อนอื่นให้แทนที่ A ด้วย x แล้วเลื่อนไปทางขวา จากนั้นข้าม A ทั้งหมดแล้วไปทางขวา
-
เมื่อศีรษะไปถึง B ตัวแรก ให้แทนที่ B หนึ่งตัวด้วย y จากนั้นให้เลื่อนไปทางขวาโดยข้าม B ระดับกลางทั้งหมดและสอดคล้องกับ B ที่ถูกแทนที่ ตอนนี้ให้แทนที่ C หนึ่งตัวด้วย z แล้วเลื่อนไปทางซ้าย
-
ตอนนี้ให้เลื่อนไปทางซ้ายโดยข้าม z และ B ทั้งหมดไปขวางทาง
-
เมื่อตัวชี้ไปถึง y ล่าสุด ให้เลื่อนไปทางขวา
-
หากตัวชี้ชี้ไปที่ B ให้ทำซ้ำขั้นตอนที่ 2 ถึง 4 ไม่เช่นนั้นเมื่อตัวชี้ชี้ไปที่ z ให้เลื่อนไปทางซ้ายโดยแทนที่ y ทั้งหมดเป็น B และข้าม A ทั้งหมด
-
เมื่อตัวชี้มาถึง x ล่าสุด ให้เลื่อนไปทางขวา
-
หากตัวชี้ยังคงชี้ไปที่ A ให้ทำซ้ำขั้นตอนข้างต้นทั้งหมด ไม่เช่นนั้นเมื่อหัวอยู่ที่ y ให้เลื่อนไปทางขวาโดยข้าม y และ z ทั้งหมด
-
เมื่อถึง $ แล้วให้เลื่อนไปทางซ้าย สตริงเป็นที่ยอมรับ
แผนภาพการเปลี่ยนสถานะ
