ماشین پشته ای

در این ویدئوی آموزشی قصد داریم به بررسی مبحث ماشین پشته ای در درس نظریه زبان ها و ماشین ها بپردازیم.

کیفیت فیلم بصورت پیش فرض بر روی حالت low تنظیم شده است و شما می توانید با استفاده از تنظیمات موجود، این آموزش را با بالاترین کیفیت مشاهده نمایید.

شما می توانید با استفاده از گزینه “متن فیلم”، متن مربوط به حل سوال را مشاهده کنید.

//******************************************************************************************************************************************//

پیشنهاد می شود قبل از مشاهده این آموزش مروری بر مبحث ماشین های پشته ای داشته باشید. انتظار می رود شما بعد از مشاهده این آموزش درک مناسبی از این مبحث

به دست آورید.

یک ماشین پشته ای ، بصورت یک هفت تایی مرتب نشان داده می شود.

واضح است که PDA یک NFA به همراه پشته است.

همانطور که مشاهده می شود تابع انتقال در این ماشین در سمت چپ با توجه به وضعیت ماشین، الفبای ورودی و عنصر بالای پشته به وضعیت جدید و جایگزینی عنصر بالای پشته در سمت راست است.

بعنوان مثال، در این تابع انتقال، ماشین از حالت q با ورودی a و X بعنوان بالاترین عنصر پشته به وضعیت p و حذف X و اضافه کردن Y به بالای پشته تغییر وضعیت می دهد.

همانطور که میدانیم: یک رشته زمانی به وسیله یک PDA پذیرفته می‌شود، اگر زمانی که رشته ورودی به انتها رسید ماشین در یکی از وضعیت‌های نهایی خود باشد.

برای پذیرفتن یک رشته بعد از پویش کامل ورودی، پشته می تواند خالی باشد.

از دیاگرام حالت برای نمایش ماشین می توان استفاده کرد.

همچنین از توصیف بلافصل برای پویش رشته ورودی می توان استفاده کرد.

برای مثال، به ازای خواندن یک حرف از ورودی با توجه به حالت فعلی ماشین و وضعیت پشته، ماشین به وضعیتی جدید و کم کردن این حرف از رشته ورودی می رود.

با توصیف بلافصل می توان مرحله به مرحله وضعیت ماشین را برای پویش رشته نشان داد.

دیاگرام حالت نمادی گرافیکی از نمایش تغییر وضعیت‌های ماشین با شرایط مختلف ورودی و وضعیت پشته است.

با توجه به مثال مشاهده می شود که ماشین در وضعیت qi با ورودی a و بودن x در بالای پشته ، x را حذف و Y را جایگزین می کند و به وضعیت qj می رود.

یک ماشین پشته ای، قطعی است اگر:

1. (δ(q,a,X به ازای هر حرف الفبا حداکثر دارای یک مقدار باشد، و اگر

       ۲. (δ(q,λ,X وجود داشته باشد، δ(q,a,X)  وجود نداشته باشد.

برای مسئله توازن پرانتزها یک ماشین پشته ای طراحی کنید.

همانطور که در مثال خواسته شده است الفبای ماشین شامل دو ورودی پرانتز باز و پرانتز بسته می شود.

در مسئله توازن پرانتزها، λ جزء رشته های پذیرفته شده توسط این زبان است چون دارای هیچ پرانتز باز یا بسته نمی شود. همچنین باید به ازای هر پرانتز باز یک پرانتز بسته وجود داشته باشد یا به عبارت دیگر تعداد آنها با هم برابر باشد. به ازای هر پرانتز بسته باید یک پرانتز باز از قبل وجود داشته باشد. به ازای هر پرانتز باز هم باید یک پرانتز بسته در ادامه وجود داشته باشد.

ماشین در حالت q0 فقط ) را می تواند دریافت کند و به ازای هر پرانتز باز یک ) در پشته پوش می شود.

در زمانی که ( بعنوان حرف نوار ورودی باشد ماشین از حالت q0 به حالت q1 رفته و یک پرانتز باز را از پشته پاپ می کند. و هر گاه دو باره پرانتز باز دیده شد به حالت q0 بر می گردد.

با تمام شدن رشته ورودی اگر پشته هم خالی باشد می توان به حالت q2 که حالت نهایی ماشین است رفت.

λ , Z_۰   / Z_۰ در تمام ماشین در جهت پذیرفتن λ توسط این ماشین پشته ای است.

الفبای پشته z0 و ( است و ماشین از سه حالت q_۰ و q1 و q_۲ تشکیل شده است.