ماشین پشته ای

صفحه 1:


صفحه 2:
ماشینهای پشته‌ای 

صفحه 3:
با توجه به این که قابلیت پذیرش ماشینهای متناهی به زبانهای باقاعده محدود مي‌شود, نیاز به ساختاری داریم که حافظه بیشتری داشته باشد. این کار با افزودن پشته به ساختار ماشین متناهی انجام ۰ ۳۵ )20۳۵-( + 6۷ 

صفحه 4:
۳۳۳۳ یک ماشین پشته‌ای از چهار قسمت تشکیل مي‌شود: 

صفحه 5:
از میت جحت مجدود و از سعت زاست :تا محدوه الست ورودى از جب به راست روى أن نوشته مي شود. توار ورزودى نيه حاتههاى تحسم موهتوة که در هر سم مها اش حرف ذخیره مي‌شود. قبل از شروع به کار ماشین تمام ورودی روی نوار قرار داده مي‌شود. 

صفحه 6:
تنها قادر است اطلاعات را مرور کند و قادر به انتقال اطلاعات به/از نوار نیست. فقط روی نوار به سمت راست حرکت مي‌کند. آجزای هز دستورالعیل: بوازحوان: را گر واجدبه نیس زآليدت اعمال مودهد. هنگام شروع به کار ماشین, نوارخوان روی اولین خانه نوار قرار دارد. 

صفحه 7:
مقدار ذخیره شده در آن نشانگر وضعیت ماشین است تعداد حالتهای یک ماشین پشته‌ای, متناهی است. بر خلاف ماشینهای متناهی, در ماشینهای پشته‌ای ثبات حالت تنها حافظه مأشین نیست. 

صفحه 8:
تعریف ریاضی یک 20۸ یک ۳۲۸ یک شش تایی مرتب به صورت زیر است: ‎M=(Q, £,T, 6, do, F)‏ ۱ اجزای مدل فوق به شرح زیر هستند: ©: مجموعه حاللتماشین ۶: مجموعه حروفالبا ]: الباعپشته 6 تابع گنر حالت 5۳ ,6: حالتاولیه‌ای‌که محاسبانماشیناز أن‌اغاز میشود. ۳ مجموعه حالف هایی‌ماشین(حا لنپ ذیرش] 

صفحه 9:
تابع گذر حالات تابع گذر ‎wb‏ رابطه‌ای به صورت زیر است: ‎Qx(ZU{A})x(FU{A})-P(Qx(TU{A}))‏ :8 هر دستور العمل ماشین به صورت زیر تعریف مي‌شود: ‎&(q, a, A)={Iq, B]}‏ معنى دستور فوق اين است که اگر ماشین در حالت ‎q,‏ ‏و عنصر مقابل نوارخوان ه و عنصر روى يشته 4 باشد, نوارخوان یک واحد به راست انتقال داده مي شود, عنصر ۸ از روی پشته حذف مي‌شود, عنصر 8 به پشته اضافه مي‌شود و حالت ماشین ‎qu‏ تبدیل مي‌گردد. 

صفحه 10:
منال معنی هریک از دستورات زیر چیست؟ * صرفنظر از عنصر مقابل نوارخوان نوارخوان جایجا نمی‌بظ2 ,666 1 ,6 ](1 شود. ‎A)‏ ‏* صرفنظر از عنصر بالای پشته ‎pop.‏ انجام نمى 2 )6© [4 ,]2 ‎A)‏ ‎3)[q, A] €6(q, a,‏ ‎A)‏ al * 168 لنجام ننمی‌شود. 

صفحه 11:
شرط پذیرش یک ۴0۸ براق :ايه جمله «حوسط ماشین 1۶ پذیرقعه شود باندهر سه فرظ ویر برقرار باشند: خاتمه ورودی توقف در حالت نهایی خالی شدن پشته 

صفحه 12:
وضعیت لحظه‌ای ۶0۸ عناصر سمت چپ نوارخوان در ادامه محاسبه تأثیری ندارند. در هر لحظه وضعیت ماشین به حالت فعلی, عنصر مقابل نوارخوان و عناصر سمت راست آن و محتویات پشته بستگی دارد. اگر وضعیت ماشین ,, عناصر پشته » و باقیمانده ورودی ۷ باشد (حرف ‎Jol‏ ۷« مقابل نوارخوان است), [0 ,۷ ,:©] را وضعیت لحظه‌ای ماشین می‌گویند. 

صفحه 13:
محاسبه در 50۸ اگر وضعیت لحظه‌ای ماشین ‎[d, au, Aa]‏ 9 ‎€6(q,, a, A)[q,, B]‏ باشد, وضعیت درونی ماشین به [80 ,11 ,©] تبديل مي‌شود. ‏اين عمل را به صورت [۸6 رنا ,]|-[30 ,لا ,ر0] نمايش ميدهيم. 

صفحه 14:
ياكرام حالت يى 08]م 7( یک گراف جهت دار است. هر گره گراف نشان دهنده یکی از حالات ماشین است. لبه ها نشان دهنده حروف الفبا هستند. حالت اولیه ماشین با نماد ()«نشان داده مي‌شود. حالات نهايى ماشين به صورت 0 رسم مي‌شوند. به ازاى هر دو حالت ,4 و 4 لبه‌ای با برچسب8,۸|۳ بين دو گره »© و 4 وجود دارد اگر و فقط اگر ‎€6(q,, a, A)[g),B]‏ 

