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