สร้าง Turing Machine สำหรับภาษา L = {wwr | w ∈ {0, 1}}

คำอธิบายปัญหา

ที่นี่เราจะดูวิธีสร้าง Turing machine สำหรับภาษา L = {WW^r |W belongs to {0, 1}} ดังนี้แสดงถึงภาษาประเภทหนึ่งที่เราจะใช้ตัวอักษรแค่สองตัวคือ 0 และ 1 w คือสตริง และ w^r คือสตริงกลับ (reverse) ของมัน เช่นถ้า w = 10110 แล้ว w^r จะเป็น 01101 ดังนั้น Turing machine จะยอมรับสตริง z = 1011001101

เพื่อแก้ปัญหานี้ เราจะใช้วิธีการนี้: ตรวจสอบสัญลักษณ์แรก ถ้าเป็น 0 ให้แทนที่ด้วย y และถ้าเป็น 1 ให้แทนที่ด้วย x จากนั้นไปที่ปลายสตริง สัญลักษณ์สุดท้ายจะเหมือนกับตัวแรก เราแทนที่มันด้วย x หรือ y ตามลำดับ หลังจากนั้นกลับมาที่ตำแหน่งถัดจากสัญลักษณ์ที่แทนที่จากจุดเริ่มต้น และทำซ้ำกระบวนการเดียวกันที่กล่าวมาข้างต้น เราต้องจำไว้ว่า เนื่องจาก w^r เป็นกลับของ w ทั้งคู่จะมีจำนวนสัญลักษณ์เท่ากัน ทุกครั้งที่แทนที่สัญลักษณ์ลำดับที่ n จากต้นทาง ให้แทนที่สัญลักษณ์ลำดับที่ n จากปลายทางด้วย

State Transition Diagram