- אוטומטים סופיים משמשים לזיהוי תבניות.
- הוא לוקח את מחרוזת הסמל כקלט ומשנה את מצבה בהתאם. כאשר הסמל הרצוי נמצא, אז המעבר מתרחש.
- בזמן המעבר, האוטומטים יכולים לעבור למצב הבא או להישאר באותו מצב.
- לאוטומטים סופיים יש שני מצבים, קבל מדינה אוֹ מצב דחייה . כאשר מחרוזת הקלט מעובדת בהצלחה, והאוטומטים הגיעו למצבו הסופי, הוא יקבל.
הגדרה פורמלית של FA
אוטומט סופי הוא אוסף של 5-טופל (Q, ∑, δ, q0, F), כאשר:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
דגם אוטומט סופי:
אוטומט סופי יכול להיות מיוצג על ידי קלטת קלט ושליטה סופית.
קלטת קלט: זהו סרט ליניארי בעל מספר תאים. כל סמל קלט ממוקם בכל תא.
שליטה סופית: הבקרה הסופי מחליטה את המצב הבא על קבלת קלט מסוים מקלטת קלט. קורא הקלטות קורא את התאים אחד אחד משמאל לימין, ובכל פעם נקרא סמל קלט אחד בלבד.
סוגי אוטומטיות:
ישנם שני סוגים של אוטומטים סופיים:
- DFA (אוטומט סופי דטרמיניסטי)
- NFA (אוטומטים סופיים לא דטרמיניסטיים)
1. DFA
DFA מתייחס לאוטומטים סופיים דטרמיניסטיים. דטרמיניסטי מתייחס לייחודיות של החישוב. ב-DFA, המכשיר עובר למצב אחד רק עבור תו קלט מסוים. DFA אינו מקבל את המהלך האפס.
2. NFA
NFA מייצג אוטומטים סופיים לא דטרמיניסטיים. הוא משמש לשידור כל מספר של מצבים עבור קלט מסוים. זה יכול לקבל את המהלך האפס.
כמה נקודות חשובות לגבי DFA ו-NFA:
- כל DFA הוא NFA, אבל NFA הוא לא DFA.
- יכולים להיות מספר מצבים סופיים גם ב-NFA וגם ב-DFA.
- DFA משמש בניתוח לקסיקלי בקומפיילר.
- NFA הוא יותר מושג תיאורטי.