نظرية آلة الحالة المحدودة

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

· يمكن لآلة الحالة أن تحل عددًا من مشكلات التجميع خفيفة الوزن. يتم دائمًا بناء الكتلة المعجمية على أساس آلة الحالة المحدودة.

· يتميز تشغيل آلة الحالة المحدودة بالأداء العالي.

· تتطلب نمذجة آلة الحالة مقدارًا ثابتًا من الذاكرة، مما يبسط إدارة الذاكرة.

· هناك عدد من النظريات والخوارزميات التي تسمح لك ببناء وتبسيط آلات الحالة المحدودة.

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

تعريف:آلة الحالة المحدودة هي نظام رسمي يتم تعريفه باستخدام الكائنات التالية:

· مجموعة محدودة من رموز الإدخال.

· مجموعة محدودة من الحالات.

· وظيفة انتقالية تخصص لكل زوج (الحالة الحالية، رمز الإدخال) حالة جديدة؛

· الحالة الأولية؛

· مجموعة فرعية من الحالات التي تم تحديدها على أنها متساهلة أو نهائية.

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

يمكن وصف تشغيل الآلة رياضياً من خلال دالة انتقالية بالصيغة d(Scurrent, x) = Snew. وإلا فإنه يمكن كتابتها على النحو التالي:

د (حتى، 0) = حتى. د(زوجي، 1) = فردي.

د(فردي، 0) = فردي. د (فردي، 1) = زوجي.

وحدة التحكم لديها حالة قبول واحدة، ODD، وEVEN هي حالة "رفض". دعونا نعكس تسلسل انتقالات الآلة عند توصيل السلسلة 1101 بمدخلها.

حتى ® غريب ® حتى ® حتى ® غريب

يحتوي الجدول الانتقالي لمثل هذا الإنسان على الشكل:

حتى	حتى	غريب
غريب	غريب	حتى

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

S = (أ، س، د، ل، الخامس)،

كائناتها هي التالية:

* A عبارة عن مجموعة محدودة من رموز الإدخال (set

محطات)؛

* س - مجموعة محدودة من الحالات الداخلية للآلة

(مجموعة من غير المحطات)؛

* V - مجموعة محدودة من رموز الإخراج (أبجدية الإخراج)؛

* د - وظيفة الانتقال، والتي تتميز بـ A ´Q ® Q؛

* ل - وظيفة الإخراج التي تحدد طريقة العرض.

نظرية الأتمتة

تعريف الآلة وتنوعها. الجداول والرسوم البيانية للانتقالات والمخرجات. الآلات شبه الأوتوماتيكية. تخفيض نظرية الآلي

العمليات مع الآلات

تحويل آلة ميلي إلى آلة مور وآلة مور إلى آلة ميلي. معادلة الآلات. التمييز بين حالات الأتمتة. التقليل من الأتمتة. توليف الآلي. آلات الاعتراف

الآلة الأوتوماتيكية هي نظام من الآليات والأجهزة تكون فيها عمليات استقبال وتحويل ونقل الطاقة والمواد والمعلومات مؤتمتة بالكامل. ويستخدم مصطلح "الآلة الأوتوماتيكية" في جانبين:

1) التقنية،

2) رياضي.

في المنهج الرياضي، يُفهم الإنسان الآلي على أنه نموذج رياضي الجهاز الفنيوالتي يجب أن تحتوي على مدخلات وحالات داخلية ومخرجات. يجب ألا تكون هناك معلومات بخصوص تفاصيل هيكل الجهاز.

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

من الحالات الخاصة والمهمة للآلة الآلية هي الآلة الرقمية (DA)، حيث تكون عمليات تلقي المعلومات الرقمية وتحويلها وتخزينها وإصدارها مؤتمتة بالكامل.

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

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

يتم تنفيذ عمل الجمهور المستهدف في وقت تلقائي، يحدده عدد فترات استلام إشارات الإدخال.

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

