مخطط الحالة

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

توفر مخططات الحالة وصفًا مجردًا لسلوك النظام . يُحلل هذا السلوك ويُمثل بسلسلة من الأحداث التي يمكن أن تحدث في حالة واحدة أو أكثر. وبالتالي، "يمثل كل مخطط عادةً كائنات من فئة واحدة ويتتبع الحالات المختلفة لهذه الكائنات عبر النظام". ^{[ 1 ]}

يمكن استخدام مخططات الحالة لتمثيل آلات الحالة المحدودة (وتُسمى أيضًا الأوتوماتا المحدودة) بيانيًا. وقد قدّم كلود شانون ووارن ويفر هذا المفهوم في كتابهما " النظرية الرياضية للاتصال" الصادر عام ١٩٤٩. كما ورد ذكره في كتاب تايلور بوث " الآلات التسلسلية ونظرية الأوتوماتا" الصادر عام ١٩٦٧. ومن التمثيلات الممكنة الأخرى جدول انتقال الحالة .

الشكل الكلاسيكي لمخطط الحالة للآلة المحدودة (FA) هو رسم بياني موجه يحتوي على العناصر التالية (Q، Σ، Z، δ، q ₀ ، F): ^{[ 2 ] [ 3 ]}

• الرؤوس Q : مجموعة محدودة من الحالات، يتم تمثيلها عادةً بدوائر ويتم تسميتها برموز تعريف فريدة أو كلمات مكتوبة بداخلها
• رموز الإدخال Σ : مجموعة محدودة من رموز الإدخال أو المعرفات
• رموز الإخراج Z : مجموعة محدودة من رموز الإخراج أو المعرفات

تمثل دالة الإخراج ω عملية ربط الأزواج المرتبة من رموز الإدخال والحالات برموز الإخراج، ويشار إليها رياضياً باسم ω  : Σ × Q → Z.

• تمثل الحواف δ الانتقالات من حالة إلى أخرى نتيجةً للمدخلات (المحددة برموزها المرسومة على الحواف). عادةً ما يُرسم الحافة كسهم يشير من الحالة الحالية إلى الحالة التالية. يصف هذا الربط انتقال الحالة الناتج عن المدخلات. يُكتب هذا رياضيًا على النحو التالي: δ  : Q × Σ → Q ، لذا فإن δ (دالة الانتقال) في تعريف الآلة المحدودة تُعطى بواسطة كلٍ من زوج الرؤوس المتصلة بحافة والرمز الموجود على الحافة في الرسم التخطيطي الذي يمثل هذه الآلة. يشير البند δ(q, a) = p في تعريف الآلة المحدودة إلى أنه من الحالة المسماة q تحت رمز الإدخال a ، يحدث الانتقال إلى الحالة p في هذه الآلة. في الرسم التخطيطي الذي يمثل هذه الآلة المحدودة، يُمثل هذا الانتقال بحافة تحمل علامة تشير من الرأس المسمى q إلى الرأس المسمى p .
• الحالة الابتدائية q ₀ : (غير موضحة في الأمثلة أدناه). عادةً ما تُمثَّل الحالة الابتدائية q ₀ ∈ Q بسهمٍ بلا نقطة بداية يشير إلى الحالة. في النصوص القديمة، ^{[ 2 ] [ 4 ]،} لا تُوضَّح الحالة الابتدائية ويجب استنتاجها من النص.
• حالة (حالات) القبول F : عند استخدامها، على سبيل المثال في آلات القبول، فإن F ∈ Q هي حالة القبول . وعادةً ما تُرسم على شكل دائرة مزدوجة. أحيانًا تعمل حالة (حالات) القبول كحالات " نهائية " (حالات توقف، حالات محاصرة). ^{[ 3 ]}

في آلات الحالة المحدودة الحتمية (DFA)، وآلات الحالة المحدودة غير الحتمية (NFA)، وآلات الحالة المحدودة غير الحتمية المعممة (GNFA)، وآلات مور ، يُشار إلى المدخلات على كل حافة. ​​أما في آلات ميلي ، فيُشار إلى المدخلات والمخرجات على كل حافة، مفصولة بشرطة مائلة "/": "1/0" يُشير إلى تغيير الحالة عند مصادفة الرمز "1"، مما يؤدي إلى إخراج الرمز "0". في آلات مور، عادةً ما تُكتب مخرجات الحالة داخل دائرة الحالة، مفصولة أيضًا عن مُعرّف الحالة بشرطة مائلة "/". توجد أيضًا صيغ مختلفة تجمع بين هاتين الطريقتين.

