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

أنواع الأوتوماتا

في علم الحاسوب النظري ، تُعرف آلة الحالة المحدودة ( FSM ) أو آلة الحالة المحدودة ( FSA ، جمعها: آلات )، أو ببساطة آلة الحالة ، بأنها نموذج رياضي للحوسبة . ^{[ 1 ]} وهي آلة مجردة يمكن أن تكون في حالة واحدة فقط من بين عدد محدود من الحالات في أي وقت. يمكن لآلة الحالة المحدودة أن تنتقل من حالة إلى أخرى استجابةً لبعض المدخلات ؛ ويُسمى هذا الانتقال " انتقالًا" . ^{[ 2 ]} تُعرَّف آلة الحالة المحدودة بقائمة حالاتها، وحالتها الابتدائية، والمدخلات التي تُحفز كل انتقال. تنقسم آلات الحالة المحدودة إلى نوعين: آلات الحالة المحدودة الحتمية وآلات الحالة المحدودة غير الحتمية . ^{[ 3 ] [ 4 ]} يمكن إنشاء آلة حالة محدودة حتمية مكافئة لأي آلة حالة محدودة غير حتمية. ^{[ 5 ]}

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

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

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

يُعتبر جهاز البوابة الدوارة بمثابة آلة حالة، وله حالتان محتملتان: مُغلق ومفتوح . ^{[ 7 ]} هناك مدخلان يؤثران على حالته: وضع عملة معدنية في الفتحة ( عملة ) ودفع الذراع ( دفع ). في الحالة المُغلقة، لا يُؤثر دفع الذراع؛ فمهما تكرر إدخال أمر الدفع ، يبقى الجهاز في الحالة المُغلقة. أما وضع عملة معدنية - أي إدخال أمر عملة - فيُغير الحالة من مُغلقة إلى مفتوحة . في الحالة المفتوحة، لا يُؤثر وضع عملات إضافية؛ أي أن إدخال المزيد من العملات لا يُغير الحالة. أما دفع العميل للذراعين فيُعطي أمر دفع ، ويُعيد الحالة إلى مُغلقة .

يمكن تمثيل آلة الحالة الخاصة بالبوابة الدوارة بواسطة جدول انتقال الحالة ، والذي يوضح لكل حالة ممكنة، الانتقالات بينها (بناءً على المدخلات المعطاة للآلة) والمخرجات الناتجة عن كل مدخل:

الوضع الحالي	مدخل	الولاية التالية	الناتج
مغلق	عملة	مفتوح	يفتح البوابة الدوارة ليتمكن العميل من المرور.
	يدفع	مغلق	لا أحد
مفتوح	عملة	مفتوح	لا أحد
	يدفع	مغلق	عندما يمر الزبون، يتم إغلاق البوابة الدوارة.

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

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

في بعض تمثيلات آلات الحالة المحدودة، من الممكن أيضًا ربط الإجراءات بحالة معينة:

• إجراء دخول: يتم تنفيذه عند دخول الولاية، و
• إجراء الخروج: يتم تنفيذه عند الخروج من الحالة.

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

يمكن تقسيم الآلات ذات الحالة المحدودة إلى مستقبلات، ومصنفات، ومحولات، ومتسلسلات. ^{[ 12 ]}

المتقبلون

تُنتج المُستقبِلات (وتُسمى أيضًا الكاشفات أو المُعرِّفات ) مُخرجات ثنائية تُشير إلى ما إذا كان المُدخل المُستقبَل مقبولًا أم لا. كل حالة من حالات المُستقبِل إما حالة قبول أو حالة رفض . بمجرد استلام جميع المُدخلات، إذا كانت الحالة الحالية حالة قبول، يتم قبول المُدخل؛ وإلا يتم رفضه. وكقاعدة عامة، يكون المُدخل عبارة عن سلسلة من الرموز (الأحرف)؛ ولا تُستخدم الإجراءات. يُمكن أن تكون حالة البداية أيضًا حالة قبول، وفي هذه الحالة يقبل المُستقبِل السلسلة الفارغة. يُظهر المثال في الشكل 4 مُستقبِلًا يقبل السلسلة "nice". في هذا المُستقبِل، حالة القبول الوحيدة هي الحالة 7.

تُسمى مجموعة (قد تكون لانهائية) من متواليات الرموز، والتي تُسمى لغة رسمية ، لغة منتظمة إذا وُجد مُستقبِل يقبل تلك المجموعة تحديدًا . ^{[ 13 ]} على سبيل المثال، تُعد مجموعة السلاسل الثنائية التي تحتوي على عدد زوجي من الأصفار لغة منتظمة (انظر الشكل 5)، بينما لا تُعد مجموعة جميع السلاسل التي يكون طولها عددًا أوليًا لغة منتظمة. ^{[ 14 ]}