يمكن تمثيل كلمات لغة الإدخال برموز المجموعة X=(x 1 ,x 2 ,...x n )، والتي تسمى أبجدية الإدخال، وكلمات لغة الإخراج هي رموز المجموعة Y=(y 1 ,y 2 ,...y p )، والتي تسمى الأبجدية الإخراج. مجموعة حالات الإنسان S=(s 1 ,s 2 ,...s m ) تسمى أبجدية الدول.

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

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

يُستخدم مفهوم "الحالة" لتحديد الاعتماد الوظيفي لرموز و/أو كلمات لغة الإخراج التي ينشئها الجهاز على رموز و/أو كلمات لغة الإدخال عندما ينفذ الجهاز خوارزمية معينة. لكل حالة من حالات الإنسان sОS ولكل رمز xОX في لحظة الوقت المنفصل [t]، يتم إنشاء الرمز yОY عند إخراج الجهاز. يتم تحديد هذا الاعتماد من خلال وظيفة الإخراج للآلة j. لكل حالة حالية للآلة sОS ولكل رمز xОX في لحظة الوقت المنفصل [t]، ينتقل الإنسان إلى الحالة التالية sОS. يتم تحديد هذا الاعتماد من خلال وظيفة الانتقال للآلة y. يتكون تشغيل الإنسان الآلي من توليد تسلسلين: تسلسل الحالات التالية للآلة (s 1[ s 2 s 3 ...) وتسلسل رموز الإخراج (y 1 y 2 y 3 ...)، والتي بالنسبة لتسلسل الرموز (x 1 x 2 x 3...) تتكشف في لحظات زمنية منفصلة t = 1,2,3،.... بين قوسين مستطيلين تشير إلى لحظات زمنية منفصلة، ​​والتي تسمى دورات الساعة ، بين قوسين - تسلسل الحروف الهجائية X و Y و S.

لذا، فإن النموذج الرياضي للإنسان المحدود هو جبر ثلاثي أساسي، حاملاته هي ثلاث مجموعات X وY وS، والعمليات هي وظيفتان j وy.

تتناول المقالة أجهزة الحالة المحدودة البسيطة وتنفيذها في لغة C++ باستخدام بنيات التبديل وجداول وقت التشغيل ومكتبة Boost Statechart.

مقدمة

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

يتم تصوير آلات الحالة المحدودة في شكل رسوم بيانية تتكون من حالات وانتقالات. اسمحوا لي أن أشرح بمثال بسيط:

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

تُستخدم الجداول الانتقالية أيضًا على نطاق واسع:

التطبيق العملي للآلات الأوتوماتيكية

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

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

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

دعونا نلقي نظرة على الرسم البياني:

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

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

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

إنسان آلي باستخدام تعليمات التبديل

الأول هو الحالات الممكنة:

وبعد ذلك نكرر الخط، وندخل الرمز الحالي إلى الجهاز. الإنسان الآلي نفسه عبارة عن تعليمات تبديل تقوم أولاً بالانتقال إلى قسم الحالة الحالية. يوجد داخل القسم بناء if-else، والذي، اعتمادًا على الحدث (الرمز الوارد)، يغير الحالة الحالية:

const size_t length = text. length(); for (size_t i = 0 ; i ! = length; ++ i) ( const char current = text[ i] ; Switch (state) ( case State_Start: if (std:: isdigit (current) ) (state = State_Number; ) وإلا إذا (std:: isalpha (current)) (state = State_Word;) فاصل case State_Number: if (std:: isspace (current) ) (

نحن هنا ننظر إلى الرسم البياني - الحالة الحالية رقم، حدث فضاء(تم العثور على حرف مسافة)، مما يعني العثور على الرقم:

FoundNumber(); الحالة = State_Start؛ ) وإلا إذا (! std::isdigit(current) ) (state = State_Skip;) فاصل; case State_Word: if (std:: isspace (current) ) ( FoundWord() ;state = State_Start; ) else if (! std:: isalpha (current)) ) (state = State_Skip; ) استراحة ; case State_Skip: if (std::isspace (current) ) (state = State_Start;) فاصل; ))

