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