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

آلة الحالة المحدودة ( FSM ) أو أتمتة الحالة المحدودة ( FSA ، جمع: أتمتة )، أتمتة منتهية ، أو ببساطة آلة حالة ، هي نموذج رياضي للحوسبة . إنها آلة مجردة يمكن أن تكون في حالة واحدة بالضبط من عدد محدود من الحالات في أي وقت معين. يمكن أن تتغير FSM من حالة إلى أخرى استجابة لبعض المدخلات ؛ يسمى التغيير من حالة إلى أخرى انتقال . ^[1] يتم تعريف FSM من خلال قائمة حالاتها وحالتها الأولية والمدخلات التي تؤدي إلى كل انتقال. آلات الحالة المحدودة هي من نوعين - آلات الحالة المحدودة الحتمية وآلات الحالة المحدودة غير الحتمية . ^[2] بالنسبة لأي آلة حالة محدودة غير حتمية، يمكن إنشاء آلة حتمية مكافئة.

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

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

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

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

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

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

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

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

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

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

تُستخدم عدة أنواع من جداول انتقال الحالة . يظهر التمثيل الأكثر شيوعًا أدناه: يُظهر الجمع بين الحالة الحالية (على سبيل المثال B) والمدخلات (على سبيل المثال Y) الحالة التالية (على سبيل المثال C). لا يتم وصف معلومات الإجراء الكاملة مباشرةً في الجدول ولا يمكن إضافتها إلا باستخدام الحواشي السفلية. ^{[ مطلوب مزيد من التوضيح ]} من الممكن إنشاء تعريف FSM يتضمن معلومات الإجراء الكاملة باستخدام جداول الحالة (انظر أيضًا آلة الحالة المحدودة الافتراضية ).

جدول انتقال الحالة

الحالة   الحالية مدخل	الدولة أ	الدولة ب	الدولة ج
الإدخال X	...	...	...
الإدخال Y	...	الدولة ج	...
الإدخال Z	...	...	...

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

لغة المواصفات والوصف هي معيار من الاتحاد الدولي للاتصالات يتضمن رموزًا رسومية لوصف الإجراءات في عملية الانتقال:

• إرسال حدث
• تلقي حدث
• بدء تشغيل مؤقت
• إلغاء مؤقت
• بدء تشغيل آلة حالة متزامنة أخرى
• قرار

تتضمن SDL أنواع بيانات أساسية تسمى "أنواع البيانات المجردة"، ولغة عمل، ودلالات تنفيذية من أجل جعل آلة الحالة المحدودة قابلة للتنفيذ. ^{[ بحاجة لمصدر ]}

هناك عدد كبير من المتغيرات لتمثيل FSM مثل تلك الموجودة في الشكل 3.

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

يمكن تقسيم الآلات ذات الحالة المحدودة إلى أجهزة قبول ومصنفات ومحولات وتسلسلات. ^[6]

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

مجموعة (ربما لا نهائية) من تسلسلات الرموز، تسمى لغة رسمية ، هي لغة عادية إذا كان هناك بعض المستقبلين الذين يقبلون هذه المجموعة بالضبط . ^[7] على سبيل المثال، مجموعة السلاسل الثنائية التي تحتوي على عدد زوجي من الأصفار هي لغة عادية (راجع الشكل 5)، في حين أن مجموعة جميع السلاسل التي يكون طولها عددًا أوليًا ليست كذلك. ^[8]

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

إن مشكلة تحديد اللغة التي يقبلها متقبل معين هي مثال على مشكلة المسار الجبري - وهي في حد ذاتها تعميم لمشكلة أقصر مسار للرسوم البيانية ذات الحواف المرجحة بعناصر شبه الحلقة (التعسفية) . ^{[9] [10] [ مصطلحات ]}

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

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

المصنفات هي تعميم للمستقبلات التي تنتج مخرجات n -ary حيث يكون n أكبر تمامًا من اثنين. ^[11]

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

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

ماكينة مور

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

آلة الدقيق

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

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

هناك تمييز آخر بين الأتمتة الحتمية ( DFA ) وغير الحتمية ( NFA ، GNFA ). في الأتمتة الحتمية، تحتوي كل حالة على انتقال واحد فقط لكل إدخال ممكن. في الأتمتة غير الحتمية، يمكن أن يؤدي الإدخال إلى انتقال واحد أو أكثر أو عدم انتقال على الإطلاق لحالة معينة. يمكن لخوارزمية بناء مجموعة القوى تحويل أي أتمتة غير حتمية إلى أتمتة حتمية (عادةً ما تكون أكثر تعقيدًا) ذات وظائف متطابقة.

