👑
The Chomsky Hierarchy & Beyond
ترتيب اللغات من الأضعف (الأقل قيوداً) إلى الأقوى (الأكثر تعقيداً):
Recursively Enumerable (RE)
Accepted by TM (May Loop)
Recursive (Decidable)
Accepted by TM (Always Halts)
Context-Sensitive
Linear Bounded Automata
Context-Free (CFL)
Pushdown Automata (PDA)
Regular
Finite Automata (DFA/NFA)
📜
The Theorem Sheet (أهم النظريات)
Pumping Lemma (CFL)
لإثبات أن اللغة ليست CFL.
$z = uvwxy$
$|vx| \ge 1, |vwx| \le n$
$uv^iwx^iy \in L$
$|vx| \ge 1, |vwx| \le n$
$uv^iwx^iy \in L$
نضخ جزئين ($v$ و $x$) معاً.
Cook's Theorem
مشكلة SAT (Boolean Satisfiability) هي أول مشكلة تم إثبات أنها NP-Complete.
بداية عصر التعقيد الحسابي.
Savitch's Theorem
$NPSPACE = PSPACE$
عدم الحتمية (Nondeterminism) لا تزيد القوة في المساحة (Space)، فقط في الوقت.
🧠
Module Recaps (6 - 13)
Module 6: Pushdown Automata (PDA) ▼
- المعادلة: PDA = $\epsilon$-NFA + Stack (ذاكرة LIFO).
- القبول: إما بالوصول لحالة نهائية (Final State) أو بتفريغ المكدس (Empty Stack).
- الحتمية: $DPDA \neq NPDA$ (الـ NPDA أقوى).
Module 7: CFL Properties & CNF ▼
- CNF: كل قاعدة إما $A \to BC$ أو $A \to a$.
- الإغلاق (Closure): مغلقة تحت الاتحاد، والضرب، والنجمة. ليست مغلقة تحت التقاطع (Intersection) أو المتممة.
- CYK Algo: لفحص الانتماء في وقت $O(n^3)$.
Module 8 & 9: Turing Machines ▼
- التعريف: شريط لانهائي + رأس قراءة/كتابة + تحكم محدود.
- Extensions: تعدد الأشرطة (Multi-tape) أو عدم الحتمية (Nondeterminism) لا تزيد من قوة الآلة (فقط الكفاءة).
- Universal TM: آلة يمكنها محاكاة أي آلة أخرى (أساس البرمجة).
Module 10: Undecidability ▼
- Halting Problem: لا يوجد برنامج يحدد هل سيتوقف برنامج آخر أم لا (Undecidable).
- $L_d$: لغة القطرية (ليست RE).
- $L_u$: اللغة الشاملة (RE ولكن ليست Recursive).
Module 11 & 12: Complexity (P vs NP) ▼
- P: حل سريع. NP: تحقق سريع.
- NP-Complete: أصعب مشاكل في NP (مثل SAT, TSP).
- PSPACE: مشاكل محدودة الذاكرة (مثل QBF).