Turing Machine − อุปกรณ์ยอมรับคำในภาษาที่สร้างโดย grammar ประเภท 0 (Type-0) TM เป็นโมเดลทางคณิตศาสตร์ประกอบด้วยเทปยาวไม่สิ้นสุดแบ่งเป็นเซลล์ ให้อินพุต มีหัวอ่าน (head) อ่านเทป ลงทะเบียนสถานะ (state register) เก็บสถานะ TM หลังอ่านสัญลักษณ์ จะแทนที่ด้วยสัญลักษณ์อื่น เปลี่ยนสถานะภายใน และเคลื่อนที่ซ้าย/ขวา 1 เซลล์ หากถึง final state คำถูกยอมรับ มิฉะนั้นปฏิเสธ
TM อธิบายอย่างเป็นทางการเป็น 7-tuple (Q, X, Σ, δ, q₀, B, F) โดย:
- Q: ชุดสถานะจำกัด
- X: อัลฟาเบทบนเทป
- Σ: อัลฟาเบทอินพุต
- δ: ฟังก์ชันการเปลี่ยนสถานะ δ: Q × X → Q × X × {Left, Right}
- q₀: สถานะเริ่มต้น
- B: สัญลักษณ์ว่าง
- F: ชุดสถานะสิ้นสุด
เป้าหมาย: สร้าง TM ที่ยอมรับภาษา L = aⁿbᵐa⁽ⁿ⁺ᵐ⁾ โดย n,m ≥ 1
ตัวอย่างคำที่ TM ยอมรับ:
- abaa (n=1,m=1)
- aabaaa (n=2,m=1)
- abbaaa (n=1,m=2)
- aaabaaaa (n=3,m=1)
คือ a ซ้ำ n ตามด้วย b ซ้ำ m ตามด้วย a ซ้ำ n+m ครั้ง อีกครั้ง n,m ≥ 1
จำนวน a น้อยที่สุดคือ 3 (n=m=1) และ b น้อยที่สุดคือ 1
แนวคิด: เครื่องจักรก่อนยอมรับ a ทั้ง n ตัว ตามด้วย b ทั้ง m ตัว เมื่อเจอ a เพิ่มเติม เริ่มลบ b และ a ที่อ่านมาแล้ว จนกว่าจะไม่มี a ใหม่ และหัวอ่านกลับถึงตัวแรก หมายถึงประมวลผลถูกต้อง
รายละเอียดการเปลี่ยนสถานะ (Transitions) แบ่งตาม state q0, q1, q2, q3, q4, qf พร้อมตัวอย่างการทำงานสำหรับสตริง "aabaaa" แสดงในเนื้อหาเดิม
ตัวอย่างการทำงาน
Input: aabaaa q0: aabaaa → q1: xabaaa → q1: xabaaa → q2: xabaaa → q3: xabzaa → q2: xazzaa q2: xazzaa → q3: xazzza → q3: xazzza → q3: xazzza → q2: xzzzzza → q2: xzzzzza q2: xzzzzza → q2: xzzzzza → q2: xzzzzza → q2: xzzzzza → q2: xzzzzzz → q3: xzzzzzz... q3: xzzzzzz → q3: xzzzzzz → q4: zzzzzzz → q4: zzzzzzz... q4: xzzzzzz$ → qf: xzzzzzz$ ถึง qf หมายถึง aabaaa ถูกยอมรับ
