ما معنى Finite State Automaton؟ ولماذا يحيلك القاموس إلى Finite State Machine
إذا صادفت في قاموس الخوارزميات أو هياكل البيانات عبارة Finite State Automaton: see Finite State Machine، فالمقصود بسيط جدًا: المصطلحان اسمان لشيء واحد، وعبارة «see» هنا مجرد إحالة قاموسية تقول لك «ابحث عن الشرح تحت المصطلح الآخر». أي أن Finite State Automaton (FSA) وFinite State Machine (FSM) مترادفان تمامًا، ويُختصران غالبًا إلى «الآلة المنتهية» أو «آلة الحالات». لا يوجد فرق تقني بينهما، والإحالة موجودة فقط لتوحيد المدخل الذي يعتمده القاموس.
بعد أن تجاوزنا هذا الالتباس الشائع، دعنا نفهم الفكرة نفسها بشكل عملي.
ما هي الآلة المنتهية أساسًا؟
الآلة المنتهية نموذج رياضي يصف نظامًا يمكن أن يكون في حالة واحدة فقط في كل لحظة من بين عدد محدود من الحالات، وينتقل بين هذه الحالات استجابةً لمدخلات يستقبلها واحدًا تلو الآخر. كلمة «منتهية» (Finite) هي جوهر الفكرة: عدد الحالات معدود ومحدود، ولا تحتفظ الآلة بأي ذاكرة إضافية سوى «أين أنا الآن».
أبسط مثال ملموس هو بوابة المترو الدوّارة (Turnstile): لها حالتان فقط، «مقفلة» و«مفتوحة». إدخال عملة ينقلها من «مقفلة» إلى «مفتوحة»، ودفع البوابة والمرور يعيدها إلى «مقفلة». لا شيء أكثر من ذلك — وهذا بالضبط جوهر الآلة المنتهية.
مكوناتها الخمسة
أي آلة منتهية تُعرَّف رسميًا بخمسة عناصر:
- مجموعة الحالات (States): كل الأوضاع الممكنة للنظام.
- الأبجدية / المدخلات (Alphabet): الرموز أو الأحداث التي تستقبلها الآلة.
- دالة الانتقال (Transition Function): القاعدة التي تحدد: إذا كنت في الحالة س ووصل المدخل ص، فإلى أي حالة أنتقل.
- الحالة الابتدائية (Start State): نقطة البداية عند التشغيل.
- الحالات المقبولة/النهائية (Accepting States): الحالات التي إذا انتهى المدخل عندها اعتُبر «مقبولًا».
DFA أم NFA؟
عند دراسة الآلات المنتهية ستقابل نوعين رئيسيين، والفرق بينهما يربك كثيرين:
| المعيار | DFA (حتمية) | NFA (غير حتمية) |
|---|---|---|
| عدد الانتقالات لكل مدخل | مسار واحد محدد فقط | قد تتفرّع لعدة مسارات |
| انتقالات فارغة (ε) | غير مسموحة | مسموحة |
| سهولة التنفيذ برمجيًا | مباشرة وسريعة | تحتاج محاكاة للمسارات |
| القدرة التعبيرية | متساوية | متساوية |
| الحجم النموذجي | قد يكون أكبر | غالبًا أصغر وأوضح تصميمًا |
النقطة الأهم التي تغيب عن الكثيرين: DFA وNFA متكافئتان في القدرة. كل ما يمكن لـ NFA التعرّف عليه يمكن لـ DFA التعرّف عليه أيضًا؛ توجد خوارزمية معروفة اسمها بناء المجموعات (Subset Construction) تحوّل أي NFA إلى DFA مكافئة. الفرق عملي فقط: الـ NFA أسهل في التصميم والقراءة، والـ DFA أسرع في التنفيذ لأنها لا تحتاج إلى تتبّع فروع متعددة.
أين تُستخدم فعليًا؟
الآلة المنتهية ليست ترفًا نظريًا؛ أنت تستعملها كل يوم دون أن تدري:
- التعابير النمطية (Regex): محرّكات البحث عن الأنماط تُترجَم داخليًا إلى آلات منتهية.
- المُحلّلات اللغوية (Lexers): المرحلة الأولى في أي مترجم برمجي تقسّم الشِفرة إلى رموز عبر آلة منتهية.
- بروتوكولات الشبكة: حالات اتصال TCP (مثل SYN وESTABLISHED وCLOSED) هي آلة حالات فعلية.
- واجهات المستخدم وألعاب الفيديو: سلوك الشخصيات («يقف»، «يطارد»، «يهرب») يُنمذَج غالبًا كآلة حالات.
- أنظمة التحكّم والأجهزة المدمجة: الغسّالة، وإشارة المرور، وماكينة البيع كلها تطبيقات مباشرة.
تصحيح تاريخي سريع
تنسب بعض الشروحات المتداولة فكرة الآلة المنتهية إلى آلان تورينج وجون فون نيومان، وهذا غير دقيق. آلة تورينج نموذج أقوى وأشمل (لها ذاكرة شريطية لا نهائية)، وليست آلة منتهية. الجذور الحقيقية للنموذج تعود إلى ورقة مكولوخ وبيتس (1943) حول الشبكات العصبية، ثم طوّره لاحقًا مور وميلي، وأرسى رابين وسكوت أسسه الرياضية سنة 1959. معرفة هذا الفرق تجنّبك خلطًا شائعًا في الامتحانات: الآلة المنتهية ليست حاسوبًا كامل القدرة، لأنها بلا ذاكرة إضافية، ولذلك تعجز عن مهام بسيطة مثل التحقق من تطابق الأقواس المتداخلة.
الأسئلة الشائعة
هل FSA وFSM مصطلحان مختلفان فعلًا؟ لا. هما مترادفان تمامًا، وعبارة «see Finite State Machine» مجرد إحالة قاموسية إلى المدخل الذي يحمل الشرح.
ما الفرق العملي بين DFA وNFA؟ لا فرق في القدرة، بل في التصميم: الـ NFA أسهل رسمًا وقد تتفرّع، والـ DFA أسرع تنفيذًا لأن لكل مدخل مسارًا واحدًا محددًا.
لماذا تُسمّى «منتهية»؟ لأن عدد حالاتها محدود ومعدود، ولا تملك ذاكرة تتوسّع مع المدخل، بخلاف النماذج الأقوى مثل آلة تورينج.
هل يمكنني التعرّف عليها في الكود الذي أكتبه؟ نعم؛ أي منطق يعتمد على متغيّر «state» يتغيّر عبر عبارات switch أو if بناءً على أحداث واردة هو في جوهره آلة حالات، حتى لو لم تسمّها كذلك.