تسمى الآلة ذات الحالة المحدودة التي تحتوي على حالة واحدة فقط "آلة FSM تركيبية". فهي تسمح فقط بالإجراءات عند الانتقال إلى حالة. هذا المفهوم مفيد في الحالات التي تتطلب فيها عدد من الآلات ذات الحالة المحدودة العمل معًا، وعندما يكون من المناسب اعتبار جزء تركيبي بحت كشكل من أشكال FSM لتناسب أدوات التصميم. ^[12]

توجد مجموعات أخرى من الدلالات المتاحة لتمثيل آلات الحالة. على سبيل المثال، توجد أدوات لنمذجة وتصميم المنطق لوحدات التحكم المضمنة. ^[13] فهي تجمع بين آلات الحالة الهرمية (التي تحتوي عادةً على أكثر من حالة حالية واحدة)، ومخططات التدفق، وجداول الحقيقة في لغة واحدة، مما ينتج عنه صيغة مختلفة ومجموعة من الدلالات. ^[14] تدعم هذه المخططات، مثل آلات الحالة الأصلية لهاريل ، ^[15] الحالات المتداخلة هرميًا، والمناطق المتعامدة ، وإجراءات الحالة، وإجراءات الانتقال. ^[16]

وفقًا للتصنيف العام، نجد التعريفات الرسمية التالية:

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

• ${\displaystyle \سيجما }$هو الأبجدية المدخلة (مجموعة محدودة غير فارغة من الرموز)؛
• ${\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}$

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

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

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

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

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

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

إن تحسين FSM يعني إيجاد آلة بها أقل عدد من الحالات التي تؤدي نفس الوظيفة. أسرع خوارزمية معروفة للقيام بذلك هي خوارزمية الحد الأدنى هوبكروفت . ^{[19] [20]} تتضمن التقنيات الأخرى استخدام جدول التضمين ، أو إجراء تقليل مور. ^[21] بالإضافة إلى ذلك، يمكن تقليل FSAs غير الدورية في وقت خطي . ^[22]

في الدائرة الرقمية ، يمكن بناء FSM باستخدام جهاز منطقي قابل للبرمجة ، ووحدة تحكم منطقية قابلة للبرمجة ، وبوابات منطقية ، وقلابات أو مرحلات . وبشكل أكثر تحديدًا، يتطلب التنفيذ المادي سجلًا لتخزين متغيرات الحالة، وكتلة من المنطق التركيبي التي تحدد انتقال الحالة، وكتلة ثانية من المنطق التركيبي التي تحدد خرج FSM. أحد التنفيذات المادية الكلاسيكية هو وحدة تحكم ريتشاردز .

في آلة ميدفيديف ، يكون الإخراج متصلاً بشكل مباشر بقلابات الحالة مما يقلل من التأخير الزمني بين القلابات والإخراج. ^{[23] [24]}

من خلال ترميز الحالة للآلات ذات الحالة منخفضة الطاقة، يمكن تحسينها لتقليل استهلاك الطاقة.

تُستخدم المفاهيم التالية عادةً لبناء تطبيقات برمجية باستخدام آلات الحالة المحدودة:

• البرمجة المعتمدة على الأتمتة
• آلة الحالة المحدودة التي تعتمد على الأحداث
• آلة الحالة المحدودة الافتراضية
• نمط تصميم الدولة

غالبًا ما تُستخدم الأتمتة المحدودة في الواجهة الأمامية لمُجمِّعي لغات البرمجة. قد تتألف هذه الواجهة الأمامية من عدة آلات ذات حالة محدودة تنفذ مُحللًا معجميًا ومُحللًا. بدءًا من تسلسل من الأحرف، يبني المُحلل المعجمي تسلسلًا من رموز اللغة (مثل الكلمات المحجوزة، والحروف، والمعرفات) والتي يبني منها المُحلل شجرة نحوية. يتعامل المُحلل المعجمي والمحلل مع الأجزاء العادية والخالية من السياق من قواعد لغة البرمجة. ^[25]

• هوبكروفت، جون إي.؛ أولمان، جيفري دي. (1979). مقدمة إلى نظرية الأتمتة واللغات والحوسبة (الطبعة الأولى). أديسون ويسلي. رقم ISBN 0-201-02988-X.(متاح للرعاة ذوي الإعاقات المطبوعة)
• هوبكروفت، جون إي .؛ موتواني، راجيف ؛ أولمان، جيفري دي. (2006) [1979]. مقدمة إلى نظرية الأتمتة واللغات والحوسبة (الطبعة الثالثة). أديسون ويسلي. ISBN 0-321-45536-3.

