What is a PDA؟
المعادلة البسيطة:
الـ Finite Automata العادية ليس لديها ذاكرة (تنسى ما قرأته).
الـ PDA يضيف مكدس (Stack) يمكنه تخزين كمية لا نهائية من المعلومات، لكن بطريقة LIFO (Last In, First Out).
يقرأ المدخل، ويغير حالته، ويقوم بعملية Push/Pop في المكدس.
Formal Definition (7-Tuple)
يعرف الـ PDA بـ 7 عناصر $(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$:
- Q: مجموعة الحالات (States).
- $\Sigma$: أبجدية المدخلات (Input Alphabet).
- $\Gamma$: أبجدية المكدس (Stack Alphabet). (جديد!)
- $q_0$: حالة البداية.
- $Z_0$: رمز قاع المكدس (Initial Stack Symbol).
- $F$: الحالات النهائية (Final States).
- $\delta$: دالة الانتقال (Transition Function).
(Current State, Input Symbol, Top of Stack) $\to$ (Next State, New String on Stack)
Acceptance Modes
متى نقول أن الـ PDA "قبلت" الكلمة؟ هناك طريقتان:
1. By Final State
مثل الـ DFA العادي. تقبل الكلمة إذا انتهت القراءة والآلة في حالة نهائية ($q \in F$).
حالة المكدس لا تهم هنا.
2. By Empty Stack
تقبل الكلمة إذا انتهت القراءة وأصبح المكدس فارغاً تماماً ($\epsilon$).
الحالة النهائية لا تهم هنا.
DPDA vs NPDA
حقيقة صادمة!
في عالم الـ Finite Automata، كان $DFA = NFA$.
ولكن في عالم الـ Pushdown Automata:
الـ Non-deterministic PDA أقوى من الـ Deterministic.
هناك لغات (مثل الباليندروم $ww^R$) يقبلها الـ NPDA ولا يقبلها الـ DPDA.
الـ DPDA: هو المستخدم في تصميم المترجمات (Compilers/Parsers) لأنه سريع ويمكن التنبؤ به.
الـ NPDA: هو النموذج النظري للـ CFG.
Equivalence Theorem
كل Context-Free Grammar (CFG) له PDA يكافئه.
وكل PDA له CFG يكافئه.
إذن: اللغات التي يقبلها الـ PDA هي بالضبط اللغات الخالية من السياق (CFLs).
شروط الـ Deterministic PDA
- لكل مدخل، يوجد انتقال واحد على الأكثر.
- إذا كان هناك انتقال $\epsilon$ (بدون مدخل)، يجب ألا يكون هناك أي انتقال آخر لنفس الحالة ونفس رمز المكدس.