برای کدامیک از زبانهای زیر یک pda وجود دارد؟
۱) a^i b^j e^k c^i c^j c^k d^k| i,j k>=0
۲) a^i b^j c^i c^j c^k d^k |i,j,k >=0
۳) a^ i b^j c ^i d ^j |i,j >=0
اگر بلدید تابع ماشینو بگید
سلام.
برای زبان اول نمیشه PDA رسم کرد. مشکل در e^k هست.هر طور که جابجایی انجام بدیم، نمی تونیم e,c,d رو که باهم برابر هستند با pda رسم کنیم.
زبان دوم رو میشه راحت براش PDA رسم کرد. زبانش رو میشه به این تبدیل کنیم :a^i b^j c^j c^i c^k d^k و مشاهده میشه که هیچ تداخلی ندارند.
زبان سومی رو نمیشه براش PDA رسم کرد.چون عناصر وابسته به هم رو نمیشه جابجا کرد به طوری که تداخل نداشته باشند.
ماشین زبان دومی راحت رسم می شه. مشکلی نداره. رسم ماشین برعهده خواننده واگذار می گردد (به قول این مولف ها در طاقت کتاب نمی گنجد
).موفق باشید.