يمكن تعريف المُستقبِل أيضًا بأنه لغة تحتوي على جميع السلاسل النصية التي يقبلها المُستقبِل، ولا تحتوي على أي من السلاسل المرفوضة؛ وهذه اللغة مقبولة من قِبَل المُستقبِل. وبحسب التعريف، فإن اللغات التي يقبلها المُستقبِلون هي اللغات المنتظمة .

تُعدّ مشكلة تحديد اللغة المقبولة من قِبل مُستقبِل مُعيّن مثالاً على مشكلة المسار الجبري ، وهي في حد ذاتها تعميم لمشكلة أقصر مسار إلى الرسوم البيانية ذات الحواف الموزونة بعناصر شبه حلقة (اختيارية) . ^{[ 15 ] [ 16 ]}

يظهر مثال على حالة القبول في الشكل 5: آلة حتمية محدودة (DFA) تكتشف ما إذا كانت سلسلة الإدخال الثنائية تحتوي على عدد زوجي من الأصفار.

_{تشير الحالة} S1 (وهي أيضًا حالة البداية) إلى الحالة التي تم فيها إدخال عدد زوجي من الأصفار. لذا، تُعدّ S1 _حالة قبول. سينتهي هذا المُستقبِل بحالة قبول إذا احتوت السلسلة الثنائية على عدد زوجي من الأصفار (بما في ذلك أي سلسلة ثنائية لا تحتوي على أصفار). من أمثلة السلاسل التي يقبلها هذا المُستقبِل: ε ( السلسلة الفارغة )، 1، 11، 11...، 00، 010، 1010، 10110، إلخ.

محولات الطاقة

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

في تطبيقات التحكم، يتم تمييز نوعين:

آلة مور

تعتمد آلة الحالة المحدودة (FSM) على إجراءات الدخول فقط، أي أن المخرجات تعتمد على الحالة فقط. وتكمن ميزة نموذج مور في تبسيط السلوك. لنفترض باب مصعد. تتعرف آلة الحالة على أمرين: "command_open" و"command_close"، واللذان يُحدثان تغييرات في الحالة. يبدأ إجراء الدخول (E:) في حالة "Opening" محركًا لفتح الباب، بينما يبدأ إجراء الدخول في حالة "Closing" محركًا في الاتجاه المعاكس لإغلاق الباب. تُوقف حالتا "Opened" و"Closed" المحرك عند فتح الباب أو إغلاقه بالكامل. تُشير هاتان الحالتان إلى العالم الخارجي (مثل آلات الحالة الأخرى) إلى الحالة: "الباب مفتوح" أو "الباب مغلق".

آلة الدقيق

تستخدم آلة الحالة المحدودة (FSM) أيضًا إجراءات الإدخال، أي أن المخرجات تعتمد على المدخلات والحالة. غالبًا ما يؤدي استخدام آلة حالة محدودة من نوع ميلي إلى تقليل عدد الحالات. يوضح المثال في الشكل 7 آلة حالة محدودة من نوع ميلي تُنفذ نفس السلوك كما في مثال مور (يعتمد السلوك على نموذج تنفيذ آلة الحالة المحدودة المُطبق، وسيعمل، على سبيل المثال، مع آلة الحالة المحدودة الافتراضية ، ولكن ليس مع آلة الحالة المحدودة القائمة على الأحداث ). يوجد إجراءان للإدخال (I:): "تشغيل المحرك لإغلاق الباب عند وصول الأمر command_close" و"تشغيل المحرك في الاتجاه المعاكس لفتح الباب عند وصول الأمر command_open". لم يتم عرض حالتي "الفتح" و"الإغلاق" الوسيطتين.

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

وفقًا للتصنيف العام، تم العثور على التعريفات الرسمية التالية.

الآلة الحتمية ذات الحالة المحدودة أو جهاز الاستقبال الحتمي ذو الحالة المحدودة هو خماسي${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$، أين:

• ${\displaystyle \Sigma }$هي الأبجدية المدخلة (مجموعة محدودة غير فارغة من الرموز)؛
• ${\displaystyle S}$هي مجموعة محدودة غير فارغة من الحالات؛
• ${\displaystyle s_{0}}$هي حالة ابتدائية، عنصر من${\displaystyle S}$؛
• ${\displaystyle \delta }$هي دالة انتقال الحالة:${\displaystyle \delta :S\times \Sigma \rightarrow S}$(في آلة محدودة غير حتمية سيكون الأمر كذلك)${\displaystyle \delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)}$، أي${\displaystyle \delta }$سوف تُعيد مجموعة من الحالات)؛
• ${\displaystyle F}$هي مجموعة الحالات النهائية، وهي مجموعة فرعية (قد تكون فارغة) من${\displaystyle S}$.

