در کتاب پیترلینز، ترجمهٔ بابک سلیمی و مجتبا پور محقق، ص ۱۷۰ مثالی (مثال ۸ از فصل ۷، آتاماتای پشته‌ای) برای یافتن گرامر یک npda زده اما من درست متوجه نشدم. دوستان می‌تونند راهنمایی کنند؟
[tex]\delta(q0,a,z)={(q0,Az)} \ \delta(q0,a,A)={(q0,A)} \ \delta(q0,b,A)={(q1,\lambda)} \ \delta(q1,\lambda,z)={(q2,\lambda)} \[/tex]
(۱۶ مرداد ۱۳۹۰ ۱۲:۵۳ ب.ظ)پرهام نوشته شده توسط: در کتاب پیترلینز، ترجمهٔ بابک سلیمی و مجتبا پور محقق، ص ۱۷۰ مثالی (مثال ۸ از فصل ۷، آتاماتای پشته‌ای) برای یافتن گرامر یک npda زده اما من درست متوجه نشدم. دوستان می‌تونند راهنمایی کنند؟
[tex]\delta(q0,a,z)={(q0,Az)} \ \delta(q0,a,A)={(q0,A)} \ \delta(q0,b,A)={(q1,\lambda)} \ \delta(q1,\lambda,z)={(q2,\lambda)} \[/tex]
شما برای یک pda علاوه بر ورودی و وضعیت فعلی که در dfa داشتید یک پشته نیز دارید که نقش حافظه را برعهده دارد، وقتی پشته خالی است علامتی که در بالای پشته نوشته شده z هست.
مورد اول که نوشتید میگه که وقتی علامت بالای پشته z هست(توجه کنید که در لحظه خواندن این z پاپ شده میدانیم که قبلا علامت بالای پشته z بوده اما در حال حاظر علامتی در بالای پشته نیست.چون پاپ میخواند و حذف میکند) و ورودی pda ما a است و در وضعیت q0 قرار دارید در پشته Az را پشته پوش کنید(z در کف پشته و A روی سر z) و در وضعیت q0 بمانید.
۲) اگر در وضعیت q0 هستید و ورودی a است , علامت بالای پشته A بوده در همین وضعیت q0 بمان و دوباره A که پاپ کرده بودی را پوش کن. یعنی اگر علامت بالای پشته A باشد و ورودی a و دروضعیت q0 باشیم در همان وضعیت میمانیم و پشته نیز تغییری نمیکند.
۳) اگر در وضعیت q0 بودی و علامت بالای پشته A بود و ورودی b، به وضعیت q1 برو و درپشته چیزی پوش نکن. (در اصل A بالای پشته را حذف کرده ایم).
۴)اگر در وضعیت q1 بودی و ورودی لاندا بود (یعنی ورودی را در نظر نمیگیریم و هد ورودی نیز جابه جا نمی شود) و علامت بالای پشته z بود (یعنی پشته خالی بود)به وضعیت q2 برو و لاندا را پوش کن.(یعنی چیزی پوش نکن و در اصل z را حذف کرده ایم)
حالا فرض کنید که رشته ab را به pda داده ایم در ابتدا پشته خالی است در وضعیت q0 قرار داریم ورودی را از چپ به راست میخوانیم پس ورودی فعلی a است طبق قانون ۱، A را در پشته پوش میکنیم. یعنی در پشته Az داریم.وضعیت همان q0 است.ورودی فعلی b می باشد طبق قانون ۳ باید به وضعیت q1 برویم و A از بالای پشته حذف شد. با استفاده از قانون ۴ به وضعیت q2 میرویم و z را از بالای پشته حذف میکنیم.اگر q2 وضعیت پذیرش باشد رشته پذیرفته میشود.