نتيجة:

كفاءة عالية

سهولة التنفيذ للخوارزميات البسيطة

- صعوبة الصيانة

تفسير وقت التشغيل

فكرة هذا النهج بسيطة - تحتاج إلى إنشاء جدول انتقالي، وتعبئته، وبعد ذلك، عند حدوث حدث ما، ابحث عن الحالة التالية في الجدول وقم بإجراء الانتقال:

تعداد الأحداث ( Event_Space، Event_Digit، Event_Letter، Event_Unknown ) ؛ عملية باطلة (حدث الأحداث) ؛ ... انتقال البنية ( States BaseState_; Events Event_; States TargetState_; ) ; void AddTransition(States fromState, Events events, States toState) ؛ ...typedef std::vector< transition>TransitionTable; TransitionTable Transitions_; الدول CurrentState_؛

ملء الجدول:

AddTransition(State_Start, Event_Digit, State_Number) ؛ AddTransition(State_Start, Event_Letter, State_Word) ؛ AddTransition(State_Number, Event_Space, State_Start) ؛ AddTransition(State_Number, Event_Letter, State_Skip) ؛ AddTransition(State_Number, Event_Unknown, State_Skip) ؛ AddTransition(State_Word, Event_Space, State_Start) ؛ AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ;

اتضح بشكل واضح تماما. سيكون ثمن الوضوح هو تشغيل الجهاز بشكل أبطأ، وهو ما لا يهم في كثير من الأحيان.

حتى يتمكن الجهاز، عند حدوث أحداث معينة، من إخطار بعض التعليمات البرمجية، يمكنك إضافته إلى البنية بمعلومات حول الانتقال ( انتقال) مؤشر الوظيفة ( فعل)، والتي سوف تسمى:

typedef void (DynamicMachine:: * Action) () ؛ انتقال البنية (states BaseState_; Events Event_; States TargetState_; Action Action_;) ; ... void AddTransition(States fromState, Events events, States toState, Action action) ؛ ...AddTransition(State_Number, Event_Space, State_Start, & DynamicMachine::FoundNumber) ؛

نتيجة:

المرونة والرؤية

أسهل للصيانة

- أداء أقل مقارنة بوحدات التبديل

تفسير وقت التنفيذ. تحسين السرعة

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

يتم تحقيق النتيجة على حساب استهلاك الذاكرة.

نتيجة:

المرونة والرؤية

فعال

- استهلاك الذاكرة (على الأرجح غير مهم)

تعزيز مخطط الحالة

ناقشنا عدة طرق لتنفيذ آلة الحالة بنفسك. من أجل التغيير، أقترح التفكير في إنشاء مكتبة لبناء الآلات من Boost. هذه المكتبة قوية للغاية؛ تتيح لك الإمكانيات المتوفرة إنشاء أجهزة ذات حالة محدودة ومعقدة للغاية. سوف ننظر في الأمر بسرعة كبيرة.

لذا، أولاً نقوم بتعريف الأحداث:

أحداث مساحة الاسم (رقم الهيكل: Boost::statechart::event< Digit>( ) ؛ الرسالة الهيكلية: Boost::statechart::event< Letter>( ) ؛ مساحة البناء: Boost::statechart::event< Space>( ) ؛ البنية غير معروفة: Boost::statechart::event< Unknown> { } ; }

الجهاز نفسه (لاحظ أن معلمة القالب الثاني هي الحالة الأولية):

آلة الهيكل: Boost::statechart::state_machine< Machine, States:: Start > { } ;

والدول نفسها. داخل الحالات، من الضروري تحديد النوع الذي يصف التحولات ( تفاعلات)، وإذا كان هناك العديد من التحولات، فقم بإدراجها في قائمة نوع Boost::mpl::list. معلمة القالب الثاني simple_state- اكتب وصف الجهاز. يتم وصف التحولات بواسطة معلمات قالب الانتقال، الزوج الحدث - الحالة التالية:

حالات مساحة الاسم (بداية الهيكل: Boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> ردود الفعل؛ ) ; رقم الهيكل: Boost::statechart::simple_state< Number, Machine>( تعزيز typedef::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, Boost::statechart::transition< Events:: Letter , States:: Skip >, Boost::statechart::transition< Events:: Unknown , States:: Skip >> ردود الفعل؛ ) ; كلمة البناء: Boost::statechart::simple_state< Word, Machine>( تعزيز typedef::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, Boost::statechart::transition< Events:: Digit , States:: Skip >, Boost::statechart::transition< Events:: Unknown , States:: Skip >> ردود الفعل؛ ) ; تخطي البنية: Boost::statechart::simple_state< Skip, Machine>( تعزيز typedef::statechart::transition< Events:: Space , States:: Start >تفاعلات؛

) ; )

تم بناء الجهاز، كل ما تبقى هو تهيئته ويمكنك استخدامه:

نتيجة:

آلة الآلة Machine.initiate(); ... Machine.process_event(Events::Space());

المرونة وقابلية التوسع

- كفاءة

أداء

لقد كتبت برنامج اختبار للتحقق من أداء الآلات التي تم بناؤها. قمت بتشغيل نص يصل حجمه إلى 17 ميجابايت عبر الأجهزة. وفيما يلي نتائج الجولة:

تحميل النص طول النص: 17605548 بايت 0.19 ثانية كلمات تشغيل BoostMachine: 998002، الأرقام: 6816 0.73 ثانية كلمات تشغيل DynamicMachine: 998002، الأرقام: 6816 0.56 ثانية كلمات تشغيل FastDynamicMachine: 998002، الأرقام: 6816 0.29 ثانية تشغيل SimpleMachine الكلمات: 998002، الأرقام: 6816 0.20 ثانية