على سبيل المثال، إذا كانت حالة ما تحتوي على عدد من المخرجات (مثل "أ = محرك عكس اتجاه عقارب الساعة = 1، ب = ضوء تحذير غير نشط = 0")، فيجب أن يعكس الرسم التخطيطي ذلك  : على سبيل المثال، يشير "q5/1,0" إلى الحالة q5 بمخرجات أ = 1، ب = 0. سيتم كتابة هذا المعرف داخل دائرة الحالة.

تكتسب مخططات حالة هاريل، ^{[ 5 ]} التي ابتكرها عالم الحاسوب ديفيد هاريل ، استخدامًا واسع النطاق منذ أن أصبح أحد أشكالها جزءًا من لغة النمذجة الموحدة (UML). يسمح هذا النوع من المخططات بنمذجة الحالات الفائقة والمناطق المتعامدة والأنشطة كجزء من حالة واحدة.

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

تتوفر مجموعات أخرى من الدلالات لتمثيل مخططات الحالة. على سبيل المثال، توجد أدوات لنمذجة وتصميم منطق وحدات التحكم المدمجة. ^{[ 6 ]} تدعم هذه المخططات، مثل آلات الحالة الأصلية لهاريل، ^{[ 7 ]} الحالات المتداخلة هرميًا، والمناطق المتعامدة، وإجراءات الحالة، وإجراءات الانتقال. ^{[ 8 ]}

كثيرًا ما يخلط المبتدئون في مجال نماذج آلات الحالة بين مخططات الحالة ومخططات التدفق . يوضح الشكل أدناه مقارنة بين مخطط الحالة ومخطط التدفق. تقوم آلة الحالة (اللوحة (أ)) بتنفيذ إجراءات استجابةً لأحداث محددة. في المقابل، ينتقل مخطط التدفق (اللوحة (ب)) تلقائيًا من عقدة إلى أخرى عند اكتمال الأنشطة. ^{[ 9 ]}

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

بتفصيلٍ أكثر، يُمثّل مُدرج الشيفرة المصدرية رسمًا بيانيًا للبرنامج. وينتج عن تنفيذ هذا الرسم البياني (تحليله وتفسيره) رسم بياني للحالات. لذا، يُنتج كل رسم بياني للبرنامج رسمًا بيانيًا للحالات. وتُسمى عملية تحويل الرسم البياني للبرنامج إلى رسم بياني الحالات المرتبط به "فكّ" الرسم البياني للبرنامج.

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

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

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

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

الانتقال الذاتي هو انتقال تكون فيه الحالة الأولية والنهائية متطابقتين.

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

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

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

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

تتيح إضافة أخرى دمج مخططات التدفق ضمن مخططات حالة Harel. تدعم هذه الإضافة تطوير البرامج التي تعتمد على الأحداث وسير العمل على حد سواء.

• ديفيد هاريل
• دراكون
• SCXML هي لغة XML توفر بيئة تنفيذ عامة قائمة على آلة الحالة تعتمد على مخططات حالة هاريل.
• آلة الحالة UML
• YAKINDU Statechart Tools هو برنامج لنمذجة مخططات الحالة (مخططات حالة هاريل، وآلات ميلي، وآلات مور)، والمحاكاة، وتوليد التعليمات البرمجية المصدرية.

• statecharts.online: برنامج تعليمي شامل وتفاعلي حول مخططات الحالة وآلات الحالة
• مقدمة إلى مخططات آلة الحالة UML 2 بقلم سكوت دبليو. أمبلر
• إرشادات رسم مخططات آلة الحالة UML 2 بقلم سكوت دبليو. أمبلر
• Intelliwizard - UML StateWizard - إطار عمل وأداة نمذجة/تطوير ديناميكي UML متوقفة عن العمل، وكانت تعمل في بيئات التطوير المتكاملة الشائعة بموجب ترخيص مفتوح المصدر.
• أدوات YAKINDU Statechart - أداة مفتوحة المصدر لتحديد وتطوير الأنظمة التفاعلية القائمة على الأحداث بمساعدة آلات الحالة .
• فهم واستخدام آلات الحالة: محاضرات تقنية حول آلات الحالة في MATLAB
• FSM: توليد آلة الحالة المحدودة مفتوحة المصدر بلغة جافا من تأليف ألكسندر ساخاروف FSM
• scxmlcc: مترجم فعال لآلة حالة scxml إلى لغة C++.
• SMC: مُجمِّع آلات الحالة مفتوح المصدر، يُولِّد آلات الحالة المحدودة للعديد من اللغات مثل C، وPython، وLua، وScala، وPHP، وJava، وVB، وغيرها. SMC