เราจะมาดูวิธีการสร้างเครื่องทัวริงสำหรับภาษา L ={0n1n2n | n ≥ n}. นี่จึงเป็นตัวแทนของภาษาประเภทหนึ่งที่เราจะใช้อักขระสามตัวเท่านั้น 0s, 1s และ 2s w เป็นสตริง ดังนั้นถ้า w =000111222 เครื่องทัวริงจะยอมรับมัน
เพื่อแก้ปัญหานี้ เราจะใช้แนวทางนี้ ก่อนอื่นให้แทนที่ 0 หนึ่งตัวจากด้านหน้าด้วย x จากนั้นให้เคลื่อนที่ไปทางขวาจนกว่าเราจะได้ 1 และแทนที่ 1 นี้ด้วย y อีกครั้ง ให้เคลื่อนที่ไปทางขวาจนกว่าเราจะได้ 2 ตัว แทนที่ด้วย z แล้วเลื่อนไปทางซ้าย ตอนนี้ให้ไปทางซ้ายจนกว่าเราจะพบ x หนึ่งตัว เมื่อได้มาแล้ว ให้ชิดขวา แล้วทำตามขั้นตอนเดิม
เงื่อนไขเกิดขึ้นเมื่อเราพบ x ตามด้วย y ทันที ณ จุดนี้ เราเคลื่อนที่ไปทางขวาและคอยตรวจสอบว่าชุดที่ 1 และ 2 ทั้งหมดถูกแปลงเป็น y และ z หรือไม่ ถ้าไม่เช่นนั้น สตริงจะไม่ได้รับการยอมรับ หากเราถึง $ ก็จะยอมรับสตริง
แผนภาพการเปลี่ยนสถานะ
