เครื่องทัวริง − เครื่องทัวริงเป็นอุปกรณ์ที่ใช้รับคำในภาษาที่สร้างโดยไวยากรณ์ประเภท 0 เครื่องจักรทัวริง (TM) เป็นแบบจำลองทางคณิตศาสตร์ซึ่งประกอบด้วยเทปความยาวอนันต์ที่แบ่งออกเป็นเซลล์ซึ่งให้อินพุต ประกอบด้วยหัวที่อ่านเทปอินพุต ทะเบียนของรัฐเก็บสถานะของเครื่องทัวริง หลังจากอ่านสัญลักษณ์อินพุต สัญลักษณ์จะถูกแทนที่ด้วยสัญลักษณ์อื่น สถานะภายในของสัญลักษณ์นั้นเปลี่ยนไป และย้ายจากเซลล์หนึ่งไปทางขวาหรือซ้าย หาก TM ถึงสถานะสุดท้าย สตริงอินพุตจะได้รับการยอมรับ มิฉะนั้น จะถูกปฏิเสธ
TM สามารถอธิบายอย่างเป็นทางการว่าเป็น 7-tuple (Q, X, Σ, δ, q0, B, F) โดยที่ −
- Q คือชุดของสถานะที่มีขอบเขตจำกัด
- X คือตัวอักษรเทป
- Σ คือตัวอักษรที่ป้อน
- δ เป็นฟังก์ชันการเปลี่ยนแปลง δ :Q × X → Q × X × {Left_shift, Right_shift}.
- q0 คือสถานะเริ่มต้น
- B คือสัญลักษณ์ว่าง
- F คือเซตของสถานะสุดท้าย
เป้าหมายของเราคือการสร้างเครื่องทัวริง TM ซึ่งยอมรับภาษา
L=anbma(n+m) โดยที่ n,m>=1
เรามาดูตัวอย่างคำศัพท์ที่ TM ยอมรับได้
- บ้า, n=1,m=1
- aaaaa, n=2,m=1
- abbaaa, n=1,m=2
- aaaaaaa, n=3,m=1
นั่นคือ n คูณ a ตามด้วย m คูณ b ตามด้วย n+m คูณ a อีกครั้ง น,m>=1
น้อยที่สุดไม่มี ของ a จะเป็น 3 เสมอ และ b เป็น 1 เสมอ เมื่อทั้งคู่ n=m=1
แนวทางสรุปได้ดังนี้ -
เครื่องแรกยอมรับทั้งหมด n no. ของ a ตามด้วย m no ทั้งหมด ของข. จากนั้นเมื่อพบ a มากขึ้น มันจะเริ่มลบอินพุต b และ a ก่อนหน้า ในท้ายที่สุดเมื่อไม่มี a ใหม่เข้ามาและส่วนหัวไปถึงอักขระป้อนแรก หมายความว่าอักขระทั้งหมดได้รับการประมวลผลอย่างถูกต้อง ให้เราทำตามขั้นตอนทีละขั้นตอนสำหรับสตริงอินพุต -
การเปลี่ยนจากสถานะ q0
-
δ (q0, a) → ( q1, x, R ). ที่สถานะ q0 หากการอ่านอักขระเป็นการส่งไปยังสถานะ q1 ให้เปลี่ยนเป็น x และเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง
ตัวอย่าง − aabaa → xabaa ( อักขระตัวแรกกลายเป็น x หัว ย้ายไปที่ a ถัดไป )
-
δ ( q0, b ) → ( q3, x, R ). ที่สถานะ q0 หากการอ่านอักขระเป็นการส่งไปยังสถานะ q3 ให้เปลี่ยนเป็น x และเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง
อดีต − babaaa…. → ซ่าาาา…. (อักขระตัวแรกกลายเป็น x หัว ย้ายไปข้าง a )
ในที่นี้ x ใช้แทนอักขระตัวแรก
การเปลี่ยนจากสถานะ q1
-
δ ( q1, a ) → ( q1, a, R ). ที่สถานะ q1 หากการอ่านอักขระเป็น a แล้วยังคงอยู่ที่สถานะ q1 และเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง
ตัวอย่าง:xaabaa… → xaabaa… (สำหรับการพักผ่อน ไม่ได้ทำอะไรและเดินไปทางขวา)
-
δ ( q1, b ) → ( q2, b, R ). ที่สถานะ q1 หากการอ่านอักขระเป็น b ให้คงอยู่ที่สถานะ q1 และเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง
Ex − xaabaa… → xaabaa… (สำหรับส่วนที่เหลือ b จะไม่ทำอะไรเลยแล้วเดินไปทางขวา)
การเปลี่ยนแปลงจากสถานะ q2
-
δ ( q2, b ) → ( q2, b, R ). ที่สถานะ q2 หากการอ่านอักขระเป็น b ให้คงอยู่ที่สถานะ q2 และเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง
Ex − xaabbbaaa… → xaabbbaaa… (สำหรับการพักผ่อน b จะไม่ทำอะไรเลยแล้วเดินไปทางขวา )
-
δ ( q2, z ) → ( q2, z, R ). ที่สถานะ q2 หากการอ่านอักขระเป็น z ให้คงอยู่ที่สถานะ q2 และเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง
Ex − xaabaazz… → xaabaazz… ( สำหรับการพักผ่อน z จะไม่ทำอะไรเลยและไปทางขวา )
-
δ ( q2, a ) → ( q3, z, L ). ที่สถานะ q2 หากการอ่านอักขระเป็น a ให้เปลี่ยนเป็น z จากนั้นเปลี่ยนเป็นสถานะ q3 แล้วเลื่อนไปทางซ้ายเพื่อชี้อักขระก่อนหน้าในสตริง
Ex − xaabaazz… → xaabazzz… ( สำหรับ a แทนที่ด้วย z แล้วเลื่อนไปทางซ้าย )
การเปลี่ยนจากสถานะ q3
-
δ ( q3, z ) → ( q3, z, L ). ที่สถานะ q3 หากการอ่านอักขระเป็น z ให้คงอยู่ที่สถานะ q3 และเลื่อนไปทางซ้ายเพื่อชี้อักขระก่อนหน้าในสตริง
Ex − xaabzzzz… → xaabzzzzzz… ( สำหรับ z ไม่ได้ทำอะไรและขยับไปทางซ้าย )
-
δ ( q3, b ) → ( q2, z, R ). ที่สถานะ q2 หากการอ่านอักขระเป็น b ให้เปลี่ยนเป็น z และขนส่งที่ stateq2 แล้วเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง แทนที่ b's ทั้งหมด
ตัวอย่าง − xaabzzzz… → xaazzzzzz… ( สำหรับ b แทนที่ด้วย z แล้วเลื่อนไปทางขวา )
-
δ ( q3, a ) → ( q2, z, R ). ที่สถานะ q2 หากการอ่านอักขระเป็น a ให้เปลี่ยนเป็น z และส่งต่อไปยัง stateq3 แล้วเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง แทนที่ a ทั้งหมด
Ex − xaazzzz… → xaazzzz… ( สำหรับ a ให้แทนที่ด้วย z แล้วเลื่อนไปทางขวา )
-
δ ( q3, x ) → ( q4, z, R ). ที่สถานะ q2 หากการอ่านอักขระเป็น x ทำให้เป็น z จากนั้นเปลี่ยนเป็นสถานะ q3 และเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง ถึงสัญลักษณ์แรกแล้ว
ตัวอย่าง − xzzzzzzz… → zzzzzzzz… ( สำหรับ x แทนที่ z แล้วเลื่อนไปทางขวา )
การเปลี่ยนจากสถานะ q4
-
δ ( q4, z ) → ( q4 z, R ). ที่สถานะ q4 หากการอ่านอักขระเป็น z ให้คงอยู่ที่สถานะ q4 และเลื่อนไปทางขวาเพื่อชี้อักขระถัดไปในสตริง อักขระทั้งหมดเป็น z แล้ว
ตัวอย่าง − zzzzzzzz… → zzzzzzzz… (สำหรับ z ทั้งหมดแล้วไม่ทำอะไรเลยและไปทางขวา)
-
δ ( q4, $ ) → ( qf, $ , R ) ที่สถานะ q4 หากไม่มีอักขระเหลืออยู่ ถึงจุดสิ้นสุด การขนส่งไปยังสถานะสุดท้าย qf ซึ่งหมายความว่ายอมรับสตริงแล้ว
ตัวอย่าง − zzzzzzzz$ → zzzzzzzz ( สำหรับการสิ้นสุดสตริง $ ไม่ทำอะไรเลยและย้ายไปยังสถานะสุดท้าย )
แผนภาพแสดงเครื่องทัวริง -
อินพุต
aabaaaq0:aabaaa → q1:xabaaa → q1:xabaaa → q2:xabaaa → q3:xabzaa → q2:xazzaaq2:xazzaaq2:xazzaa → q3:xazzza → q3:xazzza → q3:xazzaax → zzza2 x:zzz:zz → q2:xzzzzza → q2:xzzzzza → q2:xzzzzzz → q3:xzzzzzz……..q3:xzzzzzz → q3:xzzzzzz → q4:zzzzzzzz → q4:zzzzzzz…….q4:xzz zzzz$ → q$:zzzzzz>ถึง qf หมายถึงยอมรับแล้ว