• ساكاروفيتش، جاك (2009). عناصر نظرية الأتمتة . ترجمة من الفرنسية بواسطة روبن توماس. مطبعة جامعة كامبريدج . رقم ISBN 978-0-521-84425-3. زبل  1188.68177.
• فاغنر، ف.، "نمذجة البرمجيات باستخدام آلات الحالة المحدودة: نهج عملي"، منشورات أورباخ، 2006، ISBN 0-8493-8086-3 . 
• ITU-T، توصية Z.100، لغة المواصفات والوصف (SDL)
• ساميك، م.، مخططات الحالة العملية في C/C++، كتب CMP، 2002، ISBN 1-57820-110-1 . 
• ساميك، م.، مخططات حالة UML العملية في C/C++، الطبعة الثانية، نيونس، 2008، ISBN 0-7506-8706-1 . 
• جاردنر، ت.، إدارة الحالة المتقدمة محفوظ في 19 نوفمبر 2008 على موقع واي باك مشين ، 2007
• كاساندراس، سي، لافورتون، إس، "مقدمة إلى أنظمة الأحداث المنفصلة". كلوير، 1999، ISBN 0-7923-8609-4 . 
• تيموثي كام، تركيب آلات الحالة المحدودة: التحسين الوظيفي . دار نشر كلوير الأكاديمية، بوسطن 1997، رقم ISBN 0-7923-9842-4 
• تيزيانو فيلا، تركيب آلات الحالة المحدودة: تحسين المنطق . دار نشر كلوير الأكاديمية، بوسطن 1997، رقم ISBN 0-7923-9892-0 
• كارول، جيه، لونج، دي، نظرية الأتمتة المحدودة مع مقدمة للغات الرسمية . برنتيس هول، إنجلوود كليفس، 1989.
• كوهافي، ز.، نظرية التبديل والأتمتة المحدودة . ماكجرو هيل، 1978.
• جيل، أ.، مقدمة لنظرية الآلات ذات الحالة المحدودة . ماكجرو هيل، 1962.
• جينسبيرج، س.، مقدمة إلى نظرية الآلة الرياضية . أديسون ويسلي، 1962.

• أربيب، مايكل أ. (1969). نظريات الأتمتة المجردة (الطبعة الأولى). إنجلوود كليفس، نيوجيرسي: برنتيس هول، إنك. رقم ISBN 978-0-13-913368-8.
• بوبرو، ليونارد س.؛ أربيب، مايكل أ. (1974). الرياضيات المنفصلة: الجبر التطبيقي لعلوم الحاسب والمعلومات (الطبعة الأولى). فيلادلفيا: شركة دبليو بي سوندرز المحدودة. رقم ISBN 978-0-7216-1768-8.
• بوث، تايلور إل. (1967). نظرية الآلات المتسلسلة والأتمتة (الطبعة الأولى). نيويورك: جون وايلي وأولاده، شركة. رقم فهرس بطاقات مكتبة الكونجرس 67-25924.
• بولوس، جورج؛ جيفري، ريتشارد (1999) [1989]. الحوسبة والمنطق (الطبعة الثالثة). كامبريدج، إنجلترا: مطبعة جامعة كامبريدج. رقم ISBN 978-0-521-20402-6.
• بروكشير، ج. جلين (1989). نظرية الحوسبة: اللغات الرسمية، والأتمتة، والتعقيد . ريدوود سيتي، كاليفورنيا: شركة بنيامين/كومينجز للنشر، المحدودة. رقم ISBN 978-0-8053-0143-4.
• ديفيس، مارتن؛ سيجال، رون؛ وييكر، إلين جيه. (1994). قابلية الحساب والتعقيد واللغات والمنطق: أساسيات علوم الكمبيوتر النظرية (الطبعة الثانية). سان دييجو: أكاديميك بريس، هاركورت، بريس آند كومباني. رقم ISBN 978-0-12-206382-4.
• هوبكين، ديفيد؛ موس، باربرا (1976). أتمتة . نيويورك: إلسفير شمال هولندا. رقم ISBN 978-0-444-00249-5.
• كوزين، ديكستر سي. (1997). الأتمتة والحوسبة (الطبعة الأولى). نيويورك: سبرينغر-فيرلاغ. رقم ISBN 978-0-387-94907-9.
• لويس، هاري ر .؛ باباديميتريو، كريستوس هـ. (1998). عناصر نظرية الحوسبة (الطبعة الثانية). أبر سادل ريفر، نيوجيرسي: برنتيس هول. رقم ISBN 978-0-13-262478-7.
• لينز، بيتر (2006). اللغات الرسمية والآلات الآلية (الطبعة الرابعة). سودبوري، ماساتشوستس: جونز وبارتليت. رقم ISBN 978-0-7637-3798-6.
• مينسكي، مارفن (1967). الحوسبة: الآلات المحدودة واللانهائية (الطبعة الأولى). نيوجيرسي: برنتيس هول.
• باباديميتريو، كريستوس (1993). التعقيد الحسابي (الطبعة الأولى). أديسون ويسلي. رقم ISBN 978-0-201-53082-7.
• بيبنغر، نيكولاس (1997). نظريات قابلية الحساب (الطبعة الأولى). كامبريدج، إنجلترا: مطبعة جامعة كامبريدج. رقم ISBN 978-0-521-55380-3.
• روجر، سوزان؛ فينلي، توماس (2006). JFLAP: حزمة لغات رسمية تفاعلية وأتمتة (الطبعة الأولى). سودبوري، ماساتشوستس: جونز وبارتليت. رقم ISBN 978-0-7637-3834-1.
• سيبسر، مايكل (2006). مقدمة إلى نظرية الحوسبة (الطبعة الثانية). بوسطن، ماساتشوستس: دورة تومسون للتكنولوجيا. رقم ISBN 978-0-534-95097-2.
• وود، ديريك (1987). نظرية الحوسبة (الطبعة الأولى). نيويورك: هاربر ورو، للنشر، المحدودة. رقم ISBN 978-0-06-047208-5.

