การออกแบบคอมไพเลอร์ - Finite Automata
ไฟไนต์ออโตมาตาเป็นเครื่องสถานะที่รับสตริงของสัญลักษณ์เป็นอินพุตและเปลี่ยนสถานะตามนั้น Finite automata เป็นเครื่องมือจดจำสำหรับนิพจน์ทั่วไป เมื่อสตริงนิพจน์ทั่วไปถูกป้อนเข้าใน จำกัด ออโตมาตาสตริงจะเปลี่ยนสถานะสำหรับลิเทอรัลแต่ละตัว หากสตริงอินพุตได้รับการประมวลผลสำเร็จและออโตมาตาถึงสถานะสุดท้ายจะได้รับการยอมรับกล่าวคือสตริงที่เพิ่งป้อนถูกกล่าวว่าเป็นโทเค็นที่ถูกต้องของภาษาในมือ
แบบจำลองทางคณิตศาสตร์ของออโตมาตา จำกัด ประกอบด้วย:
- ชุดสถานะ จำกัด (Q)
- ชุดสัญลักษณ์อินพุต จำกัด (Σ)
- หนึ่งสถานะเริ่มต้น (q0)
- ชุดของสถานะสุดท้าย (qf)
- ฟังก์ชั่นการเปลี่ยน (δ)
ฟังก์ชันการเปลี่ยน (δ) แมปชุดสถานะ จำกัด (Q) กับชุดสัญลักษณ์อินพุต จำกัด (Σ), Q ×Σ➔ Q
การก่อสร้าง Finite Automata
ให้ L (r) เป็นภาษาปกติที่รู้จักโดย จำกัด Automata (FA)
States: สถานะของ FA แสดงด้วยวงกลม ชื่อรัฐเขียนอยู่ในวงกลม
Start state: สถานะจากจุดเริ่มต้นของออโตมาตะเรียกว่าสถานะเริ่มต้น สถานะเริ่มต้นมีลูกศรชี้ไปทางนั้น
Intermediate states: สถานะกลางทั้งหมดมีลูกศรอย่างน้อยสองลูก คนหนึ่งชี้ไปที่และอีกคนหนึ่งชี้ออกจากพวกเขา
Final state: หากแยกวิเคราะห์สตริงอินพุตสำเร็จออโตมาตาคาดว่าจะอยู่ในสถานะนี้ สถานะสุดท้ายแสดงด้วยวงกลมสองวง มันอาจมีลูกศรจำนวนคี่ชี้ไปที่มันและจำนวนลูกศรที่ชี้ออกจากมัน จำนวนลูกศรคี่มีค่ามากกว่าหนึ่งคู่กล่าวคือodd = even+1.
Transition: การเปลี่ยนจากสถานะหนึ่งไปเป็นอีกสถานะหนึ่งจะเกิดขึ้นเมื่อพบสัญลักษณ์ที่ต้องการในอินพุต เมื่อมีการเปลี่ยนแปลงออโตมาตะสามารถย้ายไปยังสถานะถัดไปหรืออยู่ในสถานะเดิม การเคลื่อนที่จากสถานะหนึ่งไปยังอีกสถานะหนึ่งจะแสดงเป็นลูกศรกำกับโดยลูกศรจะชี้ไปยังสถานะปลายทาง หากออโตมาตะยังคงอยู่ในสถานะเดิมลูกศรที่ชี้จากสถานะถึงตัวมันเองจะถูกดึงออกมา
Example: เราถือว่า FA ยอมรับค่าไบนารีสามหลักที่ลงท้ายด้วยหลัก 1 FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}
