Turing Machines Basics
ما هي آلة تورنغ؟
هي نموذج رياضي يتكون من وحدة تحكم وشريط (Tape) لا نهائي.
تعتبر أقوى من الآلات المحدودة (FSM) لأنها تمتلك ذاكرة غير محدودة ويمكنها القراءة والكتابة والتحرك في الاتجاهين.
- $S$: مجموعة الحالات.
- $I$: الأبجدية (تحتوي الرمز الفارغ $B$).
- $f$: دالة الانتقال.
آلية العمل (Transition)
تقرأ الرمز الحالي، تكتب رمزاً جديداً مكانه، تغير حالتها، ثم تتحرك يميناً (R) أو يساراً (L).
Language Recognition
متى تقبل الآلة الكلمة؟
نقول أن الآلة $T$ تتعرف على (أو تقبل) السلسلة $x$ إذا توقفت الآلة في حالة نهائية (Final State) عند تشغيلها على $x$.
النتيجة: الكلمة مقبولة.
النتيجة: الكلمة مرفوضة.
The Chomsky Hierarchy
تصنيف اللغات والقواعد حسب قوتها والآلة التي تقبلها.
Difference between Type 1 & 2
Type 2 (CFG): اليسار يجب أن يكون متغيراً واحداً فقط (مثل $A \to aBc$).
Type 1 (CSG): اليسار قد يكون أكثر من رمز، بشرط ألا يقل الطول في اليمين (مثل $Ab \to aBc$). يسمح بالسياق.
Subset Property
Type 3 $\subset$ Type 2 $\subset$ Type 1 $\subset$ Type 0
كل لغة منتظمة هي لغة خالية من السياق، وكل خالية من السياق هي حساسة للسياق، وهكذا.