• جورفيتش، يوري (يوليو 2000). "آلات الحالة المجردة المتسلسلة تلتقط الخوارزميات المتسلسلة" (ملف PDF) . معاملات ACM للمنطق الحسابي . 1 (1): 77-111. CiteSeerX  10.1.1.146.3017 . doi :10.1145/343369.343384. S2CID  2031696.

• ميتشل، توم م. (1997). التعلم الآلي (الطبعة الأولى). نيويورك: دبليو سي بي/شركة ماكجرو هيل. رقم ISBN 978-0-07-042807-2.

• بوث، تايلور إل. (1967). نظرية الآلات المتسلسلة والأتمتة (الطبعة الأولى). نيويورك: جون وايلي وأولاده، شركة. رقم فهرس بطاقات مكتبة الكونجرس 67-25924.
• Booth, Taylor L. (1971). Digital Networks and Computer Systems (الطبعة الأولى). نيويورك: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
• McCluskey, EJ (1965). Introduction to the Theory of Switching Circuits (الطبعة الأولى). نيويورك: McGraw-Hill Book Company, Inc. رقم فهرس بطاقات مكتبة الكونجرس 65-17394.
• هيل، فريدريك جيه؛ بيترسون، جيرالد ر. (1965). مقدمة إلى نظرية دوائر التبديل (الطبعة الأولى). نيويورك: شركة ماكجرو هيل للكتب. رقم فهرس بطاقات مكتبة الكونجرس 65-17394.

"يمكننا أن نفكر في سلسلة ماركوف باعتبارها عملية تتحرك على التوالي عبر مجموعة من الحالات s ₁ و s ₂ و... و s _r ... وإذا كانت في الحالة s _i فإنها تنتقل إلى المحطة التالية إلى الحالة s _j باحتمال p _ij . ويمكن عرض هذه الاحتمالات في شكل مصفوفة انتقالية" (كيميني (1959)، ص 384)

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

• بوث، تايلور إل. (1967). نظرية الآلات المتسلسلة والأتمتة (الطبعة الأولى). نيويورك: جون وايلي وأولاده، شركة. رقم فهرس بطاقات مكتبة الكونجرس 67-25924.
• Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Finite Mathematical Structures (الطبعة الأولى). Englewood Cliffs, NJ: Prentice-Hall, Inc. رقم فهرس بطاقات مكتبة الكونجرس 59-12841.الفصل السادس "سلاسل ماركوف المنتهية".

• نمذجة سلوك الذكاء الاصطناعي البسيط باستخدام آلة الحالة المحدودة مثال للاستخدام في ألعاب الفيديو
• قاموس مجاني على الإنترنت لوصف الآلات ذات الحالة المحدودة
• وصف آلات الحالة المحدودة في قاموس NIST للخوارزميات وهياكل البيانات
• نظرة عامة موجزة على أنواع آلات الحالة، ومقارنة الجوانب النظرية لآلات الحالة Mealy وMoore وHarel وUML.