ما هي الآلة ذات الحالات المنتهية (Finite State Machine)؟ شرح مبسّط بأمثلة

الآلة ذات الحالات المنتهية (Finite State Machine واختصارها FSM) هي ببساطة نموذج يصف نظامًا يمكن أن يوجد في حالة واحدة فقط في كل لحظة، وينتقل من حالة إلى أخرى عندما يصله مدخل معيّن. تخيّل إشارة المرور: إما خضراء أو صفراء أو حمراء، ولا يمكن أن تكون اثنتين في آن واحد، وتنتقل بينها وفق قاعدة ثابتة. هذا بالضبط جوهر الـ FSM. ليست خوارزمية بحد ذاتها، بل طريقة تفكير ونمذجة تستخدمها لتصميم أجزاء من برامجك عندما يكون سلوك النظام محكومًا بحالات واضحة.

في مجال الخوارزميات وهياكل البيانات نلجأ إليها لأنها تجعل المنطق المعقّد قابلًا للرسم على ورقة، وقابلًا للاختبار، وأقل عرضة للأخطاء المنطقية مقارنة بسلاسل طويلة من if/else.

المكوّنات الخمسة لأي آلة حالات

أي FSM تُعرَّف رياضيًا بخمسة عناصر، ومن المفيد حفظها لأنها تظهر في أي كتاب أو سؤال مقابلة:

1. مجموعة الحالات (States): كل الأوضاع الممكنة للنظام، مثل «مغلق»، «مفتوح»، «قيد التحميل».
2. الأبجدية أو المدخلات (Inputs): الأحداث التي تحرّك النظام، مثل ضغطة زر أو وصول حرف من نص.
3. دالة الانتقال (Transition Function): القاعدة التي تقول «إذا كنت في الحالة أ ووصلني المدخل س، فانتقل إلى الحالة ب».
4. الحالة الابتدائية (Start State): نقطة البداية الوحيدة.
5. حالات القبول (Accept States): الحالات التي تعني أن المهمة انتهت بنجاح (مهمة تحديدًا عند التحقق من صحة نص).

النقطة الجوهرية التي يغفل عنها كثيرون: الكلمة «منتهية» (Finite) تعني أن عدد الحالات محدود ومعروف مسبقًا. هذا ما يميّزها عن نماذج أعقد كآلة تورينغ التي تملك ذاكرة غير محدودة.

مثال عملي: التحقق من كلمة مرور بسيطة

لنقل إننا نريد قبول أي نص يبدأ بحرف a ثم يتبعه أي عدد من حرف b. الحالات ثلاث: q0 (البداية)، q1 (رأينا a)، وqError (مدخل غير صالح). بلغة تشبه الشيفرة:

state = q0
لكل حرف c في النص:
    إذا state == q0 و c == 'a':  state = q1
    وإلا إذا state == q1 و c == 'b':  state = q1   # نبقى مكاننا
    وإلا:  state = qError
النص صالح إذا كانت state == q1

لاحظ كيف اختفت الشروط المتشعّبة وتحوّلت إلى جدول واضح. هذه هي القيمة الحقيقية للـ FSM: تفصل «ما الحالة الآن» عن «ماذا أفعل تاليًا».

DFA أم NFA؟ الفرق بينهما

عند دراسة FSM ستقابل نوعين، والخلط بينهما شائع جدًا:

المعيار	DFA (حتمية)	NFA (غير حتمية)
الانتقال من حالة بمدخل واحد	وجهة واحدة فقط	قد تتفرّع لعدة حالات
انتقالات فارغة (ε)	غير مسموحة	مسموحة
سهولة التنفيذ برمجيًا	مباشرة وسريعة	تحتاج محاكاة للمسارات
القوة التعبيرية	متساوية	متساوية

النقطة المفاجئة: النوعان متكافئان في القدرة؛ أي نص يمكن لـ NFA التعرف عليه يمكن لـ DFA أيضًا، وهناك خوارزمية معروفة لتحويل NFA إلى DFA. عمليًا نصمّم بـ NFA لأنه أسهل على الورق، ثم نحوّله إلى DFA لأنه أسرع في التنفيذ.

أين تُستخدم فعليًا؟

آلة الحالات ليست مفهومًا أكاديميًا فقط، بل تعمل خلف أدوات تستخدمها يوميًا:

• التعابير النمطية (Regular Expressions): محرّكات regex تُبنى داخليًا على آلات حالات.
• المحلّلات اللغوية (Lexers/Parsers): أول مرحلة في أي مترجم برمجي تقطّع الكود إلى رموز عبر FSM.
• بروتوكولات الشبكات: حالات اتصال TCP (مثل LISTEN، ESTABLISHED، CLOSED) هي آلة حالات صريحة.
• واجهات المستخدم والألعاب: سلوك شخصية تنتقل بين «يقف»، «يمشي»، «يهاجم» يُنمذج بـ FSM.
• أنظمة التحكم: المصاعد وأجهزة الصرّاف الآلي أمثلة كلاسيكية.

نصيحة عملية وخطأ شائع

النصيحة التي تعلّمتها من التطبيق: ارسم الآلة قبل أن تكتب سطرًا واحدًا. دائرة لكل حالة، وسهم مُعنون لكل انتقال. إذا لم تستطع رسمها، فأنت لا تفهم المشكلة بعد، والكود سيعكس هذا التشوّش.

أما الخطأ الأكثر شيوعًا فهو نسيان معالجة المدخلات غير المتوقعة. كثير من المبتدئين يعرّفون الانتقالات «الصحيحة» فقط وينسون: ماذا يحدث لو وصل مدخل لا تتوقعه في هذه الحالة؟ آلة حالات سليمة يجب أن تُعرّف سلوكًا لكل زوج (حالة، مدخل)، ولو كان هذا السلوك مجرد الانتقال إلى حالة خطأ. إهمال هذا هو مصدر معظم الثغرات في أنظمة الحالات الحقيقية.

الأسئلة الشائعة

هل الـ FSM خوارزمية أم هيكل بيانات؟ لا هذا ولا ذاك تمامًا؛ هي نموذج حسابي لوصف السلوك. لكنها تُنفَّذ عادة عبر هيكل بيانات بسيط مثل جدول انتقالات (مصفوفة أو قاموس) وتُشغَّل بخوارزمية قراءة تسلسلية للمدخلات.

ما الفرق بين آلة مور (Moore) وآلة ميلي (Mealy)؟ كلاهما FSM يُنتج مخرجات. في آلة مور يعتمد المخرَج على الحالة الحالية فقط، بينما في آلة ميلي يعتمد على الحالة والمدخل معًا، ما يجعل ميلي غالبًا أقل عددًا في الحالات.

هل يمكن لآلة الحالات المنتهية عدّ الأقواس المتوازنة؟ لا، وهذه محدوديتها الشهيرة. لأن عدد الأقواس قد يكون غير محدود بينما حالاتها محدودة، فهي لا تملك ذاكرة كافية للعدّ. هذه المهمة تحتاج نموذجًا أقوى يُسمى آلة المكدس (Pushdown Automaton).

كيف أبدأ التطبيق العملي؟ اختر مشكلة صغيرة من حياتك البرمجية (مثل التحقق من صيغة بريد إلكتروني أو إدارة حالات زر تحميل)، ارسم حالاتها، ثم نفّذها كجدول انتقالات. التكرار على أمثلة صغيرة أسرع طريق لإتقان المفهوم.