אוטומט סופי דטרמיניסטי (DFA)

הגדרה פורמלית

DFA הוא חמישייה M = (Q, Σ, δ, q₀, F):

• Q – קבוצה סופית של מצבים.
• Σ – אלפבית הקלט (קבוצה סופית של סימנים).
• δ : Q × Σ → Q – פונקציית המעברים. פונקציה מוגדרת במלואה: לכל זוג (מצב, סימן) יש בדיוק מצב יעד אחד.
• q₀ ∈ Q – מצב התחלתי.
• F ⊆ Q – קבוצת המצבים המקבלים.

המילה "דטרמיניסטי" באה מכך ש־δ היא פונקציה: אין שום בחירה במהלך הריצה.

איך DFA קורא קלט?

1. מתחילים במצב q₀.
2. לכל אות a בקלט (משמאל לימין): המצב הנוכחי q הופך ל־δ(q, a).
3. בסוף הקלט – אם המצב הנוכחי שייך ל־F, המילה מתקבלת. אחרת – נדחית.

השפה של האוטומט היא קבוצת כל המילים שהוא מקבל: L(M) = { w ∈ Σ* | δ*(q₀, w) ∈ F }.

דוגמה: מילים שמסתיימות ב־b

נבנה DFA מעל Σ = {a, b} שמקבל בדיוק את המילים שמסתיימות ב־b.

הרעיון: המצב "זוכר" מה הייתה האות האחרונה.

→ סימן למצב התחלתי, * סימן למצב מקבל

דוגמת ריצה

על המילה abba: q₀ →ᵃ q₀ →ᵇ q₁ →ᵇ q₁ →ᵃ q₀. q₀ אינו מקבל ⇒ נדחה.

על המילה aab: q₀ →ᵃ q₀ →ᵃ q₀ →ᵇ q₁. q₁ מקבל ⇒ התקבל.

טיפים לבניית DFA

• נסחו את המידע ש"המצב צריך לזכור" אחרי קריאת תחילית. כל ערך כזה הופך למצב נפרד.
• וודאו ש־δ מוגדרת על כל זוג (מצב, אות) – אחרת זה לא DFA.
• אם השפה תלויה ב"אורך mod k", נדרשים בדיוק k מצבים.
• שרטטו תמיד דיאגרמה לפני שמנסים לכתוב טבלה – זה חוסך טעויות.

DFA ושפות רגולריות

משפט יסוד: שפה היא רגולרית אם ורק אם קיים DFA שמזהה אותה. לכן כל מה שניתן לבטא בביטוי רגולרי – ניתן לבנות עבורו DFA, ולהפך.

אם נסיון לבנות DFA דורש "אינסוף מצבים כדי לזכור" משהו – זה רמז שהשפה אינה רגולרית, ויש להוכיח זאת באמצעות למת הניפוח.