Finite Automata with Output
سابقاً، كانت الآلات (DFA/NFA) تقبل أو ترفض فقط. الآن، نريد آلات تعطينا **مخرجات** (مثل طباعة '1' أو '0').
Moore Machine
المخرجات تعتمد على الحالة (State) فقط.
- المكان: المخرج يكتب داخل الدائرة (State).
- التوقيت: يتم طباعة المخرج بمجرد دخول الحالة.
- الطول: إذا كان طول المدخل $n$، فإن طول المخرج $n+1$. (لأن حالة البداية تطبع فوراً!)
- Output = $\lambda(q)$
Mealy Machine
المخرجات تعتمد على الحالة (State) والمدخل (Input).
- المكان: المخرج يكتب على السهم (Transition) بصيغة `Input/Output`.
- التوقيت: يتم طباعة المخرج أثناء الانتقال.
- الطول: إذا كان طول المدخل $n$، فإن طول المخرج $n$.
- Output = $\lambda(q, a)$
Regular Expressions (التعابير المنتظمة)
طريقة جبرية لوصف اللغات. تستخدم 3 عمليات أساسية:
- Star (*): الأقوى.
- Concatenation (•): يليه.
- Union (+): الأضعف.
Algebraic Laws for RegEx
| Law Name | Identity | Description |
|---|---|---|
| Identity (+) | $R + \emptyset = R$ | $\emptyset$ is identity for union. |
| Identity (•) | $R \epsilon = \epsilon R = R$ | $\epsilon$ is identity for concat. |
| Annihilator | $R \emptyset = \emptyset R = \emptyset$ | $\emptyset$ destroys concatenation. |
| Idempotent | $R + R = R$ | Repeating OR does nothing. |
| Kleene Laws | $(R^*)^* = R^*$ $\emptyset^* = \epsilon$ $\epsilon^* = \epsilon$ |
Star properties. |
| Closure | $R^* = \epsilon + R R^*$ | Recursive definition. |
Moore Machine Output Length
إذا كان المدخل "101" (طوله 3)، فما طول مخرج آلة Moore؟
الجواب: 4.
السبب: Moore تطبع مخرج حالة البداية (Start State) قبل قراءة أي حرف.
Mealy: الطول 3 (نفس المدخل).
Difference between $\emptyset$ and $\epsilon$
R + $\emptyset$ = R (Identity)
R + $\epsilon$ $\neq$ R (Adds empty string)
R$\emptyset$ = $\emptyset$ (Annihilator)
R$\epsilon$ = R (Identity)
انتبه لتأثيرهما المختلف في الجمع والضرب!