הגדרה פורמלית
NFA הוא חמישייה N = (Q, Σ, δ, q₀, F):
- Q, Σ, q₀, F – כמו ב־DFA.
- δ : Q × (Σ ∪ {ε}) → 𝒫(Q) – פונקציית המעברים מחזירה קבוצה של מצבים. ε הוא "מעבר חופשי" שלא צורך אות.
קלט w מתקבל אם קיים מסלול חוקי שמתחיל ב־q₀, צורך את כל אותיות w (עם אפשרות לאפסילון־מעברים ביניהן) ומסתיים במצב מקבל.
דוגמה: מילים שמכילות את התת־מילה "ab"
נבנה NFA מעל Σ = {a, b} שמקבל בדיוק מילים שמכילות "ab" כתת־מילה (איפשהו). הרעיון: לנחש מתי מתחיל ה־a שלפני ה־b.
שימו לב: ב־q₀, כשקוראים a, יש שתי אפשרויות – להישאר ב־q₀ או לעבור ל־q₁. זה הניחוש שמייחד NFA.
| δ | a | b |
|---|---|---|
| → q₀ | {q₀, q₁} | {q₀} |
| q₁ | ∅ | {q₂} |
| * q₂ | {q₂} | {q₂} |
אפסילון־מעברים
מעבר ε (לפעמים מסומן λ) מאפשר לעבור בין מצבים בלי לקרוא אות. שימושי במיוחד כשבונים NFA לאיחוד או לשרשור של שני NFAs קיימים – פשוט מחברים אותם במעבר ε ולא צריך לחזור על כל המבנה.
המרת NFA ל־DFA (בנייה של תת־קבוצות)
כל NFA ניתן להמיר ל־DFA שקול. הרעיון: כל מצב ב־DFA הוא תת־קבוצה של מצבי ה־NFA – הקבוצה של "כל המצבים שאני עשוי להיות בהם עכשיו".
- המצב ההתחלתי של ה־DFA הוא ε-closure(q₀) – q₀ ביחד עם כל מי שניתן להגיע אליו רק במעברי ε.
- לכל קבוצה S ולכל אות a: המעבר ב־DFA הולך לאיחוד של ε-closure(δ(s, a)) לכל s ∈ S.
- תת־קבוצה היא מקבלת ב־DFA אם היא מכילה לפחות מצב מקבל של ה־NFA.
במקרה הגרוע, n מצבי NFA הופכים ל־2ⁿ מצבי DFA. בפועל לרוב פחות בהרבה.
NFA מול DFA – מתי לבחור מי?
- NFA – נוח לבניה ידנית, קומפקטי, מתאים להמרה מביטוי רגולרי.
- DFA – מהיר ופשוט לסימולציה (O(|w|) על קלט w). לרוב בשלב ההרצה ממירים NFA ל־DFA.
שאלות נפוצות
מה קורה אם אין מעבר מוגדר עבור (q, a)?
פירוש הדבר ש־δ(q, a) = ∅. המסלול הספציפי הזה "מת", אבל אם קיים מסלול אחר ל־F, הקלט עדיין מתקבל.
למה בכלל להגדיר NFA אם הוא שקול ל־DFA?
כי לרוב הרבה יותר קל לבנות NFA קטן שמתאר את השפה, ולתת לתהליך אוטומטי להמיר אותו ל־DFA.
מה זה ε-closure?
הקבוצה של כל המצבים שניתן להגיע אליהם ממצב נתון, בלי לקרוא אף אות (רק לפי מעברי ε).