بالنسبة لكل من آلات الحالة المحدودة الحتمية وغير الحتمية، من المتعارف عليه السماح${\displaystyle \delta }$أن تكون دالة جزئية ، أي${\displaystyle \delta (s,x)}$لا يلزم تعريفها لكل تركيبة من${\displaystyle s\in S}$و${\displaystyle x\in \Sigma }$إذا كانت آلة الحالة المحدودة${\displaystyle M}$يقع في ولاية${\displaystyle s}$الرمز التالي هو${\displaystyle x}$و${\displaystyle \delta (s,x)}$إذا لم يتم تعريفها، فـ${\displaystyle M}$يمكن للخوارزمية الإعلان عن خطأ (أي رفض المدخلات). يُعدّ هذا مفيدًا في تعريفات آلات الحالة العامة، ولكنه أقل فائدة عند تحويل الآلة. قد تتطلب بعض الخوارزميات في شكلها الافتراضي دوالًا كلية.

تتمتع آلة الحالة المحدودة بنفس القدرة الحسابية لآلة تورينج المقيدة بحيث لا يمكن لرأسها سوى إجراء عمليات "القراءة"، ويجب أن يتحرك دائمًا من اليسار إلى اليمين. أي أن كل لغة رسمية تقبلها آلة الحالة المحدودة تقبلها أيضًا آلة تورينج المقيدة من هذا النوع، والعكس صحيح. ^{[ 23 ]}

المحول ذو الحالة المحدودة هو سداسي${\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}$، أين:

• ${\displaystyle \Sigma }$هي الأبجدية المدخلة (مجموعة محدودة غير فارغة من الرموز)؛
• ${\displaystyle \Gamma }$هي الأبجدية الناتجة (مجموعة محدودة غير فارغة من الرموز)؛
• ${\displaystyle S}$هي مجموعة محدودة غير فارغة من الحالات؛
• ${\displaystyle s_{0}}$هي الحالة الابتدائية، عنصر من${\displaystyle S}$؛
• ${\displaystyle \delta }$هي دالة انتقال الحالة:${\displaystyle \delta :S\times \Sigma \rightarrow S}$؛
• ${\displaystyle \omega }$هي دالة الإخراج.

إذا كانت دالة الإخراج تعتمد على الحالة ورمز الإدخال (${\displaystyle \omega :S\times \Sigma \rightarrow \Gamma }$يتوافق هذا التعريف مع نموذج ميلي ، ويمكن نمذجته كآلة ميلي . إذا كانت دالة الإخراج تعتمد فقط على الحالة (${\displaystyle \omega :S\rightarrow \Gamma }$يتوافق هذا التعريف مع نموذج مور ، ويمكن نمذجته كآلة مور . تُعرف الآلة ذات الحالات المحدودة التي لا تحتوي على دالة إخراج على الإطلاق باسم شبه آلي أو نظام انتقالي .

إذا تجاهلنا رمز الإخراج الأول لآلة مور،${\displaystyle \أوميغا (s_{0})}$ثم يمكن تحويلها بسهولة إلى آلة ميلي مكافئة للمخرجات عن طريق تحديد دالة الإخراج لكل انتقال ميلي (أي تسمية كل حافة) برمز الإخراج المعطى لحالة مور الوجهة. أما التحويل العكسي فهو أقل وضوحًا لأن حالة آلة ميلي قد تحتوي على تسميات إخراج مختلفة على انتقالاتها (حوافها) الواردة. كل حالة من هذا القبيل تحتاج إلى تقسيمها إلى حالات متعددة لآلة مور، حالة لكل رمز إخراج وارد. ^{[ 24 ]}

تحسين آلة الحالة المحدودة يعني إيجاد آلة بأقل عدد من الحالات تؤدي نفس الوظيفة. أسرع خوارزمية معروفة لتحقيق ذلك هي خوارزمية هوبكروفت للتقليل . ^{[ 25 ] [ 26 ]} تشمل التقنيات الأخرى استخدام جدول الاستلزام ، أو إجراء اختزال مور. ^{[ 27 ]} بالإضافة إلى ذلك، يمكن تقليل آلات الحالة المحدودة غير الدورية في وقت خطي . ^{[ 28 ]}

عام

الآلات ذات الحالة المحدودة (نظرية الأوتوماتا) في علوم الحاسوب النظرية

آلات الحالة المجردة في علوم الحاسوب النظرية

التعلم الآلي باستخدام خوارزميات الحالة المحدودة

هندسة الأجهزة

تقليل عدد الحالات وتوليف الدوائر التسلسلية

عمليات سلسلة ماركوف المحدودة

يمكننا اعتبار سلسلة ماركوف عملية تنتقل تباعًا عبر مجموعة من الحالات s1 _، s2 ، ...، _sr . _... إذا كانت في الحالة si، _{فإنها تنتقل} إلى الحالة التالية sj باحتمال _pij . يمكن تمثيل هذه الاحتمالات في شكل مصفوفة انتقال .

تُعرف عمليات سلسلة ماركوف المحدودة أيضًا باسم التحولات الفرعية من النوع المحدود .