DFA (Deterministic Finite Automata)
آلة بسيطة ذات ذاكرة محدودة جداً. تكون دائماً في حالة (State) واحدة فقط في أي لحظة.
المكونات الخمسة (5-Tuple):
- $Q$: مجموعة الحالات (States).
- $\Sigma$: الأبجدية (Input Symbols).
- $\delta$: دالة الانتقال (Transition Function).
- $q_0$: حالة البداية (Start State).
- $F$: مجموعة الحالات النهائية (Final States).
لكل مدخل، هناك انتقال واحد ومحدد (Deterministic).
NFA (Nondeterministic Finite Automata)
ما الفرق بين DFA و NFA؟
في NFA، الآلة يمكن أن تكون في عدة حالات في نفس الوقت، ويمكنها "التخمين" (Guessing).
| الخاصية | DFA | NFA |
|---|---|---|
| الانتقال (Transition) | مسار واحد فقط لكل مدخل. | صفر، واحد، أو أكثر من المسارات. |
| دالة الانتقال ($\delta$) | $Q \times \Sigma \to Q$ | $Q \times \Sigma \to P(Q)$ (مجموعة) |
| Epsilon Moves ($\epsilon$) | غير مسموح. | مسموح (انتقال بدون دخل). |
Equivalence & Applications
حقيقة هامة (Equivalence)
كل NFA له DFA مكافئ له يقبل نفس اللغة تماماً.
NFA = DFA (من حيث القدرة التعبيرية).
تطبيق عملي: البحث عن النصوص
كيف تجد كلمة "ebay" أو "web" في صفحة ويب؟
نستخدم NFA حيث كل حالة تمثل حرفاً تم مطابقته.
هذا هو أساس عمل أدوات مثل grep و Lexical Analyzers.
$\epsilon$-NFA (Epsilon Transitions)
هي قدرة الآلة على تغيير حالتها تلقائياً دون قراءة أي رمز من المدخلات (قفزة مجانية).
ECLOSE (Epsilon Closure)
هي مجموعة كل الحالات التي يمكن الوصول إليها من حالة معينة $q$ باستخدام انتقالات $\epsilon$ فقط.
* ملاحظة: الحالة نفسها دائماً جزء من الـ ECLOSE الخاص بها.
DFA vs NFA Function Range
انتبه في الاختيارات:
DFA: $\delta(q, a) = q'$ (حالة واحدة).
NFA: $\delta(q, a) = \{q_1, q_2, \dots\}$ (مجموعة من الحالات Subset of Q).
الفرق هو في المجموعة (Set).
Subset Construction
لتحويل NFA إلى DFA:
1. ابدأ بـ $q_0$ (أو ECLOSE($q_0$)).
2. لكل رمز، جد مجموعة الحالات الممكنة.
3. كل مجموعة جديدة تصبح حالة واحدة في الـ DFA.
4. أي مجموعة تحتوي على حالة نهائية من NFA تصبح نهائية في DFA.