صفحه 15:
منال سد .دياكرام حالت ماشين زبانهاى زير ريا رسم كنيد * L=a"b" n=0 C4 9 ‏يرمح‎ ql Ly aA|A b ‘al a L=a2b" n>0 05 ‏مب‎ ‎a ‎CPD 7 aA|A b, AJ A 

صفحه 16:
زبان زیر را با استفاده از ۳10۸ طراحی کنید: L=a"b*c2 , n=O .وجود ندارد 00068 زيبان مستقل از متن نيست و برای آن ۰ 

صفحه 17:
۱ دیاگرام حالت ماشین زبان زیر را رسم کنید. L=wwsk, we{ab,c}# = “aR QC vf (a) CU) ‏اليه‎ a, AJA (5 b, BIA 6,۱ 94 

صفحه 18:
مثال دياكرام حالت ماشين زبان زير را رسم كنيد. L= a=b™ck k=m+n جع( دشن 2,7 ۸ B c, Al 3 c, BJA 

صفحه 19:
| ماشینهای پشته‌ای قطعی ماشینهای پشته‌ای غیر قطعی اگر در یک ۳۸ داشته باشیم [۸(]4,6,ه, >6)4‏ ‎€6(q,,b,B)[q.Y]‏ که [5,ر0,,۷[<۶]0] در صورتی که یکی از چهار شرط زیر برقرار باشد, ۸« غیر قطعی است: a=b and A=B a=b and (A=A or B=A) and (A=B) (a=A or b=A) and (A=A or B=A) (a=A or b=A) 

صفحه 20:
ماشینها ۳ or reall بندی بر اساس نوع دستورالعمل ی پشته‌ای ساده (اتمی, ۸]0۳00) که در هر مرحله فقط مي‌توانند یک حرف از ورودی بخوانند, يا یک عنصر به پشته اضافه کنند, یا ماشینها ماشینها یک عنصر از پشته بردارند. ی پشته‌ای عادی ی پشته‌ای تعمیم یافته (۳68060) که در هر مرحله ميتوانند بيش از یک عنصر را از ورودی بخوانند. بیش از یک عنصر را از پشته بردارند و به آن اضافه کنند. ثابت مي شود که اين سه دسته یکسان هستند. 

صفحه 21:
Pern reer Pal تقسیم بندی بر اساس شرط پذیرش خاتمه ورودی, خالی شدن پشته, توقف در حالت نهایی خاتمه ورودی, توقف در حالت نهایی خاتمه ورودی, خالی شدن پشته توقف در حالت نهایی, خالی شدن پشته ثابت مي‌شود که این چهار دسته یکسان هستند. 

صفحه 22:
تبدیل گرامر مستقل از متن به ۴۵۸ حالت اولیه ماشین, نماد آغازگر گرامر است. حالت نهایی ماشین را ۲ در نظر مي‌گيريم که ۶۷ به ازای هر قانون ۸۲6 یک یال ‎LP a A jl‏ برچسب ۸ رسم مي‌شود. به ازای هر قانون ۸7۴0 که 06۷* یک لبه از ۸ به ظ با برچسب » اضافه مي‌کنيم. به ازای هر حرف ۸ از الفبای پشته, یک لبه از ۲ به ۸ با برچسب 2,۸ رسم مي‌کنيم. 

صفحه 23:
منال گرامر زیر را به ۳1۸ تبدیل کنید. a, A|B ‏هو‎ ny ee ey “DA A al 2 —~\ (@) (B) ۱۳ ABIA S-aAB |aB AwaAB | aB Bob 

صفحه 24:
۱ گرامر زیر را به ۳10۸ تبدیل کنید. | ‎S-aBM‏ ‎aB 2۸‏ Aa |aAB ۳ Bb |bB ‏روج‎ 212 ۸ M>m | AWS BP 

صفحه 25:
گرامر زیر را به ۲10۸ تبدیل کنید. منال S-aABC A-aAA |a ‏ظ‎ | bBCC Cc |cc 

صفحه 26:
ا رت متغیرهای گرامر را به صورت ‎phi > <G,AG>‏ مي‌گيريم. معنى اين متغير اين است كه ماشین با شروع از 4 و انجام یک يا چند محاسبه به 6 مي‌رسد. و در طی این محاسبات ‎A‏ ‏از پشته برداشته مي‌شود. به ازای هر قانون [,ر2(<]4 ره ,606 که (2) 1 361 و به ازای هر ۸۶۲ قانون [6,۸]-(6)6,2,۵ را به مجموعه قوانين اصاقه م يكتيع. 

صفحه 27:
SR ee Per LP re) به ازاى هر قانون [8,©]-(6),,2,5 که ‎ACTU{A)‏ 5 (2]7)2عه قوانین زیر به گرامر اضافه می‌شوند: ‎GA G>a<q,B,q.> Vo.<eQ>‏ به ازای هر قانون [6)1,۵,۸(<]6,۳ قوانین زیر به گرامر اضافه می‌شوند: ‎a<G,adn> <A> Vie GneQ>‏ ۱ 

صفحه 28:
Pian به ازای هر ",4 قوانین زیر به گرامر اضافه مي‌گردند: ‎<S-<q,,A,q,‏ ‏به ازای هر 0,60 قوانین زیر به گرامر اضافه مي‌شوند: << رطان 

صفحه 29:
ماشین پشته‌ای زیر را به گرامر مستقل از متن تبدیل کنید: 22 b,BIA AlA 

صفحه 30:
ماشین پشته‌ای زیر را به گرامر مستقل از متن تبدیل کنید: b,BIA a AIA