صفحه 1:
صفحه 2:
Guile بوچی: ماشین متناهیای است که عبارات نامتناهی را میپذیرد
رد که میتواند برای ساخت الگو
Linear Temporal Logic)
در ادامه خواهیم دید که ماشین بوچی.
(Model Checking Algorithm) )اانا
صفحه 3:
زبانهلی لمگل()
هر مجموعه از رشتههای به
Ree ren a
مشخص. بك زبان امكا بر
70
يك زبان امگا معادل با
eal است
۱
صفحه 4:
و و
Font Symbol
زبان میتواند نامتناهه, باشد.
مشکلات.
تشخیص, ز
با
ن,هلی 1
صفحه 5:
gl کاربردهلی, 9 Sol ماشين.
تصديق سيستهها و محاسبات استفاده كرد.
صفحه 6:
(LINEAR TEMPORAL LOGIC),5h> منطق, موقت.
malas
منط
Tempe is, —
یرم 7
Lo 12 aa
LOGIC 4
صفحه 7:
صفحه 8:
صفحه 9:
صفحه 10:
زبان. ماشین, بوچی
بانی که توسط ماشین بوچی پذیرفته میشود:
بكر یک قبول که بضعیت در اجرای . بینهایت بار ظاهر شود.
به تعبیری دیگرء یک وضعیت زمانی مورد قبول است که آن وضعیت در اجرای ۰ بینهایت بار ظاهر شو
صفحه 11:
نامحدودی از الفبای [0,6 ,8) را میپذیرد.
هیچگاه نمیتوان دنباله», نامحدود ۰..360666 :۱ تولند کرد. (مسب نامعتب)
صفحه 12:
۲۱۱۱ لنحصار متقلبل(۲۱۵۱ J>
(EXCLUSION
* اگر فرآیندهای 1 یا 2 و یا هیچکدام در ناحیهی بحرانی خود نباشند. پذیرش و اگر هر دو همزمان
بذ
Mutax
صفحه 13:
اشير است با تمام عبا امتناهی که
ی i
b 1 \ 4, ) la
٠١ a
صفحه 14:
با
b
۱
@
ماشین بوچی غیرقطعی(۱۱5۸)
b
در آنها بینهایت بار حرف ۵ آمده باشد.
2.0 ۱
صفحه 15:
فرض کنید ایک ماشین بوچی متناهی باشد..در ul ضورت یک تعمیم طبیعی از
میتواند مطرح شود که به لین صوزت است که یک اجرا روی یک عبارت نامتناهی
میکنيم و با به وسپس با به و .. مىرويم. به عنوان مثال در اين ماشين.
Eel sl este ee
در این صورت میگوییم:
ماشین رشته را قبول میکند اگر اجرایی وجود داشته باشد که در آن حداقل یکی از حالات قبول را به تعداد نامتناهی دیده باشیم.
در ماشین بوچی غیرقطعی به جای تلبع انتقال. رابطمی انتقال مطرح است و مانند هر حللت» تحت رابطهی انتقال به مجموعهای |
حالات منجر میشود و به جای حالت آغازی مجموعه از حالات ابتدلیی در نظر گر
بوچی را به تنهایی به کار میبریم» منظورمان ماشین بوچی غیرقطعی stu! (NBA)
میشود. در حللت کلی وقتی کلمه ماشین
صفحه 16:
ویژگیهلی. ملشین, بوچی
)...= @ ©
.228 @ )»
Cae ۰ ©
اتصال بوج اشين بوجى
هي ©
صفحه 17:
FSM VS BUCHI
FM oe 3
تشخیص عبارات متناهی
ae ۲ NEAL ean eeDeA ۲ ۸۵ و 1۳۸۵ دارای قدرت
کل مجموعه زبانهاي منظم را میبذ برد 2 تشخیص یکسان هستند
صفحه 18:
منلبع و مراجع
Rich, Elaine. Automata, Computability and Complexity Theory and
Applications. Upper Saddle River (N. J.) Pearson Prentice Hall, 2008. Print.
صفحه 19: