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

در نظریه ماشین‌ها و ترتیبی منطق، یک جدول انتقال حالت یک جدول نشان دادن آنچه حالت است (و یا می‌گوید در مورد یک ماشین متناهی غیرقطعی) دستگاه نیمه محدود یا ماشین حالت محدود به حرکت، بر اساس جریان ورودی حالت و دیگر. جدول حالت در اصل یک جدول درستی است که در آن برخی از ورودی‌ها می‌باشد وضعیت فعلی و خروجی‌ها شامل حالت بعدی، همراه با خروجی‌های دیگر. جدول حالت یکی از راه‌های بسیاری برای مشخص کردن یک دستگاه حالت، از راه‌های دیگر به عنوان یک نمودار حالت و معادله مشخصه است.

فرمهای متداول

جداول حالت یک بعدی

همچنین جداول مشخصه نامیده می‌شود، جداول حالت تک بعدی هستند بسیار بیشتر مانند جداول حقیقت نسبت به نسخه دو بعدی. ورودی معمولاً در سمت چپ قرار داده شده، و جدا از خروجی، که در سمت راست می‌باشد . خروجی حالت بعدی از دستگاه ایجاد خواهد کرد. یک مثال ساده از یک ماشین حالت با دو کشور و دو ورودی ترکیبی زیر است:

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

S₁ و S₂ به احتمال زیاد نشان دهنده تک بیت 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 دستگاه همراه با نمودار حالت متناظر زیر آورده شده‌است.

جدول حالت گذار   ورودی حالت 1 0 S1 S1 S2 S2 S2 S1

State Diagram

همه ورودی‌های ممکن برای دستگاه‌ها در سراسر ستون از جدول را برشمرده است. تمام حالات ممکن در سراسر ردیف را برشمرده است. از جدول انتقال حالت داده شده در بالا، از آن آسان است برای دیدن است که اگر دستگاه در S₁ (سطر اول) و ورودی بعدی کاراکتر 1 باشد، دستگاه در S₁ خواهد ماند. اگر یک کاراکتر 0 می‌رسد، دستگاه را به S₂ انتقال به عنوان را می‌توان از ستون دوم دیده می‌شود. در نمودار این است که توسط فلش از S₁ به S₂ نشاندار شده با 0 نشان داده می‌شود. برای یک ماشین متناهی غیرقطعی (NFA)، یک ورودی جدید ممکن است باعث شود تا دستگاه در بیش از یک حالت باشد، از این رو خود را غیر جبر. این است که در جدول انتقال حالت توسط یک جفت آکولاد {} با مجموعه ای از تمام کشورهای مورد نظر بین آن‌ها می‌شود. یک مثال در زیر آورده شده‌است.

جدول حالت گذار برای 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

[[دسته بندی:نظریه ماشینها]]