- מכונת מצב סופי משמשת לזיהוי תבניות.
- מכונה אוטומטית סופית לוקחת את מחרוזת הסמל כקלט ומשנה את מצבה בהתאם. בקלט, כאשר נמצא סמל רצוי אז המעבר מתרחש.
- בזמן המעבר, האוטומטים יכולים לעבור למצב הבא או להישאר באותו מצב.
- ל-FA יש שני מצבים: קבלת מדינה או מצב דחה. כאשר מחרוזת הקלט מעובדת בהצלחה והאוטומטים הגיעו למצבו הסופי אז הוא יקבל.
אוטומט סופי מורכב מהבאים:
ש: קבוצה סופית של מצבים
∑: קבוצה סופית של סמל קלט
q0: מצב התחלתי
F: מצב סופי
ד: פונקציית מעבר
ניתן להגדיר את פונקציית המעבר כ
δ: Q x ∑ →Q
FA מאופיין בשתי דרכים:
- DFA (אוטומט סופי)
- NDFA (אוטומטים סופיים לא דטרמיניסטיים)
DFA
DFA ראשי תיבות של Deterministic Finite Automata. דטרמיניסטי מתייחס לייחודיות של החישוב. ב-DFA, תו הקלט עובר למצב אחד בלבד. DFA אינו מקבל את המהלך האפס שפירושו שה-DFA אינו יכול לשנות מצב ללא תו קלט כלשהו.
ל-DFA יש חמישה טופלים {Q, ∑, q0, F, δ}
ש: קבוצה של כל המדינות∑: קבוצה סופית של סמל קלט כאשר δ: Q x ∑ →Q
q0: מצב התחלתי
F: מצב סופי
ד: פונקציית מעבר
דוגמא
ראה דוגמה לאוטומטים סופיים דטרמיניסטיים:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 
NDFA
NDFA מתייחס ל-Non Deterministic Finite Automata. הוא משמש להעברת כל מספר מצבים עבור קלט מסוים. NDFA מקבל את המהלך NULL כלומר הוא יכול לשנות מצב מבלי לקרוא את הסמלים.
ל-NDFA יש גם חמש מדינות זהות ל-DFA. אבל ל-NDFA יש פונקציית מעבר שונה.
ניתן להגדיר את פונקציית המעבר של NDFA כ:
d: Q x ∑ →2שדוגמא
ראה דוגמה לאוטומטים סופיים לא דטרמיניסטיים:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 