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

الموسوعة الحرة

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

يُعد جدول انتقال الحالة أحد الطرق العديدة لتحديد آلة ذات حالات محدودة . ومن الطرق الأخرى مخطط الحالة .

الأشكال الشائعة

أحادي البعد

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

جدول انتقال الحالة (S: الحالة، I: المدخلات، O: المخرجات)
مدخلالوضع الحاليالولاية التاليةالناتج
أنا 1S 1S iO x
أنا 2S 1S jيا إلهي
............
في​S 1S kأونصة​
أنا 1S 2S i′O x′
أنا 2S 2S j′يا​
............
في​S 2S k′أو أونصة
............
أنا 1S mS i″O x″
أنا 2S mS j″يا ص
............
في​S mS k″O z″

ثنائي الأبعاد

عادةً ما تكون جداول انتقال الحالة جداول ثنائية الأبعاد. وهناك طريقتان شائعتان لترتيبها.

في الطريقة الأولى، يشير أحد الأبعاد إلى الحالات الحالية، بينما يشير الآخر إلى المدخلات. وتشير تقاطعات الصفوف والأعمدة إلى الحالات التالية، وإلى المخرجات المرتبطة بانتقالات الحالة (اختيارياً).

جدول انتقال الحالة (S: الحالة، I: المدخلات، O: المخرجات)
مدخل
الوضع الحالي
أنا 1أنا 2...في​
S 1S i /O xS j /O y...S k /O z
S 2S i′ /O x′S j′ /O y′...S k′ /O z′
...............
S mS i″ /O x″S j″ /O z″...S k″ /O z″

في الطريقة الثانية، يشير أحد الأبعاد إلى الحالات الحالية، بينما يشير الآخر إلى الحالات التالية. وتشير تقاطعات الصفوف والأعمدة إلى المدخلات (والمخرجات اختيارياً) المرتبطة بانتقالات الحالة.

جدول انتقال الحالة (S: الحالة، I: المدخلات، O: المخرجات، —: غير مسموح به)
الولاية التالية
الوضع الحالي
S 1S 2...S m
S 1أنا / O x—...—
S 2——...أنا ج / أو ي
...............
S m—أنا ك / أو أوز...—

أشكال أخرى

يمكن تمثيل الانتقالات المتزامنة في عدة آلات ذات حالات محدودة بما يشبه جدول انتقالات الحالة ذي الأبعاد n ، حيث تربط أزواج الصفوف (مجموعات من) الحالات الحالية بالحالات التالية. [ 1 ] وهذا بديل لتمثيل التواصل بين آلات ذات حالات محدودة منفصلة ومترابطة.

وعلى النقيض من ذلك، تم استخدام جداول منفصلة لكل انتقال داخل آلة حالة محدودة واحدة: "جداول AND/OR" [ 2 ] تشبه جداول القرار غير الكاملة التي يكون فيها القرار للقواعد الموجودة هو ضمنيًا تنشيط الانتقال المرتبط.

مثال

فيما يلي مثال على جدول انتقال الحالة مع مخطط الحالة المقابل لآلة ذات حالات محدودة تقبل سلسلة تحتوي على عدد زوجي من الأصفار:

جدول انتقال الحالة
مدخل
الوضع الحالي
01
S 1S 2S 1
S 2S 1S 2
مخطط الحالة
مخطط حالة آلة الحالة المحدودة

في جدول انتقال الحالة، تُدرج جميع المدخلات الممكنة لآلة الحالة المحدودة في أعمدة الجدول، بينما تُدرج جميع الحالات الممكنة في صفوفه. إذا كانت الآلة في الحالة S1 ( الصف الأول) وتلقت مدخلاً قيمته 1 (العمود الثاني)، فستبقى الآلة في الحالة S1 . أما إذا كانت الآلة في الحالة S2 وتلقت مدخلاً قيمته 0 (العمود الأول)، فستنتقل الآلة إلى الحالة S2 . في مخطط الحالة، يُرمز للحالة الأولى بسهم دائري من S1 إلى S2 مُرقّم بالرقم 1، بينما يُرمز للحالة الثانية بسهم من S1 إلى S2 مُرقّم بالرقم 0. يمكن وصف هذه العملية إحصائيًا باستخدام سلاسل ماركوف .

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

جدول انتقال الحالة
مدخل
الوضع الحالي
01
S 1S 2S 1
S 2{S 1 , S 2 }S 2
مخطط الحالة
مخطط حالة NFSM

إذا كانت الآلة في الحالة S 2 وتلقت مدخلات بقيمة 0، فستكون الآلة في حالتين في نفس الوقت، وهما الحالتان S 1 و S 2 .

التحولات من/إلى مخطط الحالة

من الممكن رسم مخطط الحالة من جدول انتقال الحالة. فيما يلي سلسلة من الخطوات السهلة المتابعة:

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

انظر أيضاً

مراجع

  1. ↑ برين، مايكل (2005)، "تجربة استخدام أسلوب مواصفات رسمي خفيف الوزن لخط إنتاج نظام مضمن تجاري" (ملف PDF) ، مجلة هندسة المتطلبات ، 10 (2): 161-172 ، CiteSeerX 10.1.1.60.5228 ، doi : 10.1007/s00766-004-0209-1 ، S2CID 16928695  
  2. ↑ ليفيسون، نانسي؛ هايمدال، ماتس بير إريك؛ هيلدريث، هولي؛ ريس، جون دامون (1994)، "مواصفات متطلبات أنظمة التحكم في العمليات" (ملف PDF) ، معاملات IEEE في هندسة البرمجيات ، 20 (9): 684-707 ، Bibcode : 1994ITSEn..20..684L ، CiteSeerX 10.1.1.72.8657 ، doi : 10.1109/32.317428 

للمزيد من القراءة

  • مايكل سيبسر: مقدمة في نظرية الحوسبة . دار نشر PWS، بوسطن 1997، رقم ISBN 0-534-94728-X