آلات الحالة المحدودة

نظرة عامة سريعة على ماهية آلات الدولة ، مع أمثلة بسيطة

هناك الكثير من الحديث عنآلات الحالة المحدودةهذه الأيام في أرض جافا سكريبت.

هناك مكتبة شعبية تسمىXState، مع أكثر من 11000 نجمة على GitHub ، والتي صادفتها مؤخرًا ، وأواصل القراءة عنها على Twitter وأماكن أخرى. إنه مشروع رائع جدًا.

لقد قابلت لأول مرة شركة Finite State Machines و Automata في المدرسة الثانوية ، منذ 20 عامًا ، ثم قابلتهم مرة أخرى في دورة التصميم الرقمي في الجامعة.

كانت دورة التصميم الرقمي هذه حول ترميز المعلومات والجبر المنطقي والشبكات التوافقية والدوائر المتسلسلة وآلات الحالة المتسلسلة والدوائر الحسابية و VHDL والمزيد.

لقد وجدت موضوع Finite State Machines المطبق على Frontend Engineering مدهشًا للغاية ، وعدت إلى كتبي القديمة لمعرفة ما إذا كان بإمكاني العثور على شرح جيد لها.

لقد وجدت الكثير من المعلومات ، وبالطبع أصبحت الأشياء أكثر تعقيدًا من الحاجة إلى الكتب المدرسية (IMHO). أحب أن أبسط الأمور ، وقررت أن أكتب شرحًا بسيطًا للبشر العاديين ، لا نظريًا أو أي شيء تم إجراؤه لاجتياز اختبار. أشياء يمكنك تطبيقها على العالم الحقيقي.

آلات الدولة

قبل النظر في ماهية آلة الدولة المحدودة ، أود أولاً أن أقدم ما هي آلة الدولة.

العالم مليء بآلات الدولة. يمكنك رؤيتهم في كل مكان ، لكن ربما لم تفكر فيهم على هذا النحو. بعد قراءة هذا البرنامج التعليمي ، أنا متأكد من أنك ستشير إلى أشياء في العالم الحقيقي تقول لأصدقائك "هذا هوآلة الدولة"(اعتمادًا على المستوى المهووس لأصدقائك).

المثال الأكثر شيوعًا والأكثر شيوعًا هوإشارات المرور.

في أي وقت ، يكون لإشارة المرور حالة محددة. عادة ، إما:

  • الضوء الأخضر مضاء ، والآخران مطفأان
  • الضوء الأحمر مضاء والأضواء الأخرى مطفأة
  • كالمصباح الأصفر مضاء والأضواء الأخرى

Traffic lights

(بعض الإشارات تختلف قليلاً ، لكننا لا نهتم من أجل هذا المثال)

في مصطلحات State Machines ، يتم استدعاء الأضواء التي يتم تشغيلها أو إيقاف تشغيلهاانتاج.

يتم استدعاء كل من هذه السيناريوهات الثلاثةحالة. ستتغير إشارة المرور حالتها عندما تتلقى إدخالًا ، وعادةً ما يكون مجرد مؤقت ثابت يقرر مقدار الوقت الذي يجب أن تكون فيه إشارات المرور خضراء وصفراء وحمراء.

الموقت في هذه الحالة هوإدخالالنظام. تحتوي بعض الإشارات على زر يمكن للمشاة الضغط عليه لإظهار اللون الأحمر للسيارات ، وسيكون ذلك بمثابة إدخال آخر.

في آلة الدولة ، لا يمكن للدولة إلا أن تتغير (ولدينا ملفانتقال) ردا على أحد المدخلات.

آلات الحالة المحدودة

يقال إن آلة حالة إشارات المرور الخاصة بنامحدودلأن لدينا عددًا محدودًا من الدول.

قد تحتوي بعض الأنظمة على عدد لا حصر له من الحالات.

مثل نموذج النظام البيئي العالمي ، أو حياة حشرة. لا يمكننا تحديده في عدد محدود من الحالات.

لكن إشارات المرور؟ هذا شيء بسيط ، وله 3 حالات ، كما قلنا أعلاه.

هناك العديد من الأمثلة على آلات الحالة المحدودة التي يمكننا استخدامها:

  • آلة بيع
  • باب دوار مدخل المترو
  • نظام تدفئة
  • نظام مترو أنفاق آلي
  • نظام سيارة ذاتية القيادة
  • مصعد

لكن دعنا نلتزم بمثال إشارات المرور ، وهو بسيط للغاية ويمكننا التفكير فيه بسهولة.

نمذجة آلة الدولة

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

Crossroads

لا تفكر في ذلك الآن. دعونا نركز على إشارة مرور واحدة.

كما قلنا أعلاه ، لدينا 3 حالات ، والتي يمكن أن تسمي الأخضر والأحمر والأصفر.

The 3 states

