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

در نظریه ماشینها و ترتیبی منطق، یک جدول انتقال حالت یک جدول نشان دادن آنچه حالت است (و یا می‌گوید در مورد یک ماشین متناهی غیرقطعی) دستگاه نیمه محدود یا ماشین حالت محدود به حرکت، بر اساس جریان ورودی حالت و دیگر.جدول حالت در اصل یک جدول درستی است که در آن برخی از ورودی‌ها می‌باشد وضعیت فعلی و خروجیها شامل حالت بعدی، همراه با خروجی‌های دیگر.
جدول حالت یکی از راه‌های بسیاری برای مشخص کردن یک دستگاه حالت، از راه‌های دیگر به عنوان یک نمودار حالت و معادله مشخصه است.
فرمهای متداول
جداول حالت یک بعدی
همچنین جداول مشخصه نامیده می‌شود، جداول حالت تک بعدی هستند بسیار بیشتر مانند جداول حقیقت نسبت به نسخه دو بعدی. ورودی معمولا در سمت چپ قرار داده شده، و جدا از خروجی، که در سمت راست می‌باشد. خروجی حالت بعدی از دستگاه ایجاد خواهد کرد. یک مثال ساده از یک ماشین حالت با دو کشور و دو ورودی ترکیبی زیر است:
A
B
حالت کنونی
حالت بعدی
خروجی
0
0
S 1
S 2
1
0
0
S 2
S 1
0
0
1
S 1
S 2
0
0
1
S 2
S 2
1
1
0
S 1
S 1
1
1
0
S 2
S 1
1
1
1
S 1
S 1
1
1
1
S 2
S 2
0
S 1 و S 2 به احتمال زیاد نشان دهنده تک بیت 0 و 1، از یک بیت فقط می‌تواند دو حالت داشته باشد
جداول حالت دو بعدی
جداول گذار حالت جداول دو بعدی می‌باشد به طور معمول. دو نوع رایج برای تنظیم آنها وجود دارد.
- عمودی (یا افقی) بعد نشان می‌دهد ایالات در حال حاضر، بعد افقی (یا عمودی) نشان می‌دهد وقایع، و سلول (تقاطع سطر / ستون) در جدول شامل حالت بعدی اگر یک رویداد رخ می‌دهد (و احتمالا اقدام مربوط به این حالت انتقال).
+ جدول حالت گذار
حالتوقوع
E 1
E 2
E n
S 1
A y /S j
S 2
A x /S i
S m
A z /S k
s: حالت e: واقعه a: عمل یا حرکت: انتقال غیرقانونی
بعد عمودی (یا افقی) نشان می‌دهد ایالات در حال حاضر، بعد افقی (یا عمودی) نشان می‌دهد حالت‌های بعدی، و تقاطع سطر / ستون حاوی این رویداد است که به حالت بعدی خاص منجر خواهد شد.
+ جدول حالت گذار
جریانبعدی
S 1
S 2
S m
S 1
A x /E i
S 2
A y /E j
S m
A z /E k
s: حالت e: واقعه a: عمل یا حرکت: انتقال غیرقانونی
اشکال دیگر
انتقال همزمان در چندین دستگاه حالت محدود را می‌توان در آن چیزی است که به طور موثر یک حالت جدول انتقال n بعدی نشان داده شده است که در آن جفت از نقشه ردیف (مجموعه) ایالات در حال حاضر به حالت‌های بعدی. این یک جایگزین به نمایندگی از ارتباط بین جداگانه، ماشین‌های به هم وابسته است.
در دیگر، جداول جداگانه برای هر یک از انتقال در دستگاه حالت واحد استفاده شده است: "AND / OR جدول" شبیه به جدول تصمیم گیری ناقص است که در آن تصمیم گیری برای قوانین است که حاضر است به طور ضمنی فعال شدن مرتبط انتقال.
مثال
نمونه‌ای از یک جدول انتقال حالت را برای M دستگاه همراه با نمودار حالت متناظر زیر آورده شده است.
+ جدول حالت گذار
ورودیحالت
1
0
S 1
S 1
S 2
S 2
S 2
S 1
State Diagram DFAexample.svg
همه ورودی‌های ممکن برای دستگاه‌ها در سراسر ستون از جدول را برشمرده است. تمام حالات ممکن در سراسر ردیف را برشمرده است. از جدول انتقال حالت داده شده در بالا، از آن آسان است برای دیدن است که اگر دستگاه در S 1 (سطر اول) و ورودی بعدی کاراکتر 1 باشد، دستگاه در S 1 خواهد ماند. اگر یک کاراکتر 0 می‌رسد، دستگاه را به S 2 انتقال به عنوان را می‌توان از ستون دوم دیده می‌شود. در نمودار این است که توسط فلش از S 1 به S 2 نشاندار شده با 0 نشان داده می‌شود.
برای یک ماشین متناهی غیرقطعی (NFA)، یک ورودی جدید ممکن است باعث شود تا دستگاه در بیش از یک حالت باشد، از این رو خود را غیر جبر. این است که در جدول انتقال حالت توسط یک جفت آکولاد { با مجموعه‌ای از تمام کشورهای مورد نظر بین آنها می‌شود. یک مثال در زیر آورده شده است.
+ جدول حالت گذار برای NFA
ورودیحالت
1
0

S 1
S 1
{ S 2 , S 3

S 2
S 2
S 1

S 3
S 2
S 1
S 1
تبدیل به نمودار حالت
ممکن است که یک نمودار حالت را به منظور جلب از جدول. دنباله‌ای از آسان به دنبال مراحل زیر آورده شده است:
1- کشیدن مدار به نمایندگی حالت داده شده است.
2- برای هر یک از حالت‌ها، اسکن در سراسر ردیف مربوطه و جلب فلش به حالت مقصد (ها). می‌توان فلش‌های متعدد برای یک کاراکتر ورودی وجود دارد اگر ماشین NFA است.
3- تعیین یک حالت به عنوان حالت شروع می‌شود. حالت آغاز شده است در تعریف رسمی از ماشین خودکار داده می‌شود.
4- تعیین یک یا چند حالت به عنوان حالت شرایط. این نیز در تعریف رسمی داده شده است.