บุขิออโตมาตา
จากวิกิพีเดีย สารานุกรมเสรี
บุขิออโตมาตา (Büchi automaton) เป็นโมเดลทางคณิตศาสตร์ ตั้งชื่อตาม Julius Richard Büchi นักคณิตศาสตร์ชาวสวิส ใช้สำหรับการคำนวณซึ่งมีลักษณะเป็นอนันต์ คือการคำนวณนั้นดำเนินเรื่อยไปไม่มีสิ้นสุด การประยุกต์ใช้ของบุขิ ออโตมาตานั้น มีตัวอย่างในด้าน formal method เช่น ตรรกและการให้เหตุผลในระบบรีแอคทีฟ (reactive system) และ การตรวจสอบโมเดล (model checking)
[แก้] สัญลักษณ์
สัญลักษณ์ที่ใช้ในหัวข้อนี้:
- A : เซตจำกัด ของอักษร
- A * : เซตของคำจำกัด
- Aω : เซตของคำω (ω-words หรือ ω-sequences )
[แก้] บุขิ ออโตมาตา
บุขิออโตมาตา เป็น NFA ซึ่งมีการปรับเปลี่ยนเงื่อนไงการยอมรับ เพื่อรองรับ คำ ω. การยอมรับคำ ω ของ บุขิออโตมาตาเกิดขึ้นเมื่อ อ่านคำซึ่งอินพุตจากซ้ายไปขวาและทำการเปลี่ยนสถานะตาม ที่กำหนดโดยฟังก์ชันการเปลี่ยนสถานะ แล้วในสายลำดับการเปลี่ยนสถานะนั้น มีสถานะยอมรับเกิดขึ้นบ่อยเป็นอนันต์
เราเรียกการยอมรับคำแบบนี้ว่าการยอมรับแบบบุขิ (Büchi acceptance)
[แก้] อ้างอิง
- Wolfgang THOMAS, Automata on Infinite Objects, Handbook of theoretical computer science (vol. B): formal models and semantics, ISBN 0-444-88074-7