لدينا حالة أولية. لنفترض أن إشارات المرور الخاصة بنا تبدأ ، عندما نعيد ضبطها ، عندgreenحالة.

Initial state

لدينا مؤقت بعد 50 ثانية من الحالة الخضراء ، ينقل الإشارة إلى ملفyellowحالة. لدينا 8 ثوان منyellowالدولة ، ثم ننتقل إلىredالدولة ، ونجلس هناك لمدة 32 ثانية ، لأن هذا الطريق ثانوي ويستحق وقتًا أقل من اللون الأخضر. بعد ذلك ، تعود الإشارة إلى الحالة الخضراء وتستمر الدورة إلى أجل غير مسمى ، حتى تتوقف الكهرباء ويعاد ضبط السيمافور عندما تحصل على الطاقة مرة أخرى.

في المجموع ، لدينا دورة 90 ثانية.

هذه هي الطريقة التي يمكننا بها نمذجتها:

The model

يمكننا أيضًا تصميمه باستخدام ملفالجدول الانتقالي للدولة، مما يدل علىحالةالجهاز موجود حاليًا ، ما هو ملفإدخاليتلقى ، ما هوالدولة التالية، و الانتاج:

حالة إدخال الحالة التالية انتاج |
لون أخضر عداد الوقت 50 ثانية أصفر الضوء الأخضر مضاء ، والبعض الآخر مغلق
أصفر الموقت 8s أحمر الضوء الأصفر مضاء ، والبعض الآخر مطفأ
أحمر الموقت 32 ثانية لون أخضر الضوء الأحمر مضاء ، والبعض الآخر مطفأ

في حالتنا البسيطة ، بالنظر إلى أي حالة للآلة ، لدينا حالة منطقية واحدة ننتقل إليها ، لذا فإن الجدول والرسم البياني اللذين صنعتهما بسيطان للغاية.

ولكن عندما يبدأ نظامك في التعقيد ، فمن المفيد جدًا أن يكون لديك مثل هذه المخططات والتحليلات لأنك تستطيع التفكير في تطبيقك أسهل بكثير من مجرد الاحتفاظ بكل شيء في رأسك.

آلة حالة محدودة مع انتقالات حالة أكثر تعقيدًا

المثال أعلاه بسيط للغاية. لنقم بتصميم آلة دولة محدودة أخرى الآن.

سيناريو عالمنا الحقيقي هو: لدينا منزل بباب واحد وزرين و 3 مصابيح.

في الحالة الافتراضية ، يتم إطفاء جميع الأضواء.

lights

عندما تدخل المنزل ، يمكنك الضغط على أحد زري الضغط اللذين لديك ،p1أوp2. عندما تضغط على أي من هذه الأزرار ، فإن ملفl1يضيء الضوء.

تخيل أن هذا هو ضوء المدخل ، ويمكنك خلع سترتك. بمجرد الانتهاء ، عليك أن تقرر الغرفة التي تريد الدخول إليها (المطبخ أو غرفة النوم ، على سبيل المثال).

إذا ضغطت على الزرp1وl1ينطفئ وl2يشغل. بدلا من ذلك إذا ضغطت على الزرp2وl1ينطفئ وl3يشغل.

الضغط مرة أخرى على أي من الزرين ،p1أوp2، سوف ينطفئ الضوء الموجود حاليًا ، وسنعود إلى الحالة الأولية للنظام

تعتبر آلة الحالة المحدودة هذه أكثر تعقيدًا قليلاً من الأولى ، لأنه في هذه المرة يمكن أن يكون لدينا مسارات متعددة اعتمادًا على المدخلات.

دعونا نمذجة هذا.

لدينا أساسًا 4 حالات:

  • لم يتم تشغيل أي أضواء
  • l1تشغيل
  • l2تشغيل
  • l3تشغيل

model lights

لدينا مدخلين:

  • p1
  • p2

إذا بدأنا من الحالة الأولية ، وحاولنا تصميم كل ما يمكن أن يحدث اعتمادًا على كيفية تشغيل المدخلات بمرور الوقت ، فسننتهي بـ:

State transitions

والتي يمكن تلخيصها باستخدام هذا الجدول:

حالة إدخال الحالة التالية
لم يتم تشغيل أي أضواء p1ضغط l1تشغيل
لم يتم تشغيل أي أضواء p2ضغط l1تشغيل
l1تشغيل p1ضغط l2تشغيل
l1تشغيل p2ضغط l3تشغيل
l2تشغيل p1ضغط لم يتم تشغيل أي أضواء
l2تشغيل p2ضغط لم يتم تشغيل أي أضواء
l3تشغيل p1ضغط لم يتم تشغيل أي أضواء
l3تشغيل p2ضغط لم يتم تشغيل أي أضواء

هذا شرح قصير وبسيط ، لكنه ربما يجعل الأمور "تنقر".


المزيد من دروس الكمبيوتر: