Finite Automaton ที่มุ่งมั่น

Finite Automaton สามารถแบ่งออกเป็นสองประเภท -

• กำหนด Finite Automaton (DFA)
• Finite Automaton แบบไม่กำหนด (NDFA / NFA)

กำหนด Finite Automaton (DFA)

ใน DFA สำหรับสัญลักษณ์อินพุตแต่ละสัญลักษณ์สามารถกำหนดสถานะที่เครื่องจักรจะเคลื่อนที่ได้ ดังนั้นจึงเรียกว่าDeterministic Automaton. เนื่องจากมีสถานะจำนวน จำกัด จึงเรียกเครื่องDeterministic Finite Machine หรือ Deterministic Finite Automaton.

คำจำกัดความอย่างเป็นทางการของ DFA

DFA สามารถแสดงได้ด้วย 5-tuple (Q, ∑, δ, q ₀ , F) โดยที่ -

• Q เป็นชุดของรัฐที่ จำกัด

• ∑ เป็นชุดสัญลักษณ์ จำกัด ที่เรียกว่าตัวอักษร

• δ คือฟังก์ชันการเปลี่ยนโดยที่δ: Q × ∑ → Q

• q₀คือสถานะเริ่มต้นจากการประมวลผลอินพุตใด ๆ (q ₀ ∈ Q)

• F คือชุดของสถานะสุดท้าย / สถานะของ Q (F ⊆ Q)

การแสดงกราฟิกของ DFA

DFA แสดงด้วยกราฟที่เรียกว่า state diagram.

• จุดยอดแสดงถึงสถานะ
• ส่วนโค้งที่มีป้ายกำกับด้วยอักษรอินพุตแสดงการเปลี่ยน
• สถานะเริ่มต้นแสดงด้วยส่วนโค้งขาเข้าเดี่ยวที่ว่างเปล่า
• สถานะสุดท้ายถูกระบุด้วยวงกลมสองวง

ตัวอย่าง

ให้หุ่นยนต์ จำกัด กำหนดเป็น→

• ถาม = {a, b, c},
• ∑ = {0, 1},
• q ₀ = {a}
• F = {c} และ

ฟังก์ชันการเปลี่ยนδดังแสดงในตารางต่อไปนี้ -

สถานะปัจจุบัน	สถานะถัดไปสำหรับอินพุต 0	สถานะถัดไปสำหรับอินพุต 1
a	ก	ข
b	ค	ก
c	ข	ค

การแสดงกราฟิกจะเป็นดังนี้ -