لا يزال هناك العديد من تطبيقات أجهزة الحالة المحدودة التي تركت مكشوفة (أوصي بـ http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml و http://www.rsdn.ru/article/alg/FiniteStateMachine.xml) والمولدات التي تبني الآلات من الأوصاف، ومكتبة Meta State Machine من Boost الإصدار 1.44.0، بالإضافة إلى الأوصاف الرسمية لآلات الحالة المحدودة. يمكن للقارئ الفضولي أن يتعرف على كل ما سبق بنفسه.

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

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

دعونا نعطي بعض الأمثلة على آلات الحالة المحدودة.

مثال 1. عنصر التأخير (عنصر الذاكرة).

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

لنفترض أن أبجدية الإدخال، وبالتالي الإخراج، هي X ={0, 1}, ي =(0، 1). ثم س =(0، 1). في ظل حالة عنصر التأخير في ذلك الوقت ر يتم فهم محتوى عنصر الذاكرة في لحظة معينة. هكذا س (ر )= X (ر -1)، أ ي (ر )= س (ر )=X (ر 1).

لنقم بتعيين عنصر التأخير بجدول حيث أ 1 =0, أ 2 =1, س 1 =0, س 2 =1,

(أ 1 , س 1)= (0, 0)=0,  (أ 1 , س 1)= (0, 0)=0;

(أ 1 , س 2)= (0, 1)=0,  (أ 1 , س 2)= (0, 1)=1;

(أ 2 , س 1)= (1, 0)=1,  (أ 2 , س 1)= (1, 0)=0;

(أ 2 , س 2)= (1, 1)=1,  (أ 2 , س 2)= (1, 1)=1;

س أ
	=0,  =0	=0,  =1
	=1,  =0	=1,  =1

يظهر مخطط مور في الشكل. 3

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

دعونا ننتبه إلى حقيقة ذلك ر = ع = ص =2. ثم ك =ص =س =1، وبالتالي يتم إعطاء عنصر التأخير بواسطة وظيفتين  و  . يحتوي جدول الحقيقة لهذه الوظائف على 2 ك + ص =2 2 =4 خطوط و ك +ص +ص +س =4 أعمدة:

س	ض

مثال 2. المضاف المتسلسل الثنائي.

هذا المجمع المتسلسل هو جهاز يضيف رقمين في النظام الثنائي. يتم توفير الأرقام لمدخلات الأفعى X 1 و س 2، بدءًا من الأرقام الأقل أهمية. ينشئ الإخراج تسلسلًا يتوافق مع إدخال الرقم X 1 +س 2 في النظام الثنائي (الشكل 4).

يتم تعريف أبجديات الإدخال والإخراج بشكل فريد: X ={00; 01; 10; 11}, ي =(0,1). يتم تحديد مجموعة الحالات من خلال القيمة المحمولة عند إضافة الأرقام المقابلة من الأرقام X 1 و س 2. إذا تم تشكيل حمل عند إضافة بعض البتات، فسوف نفترض أن الأفعى قد دخل الحالة س 1 . في حالة عدم وجود حمل، سنفترض أن الأفعى في الحالة س 0 .

يتم تحديد الأفعى بواسطة جدول.

س أ	س 0	س 1
	س 0 , 0	س 0 , 1
	س 0 , 1	س 1 , 0
	س 0 , 1	س 1 , 0
	س 1 , 0	س 1 , 1

يظهر مخطط مور للمجمع المتسلسل في الشكل. 5.

لاحظ أن رموز الإدخال والإخراج مشفرة بالفعل. نقوم بتشفير الحالات على النحو التالي:  (س 0)=0,  (س 1)=1. لذلك، يتم تحديد الجامع المتسلسل بواسطة دالتين منطقيتين، جدول الحقيقة الخاص بهما هو كما يلي:

س 1	س 2	ض

مثال 3. مخطط مقارنة المساواة.

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

لهذا الجهاز X ={00, 01, 10, 11}; ي ={0,1}.

يتم تحديد عمل الدائرة من خلال حالتين. ولاية س 0 يتوافق مع المساواة بين الأرقام المقارنة حاليا. في هذه الحالة، يبقى الجهاز في نفس الحالة. إذا كانت الأرقام المقارنة مختلفة في اللحظة التالية، فسوف ينتقل الجهاز إلى حالة جديدة س 1 ويبقى فيه، لأن هذا يعني أن الأرقام مختلفة. وبالتالي، يمكن تحديد مخطط المقارنة من خلال الجدول:

س س	س 0	س 1
	س 0 , 0	س 1 , 1
	س 1 , 1	س 1 , 1
	س 1 , 1	س 1 , 1
	س 0 , 0	س 1 , 1

يظهر مخطط مور لمخطط مقارنة المساواة في الشكل. 6.

سنقوم بتشفير الحالات على النحو التالي:  (س 0)=0,  (س 1)=1. سيتم تحديد الجهاز بوظيفتين.

س 1	س 2	ض

مثال 4. مخطط مقارنة عدم المساواة.

دائرة مقارنة المتباينات هي جهاز يسمح لك بمعرفة ما إذا كانت الأشياء التي تتم مقارنتها متساوية. X 1 و س 2، وإذا لم يكونا متساويين، فانظر أيهما أكبر من الآخر. يحتوي هذا الجهاز على مدخلين ومخرجين. إشارات الإخراج ذ 1 (ر ) و ذ 2 (ر ) يتم تحديدها وفقا للقواعد التالية:

ذ 1 (ر )=ذ 2 (ر )=0 إذا س 1 (ر )=س 2 (ر );

ذ 1 (ر )=1, ذ 2 (ر )=0 إذا س 1 (ر )>س 2 (ر )، إنه س 1 (ر )=1, س 2 (ر )=0;

ذ 1 (ر )=0, ذ 2 (ر )=1، إذا س 1 (ر )<س 2 (ر )، إنه س 1 (ر )=0, س 2 (ر )=1.

وهكذا، عند تغذية مدخلات دائرة المقارنة لعدم المساواة في الأرقام س 1 =س 1(ل)… س 1 (ر ) و س 2 =س 2(ل)… س 2 (ر ) تتم مقارنة أرقام هذه الأرقام بالتسلسل، بدءًا من الأرقام الأكثر أهمية. تتم صياغة إشارات الإخراج وفقًا للقواعد المذكورة أعلاه. علاوة على ذلك، إذا كان تسلسل الإخراج يتكون من أزواج صفرية، إذن س 1 =س 2. إذا كان الزوج الأول غير الصفري له النموذج , () الذي - التي س 1 >س 2 (س 1 <س 2).

من وصف الدائرة يتبع ذلك

X ={00, 01, 10, 11}, ي ={00, 01, 10}.

يتم تحديد حالة الدائرة على النحو التالي. لنفترض أنه في اللحظة الأولى من الزمن ر =1 آلة في الدولة س 1 . إذا كانت الأرقام المقارنة من الأرقام X 1 و X 2 يتزامن، ثم يبقى الجهاز في هذه الحالة. لاحظ أن إشارة 00 ستظهر عند الإخراج إذا كان رقم الرقم X 1 سيكون أقل (أكبر) من الرقم المقابل للرقم X 2، ثم الجهاز سوف يذهب إلى الدولة س 2 (س 3). في هذه الحالة، ستظهر الإشارة 01 (10) عند الخرج. وبعد ذلك، عند تقديم الأرقام المتبقية من الأرقام X 1 و X 2 إلى مدخلات الجهاز، سيبقى الجهاز في الحالة س 2 (س 3) وإنشاء رمز الإخراج 10 (01). ويترتب على ما سبق أنه يمكن تحديد مخطط المقارنة للمتباينة من خلال الجدول:

س س	س 1	س 2	س 3
	س 1 , 00	س 2 , 01	س 3 , 10
	س 2 , 01	س 2 , 01	س 3 , 10
	س 3 , 10	س 2 , 01	س 3 , 10
	س 1 , 00	س 2 , 01	س 3 , 10

يظهر مخطط مور المقابل في الشكل. 7.

تم بالفعل ترميز أبجديات الإدخال والإخراج هنا. تنص على س 1 , س 2 و س دعونا تشفير 3:  1 (س 1)=00,  (س 2)=01,  (س 3)=10.

لذلك يمكن تحديد هذه الدائرة بنظام يتكون من أربع دوال منطقية تعتمد على أربعة متغيرات. يتم تعريف هذه الوظائف جزئيًا وإعطاؤها بواسطة جدول الحقيقة

	س 1	س 2	ض 1	ض 2

في الجدول، تشير الرموز * إلى مجموعات من المتغيرات س 1 , س 2 , ض 1 , ض 2 التي عليها الوظائف  1 ,  2 ,  1 ,  2 لم يتم تعريفها. هيا نضع قيم الوظيفة  1 ,  2 ,  1 ,  2 في هذه المجموعات يساوي 1.

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

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

معرفة ما يحتاجه العميل.

إنشاء مخطط انتقال الدولة

قم بتشفير "الهيكل العظمي" لجهاز الحالة دون تفصيل عمليات الفرع.

تأكد من أن التحولات تعمل بشكل صحيح.

كن محددًا بشأن تفاصيل الانتقال.

خذ الاختبار.

مثال آلة الدولة

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

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

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

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

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

عند إنشاء مخطط انتقال الحالة (أو أي خوارزمية أخرى)، ضع ما يلي في الاعتبار:

تعمل أجهزة الكمبيوتر بسرعة كبيرة مقارنة بالمعدات الميكانيكية

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

كيف سيتصرف برنامجك إذا انكسر جزء ميكانيكي أو كهربائي؟

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

تنفيذ آلة الدولة المحدودة

القائمة 1 هي تطبيقي لآلة الحالة الموضحة في الشكل 3. دعونا نناقش بعض تفاصيل الكود.

/*القائمة 1*/

تعداد typedef(GEAR_DOWN = 0، WTG_FOR_TKOFF، RAISING_GEAR، GEAR_UP، LOWERING_GEAR) نوع_الحالة؛

/*يحتوي هذا المصفوفة على مؤشرات للوظائف التي يتم استدعاؤها في حالات معينة*/

فارغ(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

State_Type curr_state؛

تهيئةLdgGearSM();

/*قلب الآلة هو هذه الحلقة التي لا نهاية لها. وظيفة المقابلة

الحالة الحالية، يتم استدعاؤها مرة واحدة لكل تكرار */

بينما (1) {

State_table();

DecrementTimer();

فارغتهيئةLdgGearSM( فارغ )

curr_state = GEAR_DOWN;

/*إيقاف المعدات، وإطفاء الأضواء، وما إلى ذلك.*/

فارغجير داون( فارغ )

/* انتقل إلى حالة الانتظار إذا كانت الطائرة

لم يكن على الأرض وتلقى الأمر برفع جهاز الهبوط*/

لو((gear_lever == UP) && (prev_gear_lever == DOWN) && (squat_switch == UP)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = gear_lever;

فارغرايزينج جير( فارغ )

لو((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/*إذا غيّر الطيار قراره، انتقل إلى حالة "جهاز الهبوط السفلي"*/

لو(gear_lever == للأسفل) (

curr_state = LOWERING_GEAR;

فارغاستعد( فارغ )

/*إذا قام الطيار بتحريك الرافعة إلى الوضع "لأسفل"،

نذهب إلى حالة "خفض جهاز الهبوط"*/

لو(gear_lever == للأسفل) (

curr_state = LOWERING_GEAR;

فارغوتغفورتاكيوف( فارغ )

/* انتظر قبل رفع جهاز الهبوط.*/

لو(مؤقت<= 0.0) {

curr_state = RAISING_GEAR;

/*إذا لمسنا مرة أخرى أو غير الطيار رأيه، ابدأ من جديد*/

لو((squat_switch == DOWN) || (gear_lever == DOWN)) (

curr_state = GEAR_DOWN;

/* لا أريد أن أطلب منه تبديل الرافعة مرة أخرى

كان هذا مجرد ارتداد.*/

prev_gear_lever = DOWN;

فارغخفض العتاد( فارغ )

لو(gear_lever == UP) (

curr_state = RAISING_GEAR;

لو((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

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

لتجنب استخدام عبارة التبديل، أستخدم مصفوفة من المؤشرات لتوضيح الوظائف، وأعلن أن المتغير المستخدم كمؤشر للمصفوفة هو من النوع enum.

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

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

مفتاح النجاح يكمن في الكود الذي يسبب انتقال الحالة، أي. يحدد أن إدخال البيانات قد حدث.

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

في جدول انتقال الحالة، يوجد صف واحد لكل انتقال حالة.

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

يقوم مقتطف الكود الموجود في القائمة 2 بتوسيع وظيفة RaisingGear(). لاحظ أن كود الدالة RaisingGear() يهدف إلى عكس صفين من جدول الانتقال لحالة RaisingGear.

فارغرايزينج جير( فارغ )

/*بعد رفع جميع المفاتيح، ننتقل إلى حالة "رفع الهيكل"*/

لو((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

Pump_motor = OFF؛

gear_lights = EXTINGUISH;

curr_state = GEAR_UP;

/*إذا غيّر الطيار رأيه، ابدأ في سحب جهاز الهبوط*/

لو(gear_lever == للأسفل) (

Pump_direction = DOWN;

curr_state = GEAR_LOWERING;

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

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

اختبار آلة الدولة

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

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

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

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

يطلق

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

مارتن جوميز هو مبرمج في مختبر الفيزياء التطبيقية بجامعة جونز هوبكنز. تشارك في تطوير البرمجيات لدعم رحلات المركبات الفضائية البحثية. عملت في مجال تطوير الأنظمة المدمجة لمدة 17 عاما. يحمل مارتن بكالوريوس العلوم في هندسة الطيران وماجستير العلوم في الهندسة الكهربائية من جامعة كورنيل.