ماشین های پشته ای غیر قطعی (NPDA)

1396/3/26 محمدرضا احمدآبادی 1710

سلام . محمدرضا احمدآبادی هستم که با جلسه 22 آموزش نظریه زبان ها در خدمتتون هستم . امیدوارم تا به الان اوقات خوبی را پشت سر گذاشته باشید. سال نو را هم به شما تبریک گفته و امیدوارم سالی پر از موفقیت و شادابی در پیش رو داشته باشید . 
همان طور که میدانید کم کم  داریم به انتهای آموزش ها میرسیم و حداکثر سه یا چهار جلسه دیگر پرونده آموزش نظریه زبان هاراخواهیم بست.  امیدوارم تا به اینجا مطالب برایتان مفید بوده و بهره کافی از مطالب را برده باشید. امروز میخواهیم باهم درباره ماشین های پشته ای غیر قطعی ( NPDA ) باهم صحبت کنیم.
در ماشین های پشته ای نیز میتواند شرایط عدم قطعیت  وجود داشته باشد اما شرایط عدم قطعیت این ماشین ها با شرایط عدم قطعیت ماشین های متناهی متفاوت است . به طور مثال اگر یک حالت به ازای سمبل a بیش از یک انتقال داشته باشد  یا اینکه اصلا انتقال نداشته باشد نمی توان گفت که ماشین حتما غیر قطعی است . یک ماشین پشته ای زمانی غیر قطعی خواهد بود که در یک حالت با شرایط یکسان ( سمبل ورودی و سمبل بالای پشته) بیش از یک مورد برای تصمیم گیری وجود داشته باشد و یا اینکه در ماشین انتقال λ داشته باشیم که این λ به معنی λ انتهای رشته نباشد.
کاربرد این انتقالات  λ در ماشین های پشته ای مربوط به زمانی است که میخواهیم بدون توجه  به سمبل جاری رشته ورودی و فقط بادرنظر گرفتن بالای پشته تصمیم مناسب را اتخاذ کنیم که در این صورت از انتقال  λ استفاده میکنیم . در این نوع انتقال هد رشته ورودی هیچ حرکتی نمیکند . در این صورت ماشین پشته ای غیر قطعی خواهد بود.

نکته: ماشین های پشته ای غیر قطعی را نمیتوان به ماشین های پشته ای قطعی تبدیل کرد پس میتوان گفت توانایی NPDA  ها بیشتر از PDA ها می باشد.
مثال: 
 


اگه بخواهیم برای این زبان ماشین پشته ای رسم کنیم ایده ای که باید پیاده سازی کنیم خواهد بود: به ازای هر سمبلی که میبینم باید بالای پشته همان سمبل را push کنم تا زمانی که به λ میان رشته یا سمبل a یا b وسط رشته برسم زمانی که به این سمبل رسیدم باید از سمبل بعد ازآن به شرط اینکه سمبل جاری رشته که دارم مشاهده میکنم با سمبل بالای پشته یکسان باشد از بالای پشته عمل pop را انجام میدهم. تا زمانی که به انتهای رشته جاری برسم و همزمان پشته هم خالی شده باشد انگاه میتوان گفت این ماشین رسم شده مربوط به رشته های مورد پذیرش این زبان خواهد بود. 
بریم این ایده را پیاده سازی کنیم. در ابتدا من یا سمبل a رامشاهده خواهم کرد ویاسمبل b . بالای پشته طبعا در ابتدا تهی خواهد بود پس باید با مشاهده سمبل a بالای پشته a عمل  push انجام شود (  a,z/az) .  و اگر سمبل b را مشاهده کردم باید در ابتدا بالای پشته سمبل b را  push  کنم. ( b,z/bz ) .از سمبل دوم به بعد رشته به ازای هر سمبلی که مشاهده میکنیم باید تا رسیدن به وسط رشته ورودی عمل push را انجام دهیم. که چهار حالت پیش می آید :
1-    سمبل بالای پشته a خواهد بود وسمبل جاری رشته نیزa میباشد پس باید سمبل a را روی پشته دوباره push  کنیم. ( a,a/aa )
2-    سمبل بالای پشته a خواهد بود و سمبل جاری رشته  b می باشد آنگاه باید سمبل b را روی سمبل a push کنیم. ( b,a/ba )
3-    سمبل بالای پشته b خواهد یود و سمبل جاری رشته a می باشد آنگاه باید سمبل a را روی سمبل b  push  کنیم.( a,b/ab )
4-    سمبل بالای پشته b خواهد بود و سمبل جاری رشته b می باشد آنگاه باید سمبل b را روی سمبل b  push کنیم. ( b,b/bb )

پس تا به اینجا برای حالت q0 ماشین این زبان خواهیم داشت:
 


حال زمانی هست که باید تغییر وضعیت انجام دهیم. یعنی من یا دارم λ میان رشته را مشاهده میکنم و یا سمبل a یا b وسط رشته. اگر λ مشاهده کردم بدون تغییر بالای پشته باید حرکت کنم و اگر سمبل میانی رشته را مشاهده کردم باید بدون تغییر بالای پشته  حرکت کنم . چون سمبل میانی رشته ورودی فقط یکی خواهد بود . پس به این ترتیب قوانین انتقال این حالت خواهد شد:
  


حالا باید به ازای هرسمبلی که در رشته ورودی میبینم به شرط اینکه همان سمبل هم در بالای پشته باشد از بالای پشته pop کنم .پس تا به این جا ماشین این زبان خواهد شد: 
 


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


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


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

انواع زبان های مستقل از متن:

یک زبان مستقل از متن خواهد بود اگر و تنها اگر یک گرامر مستقل از متن یا یک ماشین پشته ای برای پذیرش رشته های آن وجود داشته باشد. 
زبانهای مستقل از متن خطی:
یک زبان مستقل از متن خطی خواهد بود اگر و تنها اگر برای پذیرش رشته های آن یک گرامر مستقل از متن خطی وجود داشته باشد.
مثال) 
 


 


برای تمرین گرامر های مستقل از متن  میتوانید مثال های بالارا به عنوان تمرین داشته باشید. سعی کنید برای مثال های بالا یک گرامر مستقل از متن خطی بنویسید.
زبان های مستقل از متن قطعی:
یک زبان مستقل از متن قطعی خواهد بود اگر وتنها اگر برای پذیرش رشته های آن یک ماشین پشته ای قطعی یا PDA وجود داشته باشد.
مثال تمرین)

 

 

زبان های مستقل از متن غیر قطعی :

هر زبان مستقل از متنی را که بتوان برای پذیرش رشته های آن یک ماشین پشته ای غیر قطعی طراحی نمود، یک زبان مستقل از متن غیر قطعی مینامند. 
 ویژگی های بستاری زبان های مستقل از متن:

 

ویژگی های الگوریتمیک زبان های مستقل از متن:
 

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

کلمات کلیدی

محمدرضا احندآبادی
مهندس نرم افزار
کارشناسی مهندسی نرم افزار
مدرس دوره نظریه زبان ها و ماشین ها