Phrase-Structure Grammars
المكونات الأربعة $G=(V, T, S, P)$
- $V$ (Vocabulary): المجموعة الكلية للرموز (المتغيرات + النهائية).
- $T$ (Terminals): الرموز النهائية التي لا يمكن استبدالها (حروف صغيرة، أرقام).
- $S$ (Start Symbol): رمز البداية (من $V$).
- $P$ (Productions): قواعد الاستبدال. شكلها: $\alpha \to \beta$.
القواعد: $S \to 0S1, S \to \lambda$
Language $L(G) = \{0^n 1^n \mid n \ge 0\}$
Types of Grammars
| Type | Name | Rule Constraints ($\alpha \to \beta$) | Machine |
|---|---|---|---|
| Type 0 | Unrestricted | No constraints | Turing Machine |
| Type 1 | Context-Sensitive | $|\alpha| \le |\beta|$ (No shrinking) | Linear Bounded |
| Type 2 | Context-Free | $\alpha = A$ (Single Non-terminal) | Pushdown Automata |
| Type 3 | Regular | $A \to aB$ or $A \to a$ | Finite Automata |
Finite-State Machines
FSM with Output (Mealy)
آلة تنتج مخرجات بناءً على الانتقال.
$M = (S, I, O, f, g, s_0)$
- $f$: Transition function (State $\times$ Input $\to$ State).
- $g$: Output function (State $\times$ Input $\to$ Output).
FSM without Output (DFA)
آلة للقبول أو الرفض فقط (Language Recognition).
$M = (S, I, f, s_0, F)$
- $F$: مجموعة الحالات النهائية (Final States).
- تقبل الكلمة إذا انتهت في حالة $s \in F$.
Regular Grammar Constraint
في القواعد المنتظمة (Type 3)، يجب أن يكون الرمز المتغير (Non-terminal) في الطرف الأيمن دائماً في أقصى اليمين (Right-Linear) أو أقصى اليسار.
مثال صحيح: $A \to 0B$.
مثال خطأ (Context-Free): $A \to 0B1$ (المتغير في الوسط أو محاط برموز).
Language of a Grammar $L(G)$
هي مجموعة كل السلاسل المكونة من رموز نهائية فقط (Terminals) التي يمكن اشتقاقها من رمز البداية $S$.
أي سلسلة تحتوي على متغير (Variable) ليست في اللغة بعد.