جدول انتقال حالت
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. (آوریل ۲۰۱۴) |
در نظریه ماشینها و ترتیبی منطق، یک جدول انتقال حالت یک جدول نشان دادن آنچه حالت است (و یا می‌گوید در مورد یک ماشین متناهی غیرقطعی) دستگاه نیمه محدود یا ماشین حالت محدود به حرکت، بر اساس جریان ورودی حالت و دیگر. جدول حالت در اصل یک جدول درستی است که در آن برخی از ورودی‌ها می‌باشد وضعیت فعلی و خروجی‌ها شامل حالت بعدی، همراه با خروجی‌های دیگر. جدول حالت یکی از راه‌های بسیاری برای مشخص کردن یک دستگاه حالت، از راه‌های دیگر به عنوان یک نمودار حالت و معادله مشخصه است.
فرمهای متداول
[ویرایش]جداول حالت یک بعدی
[ویرایش]همچنین جداول مشخصه نامیده می‌شود، جداول حالت تک بعدی هستند بسیار بیشتر مانند جداول حقیقت نسبت به نسخه دو بعدی. ورودی معمولاً در سمت چپ قرار داده شده، و جدا از خروجی، که در سمت راست می‌باشد . خروجی حالت بعدی از دستگاه ایجاد خواهد کرد. یک مثال ساده از یک ماشین حالت با دو کشور و دو ورودی ترکیبی زیر است:
| A | B | حالت کنونی | حالت بعدی | خروجی |
|---|---|---|---|---|
| 0 | 0 | S1 | S2 | 1 |
| 0 | 0 | S2 | S1 | 0 |
| 0 | 1 | S1 | S2 | 0 |
| 0 | 1 | S2 | S2 | 1 |
| 1 | 0 | S1 | S1 | 1 |
| 1 | 0 | S2 | S1 | 1 |
| 1 | 1 | S1 | S1 | 1 |
| 1 | 1 | S2 | S2 | 0 |
S1 و S2 به احتمال زیاد نشان دهنده تک بیت 0 و 1، از یک بیت فقط می‌تواند دو حالت داشته باشد
جداول حالت دو بعدی
[ویرایش]جداول گذار حالت جداول دو بعدی می‌باشد به‌طور معمول. دو نوع رایج برای تنظیم آن‌ها وجود دارد. - عمودی (یا افقی) بعد نشان می‌دهد ایالات در حال حاضر، بعد افقی (یا عمودی) نشان می‌دهد وقایع، و سلول (تقاطع سطر / ستون) در جدول شامل حالت بعدی اگر یک رویداد رخ می‌دهد (و احتمالاً اقدام مربوط به این حالت انتقال).
| حالت وقوع |
E1 | E2 | ... | En |
| S1 | - | Ay/Sj | ... | - |
| S2 | - | - | ... | Ax/Si |
| ... | ... | ... | ... | ... |
| Sm | Az/Sk | - | ... | - |
s: حالت e: واقعه a: عمل یا حرکت: انتقال غیرقانونی
بعد عمودی (یا افقی) نشان می‌دهد ایالات در حال حاضر، بعد افقی (یا عمودی) نشان می‌دهد حالت‌های بعدی، و تقاطع سطر / ستون حاوی این رویداد است که به حالت بعدی خاص منجر خواهد شد.
| جریان بعدی |
S1 | S2 | ... | Sm |
| S1 | - | - | ... | Ax/Ei |
| S2 | Ay/Ej | - | ... | - |
| ... | ... | ... | ... | ... |
| Sm | - | Az/Ek | ... | - |
s: حالت e: واقعه a: عمل یا حرکت: انتقال غیرقانونی
اشکال دیگر
[ویرایش]انتقال همزمان در چندین دستگاه حالت محدود را می‌توان در آن چیزی است که به‌طور مؤثر یک حالت جدول انتقال n بعدی نشان داده شده‌است که در آن جفت از نقشه ردیف (مجموعه) ایالات در حال حاضر به حالت‌های بعدی. این یک جایگزین به نمایندگی از ارتباط بین جداگانه، ماشین‌های به هم وابسته است. در دیگر، جداول جداگانه برای هر یک از انتقال در دستگاه حالت واحد استفاده شده‌است: "AND / OR جدول" شبیه به جدول تصمیم گیری ناقص است که در آن تصمیم‌گیری برای قوانین است که حاضر است به‌طور ضمنی فعال شدن مرتبط انتقال.
مثال
[ویرایش]نمونه ای از یک جدول انتقال حالت را برای M دستگاه همراه با نمودار حالت متناظر زیر آورده شده‌است.
|
State Diagram
|
همه ورودی‌های ممکن برای دستگاه‌ها در سراسر ستون از جدول را برشمرده است. تمام حالات ممکن در سراسر ردیف را برشمرده است. از جدول انتقال حالت داده شده در بالا، از آن آسان است برای دیدن است که اگر دستگاه در S1 (سطر اول) و ورودی بعدی کاراکتر 1 باشد، دستگاه در S1 خواهد ماند. اگر یک کاراکتر 0 می‌رسد، دستگاه را به S2 انتقال به عنوان را می‌توان از ستون دوم دیده می‌شود. در نمودار این است که توسط فلش از S1 به S2 نشاندار شده با 0 نشان داده می‌شود. برای یک ماشین متناهی غیرقطعی (NFA)، یک ورودی جدید ممکن است باعث شود تا دستگاه در بیش از یک حالت باشد، از این رو خود را غیر جبر. این است که در جدول انتقال حالت توسط یک جفت آکولاد {} با مجموعه ای از تمام کشورهای مورد نظر بین آن‌ها می‌شود. یک مثال در زیر آورده شده‌است.
| ورودی حالت |
1 | 0 | ε |
| S1 | S1 | { S2, S3 } | Φ |
| S2 | S2 | S1 | Φ |
| S3 | S2 | S1 | S1 |
تبدیل به نمودار حالت
[ویرایش]ممکن است که یک نمودار حالت را به منظور جلب از جدول. دنباله ای از آسان به دنبال مراحل زیر آورده شده‌است: 1- کشیدن مدار به نمایندگی حالت داده شده‌است. 2- برای هر یک از حالت‌ها، اسکن در سراسر ردیف مربوطه و جلب فلش به حالت مقصد (ها). می‌توان فلش‌های متعدد برای یک کاراکتر ورودی وجود دارد اگر ماشین NFA است. 3- تعیین یک حالت به عنوان حالت شروع می‌شود. حالت آغاز شده‌است در تعریف رسمی از ماشین خودکار داده می‌شود. 4- تعیین یک یا چند حالت به عنوان حالت شرایط. این نیز در تعریف رسمی داده شده‌است.
منابع
[ویرایش]- Breen, Michael (2005), "Experience of using a lightweight formal specification method for a commercial embedded system product line"
, Requirements Engineering Journal 10 (2), doi:10.1007/s00766-004-0209-1
- Leveson, Nancy; Heimdahl, Mats Per Erik; Hildreth, Holly; Reese, Jon Damon (1994), "Requirements Specification for Process-Control Systems"
IEEE Transactions on Software Engineering 20 (9), doi:10.1109/32.317428
منابعی برای مطالعات بیشتر
[ویرایش]- Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X