صفحه‌ها: ۱ ۲
(۲۱ دى ۱۳۹۰ ۰۵:۱۷ ب.ظ)پشتکار نوشته شده توسط:در پشته‌ی مربوط به اتوماتهای پشته ایی یا پشته از ابتدا خالیه یا اینکه شامل یک مقدار هست که تو کتاب لینز این Z رو مقدار اولیه‌ی داخل پشته فرض میکنه و تا اخر باید در درون پشته باشه و نباید حذف بشه.(21 دى ۱۳۹۰ ۰۲:۴۵ ب.ظ)marzieh نوشته شده توسط: در مورد سوال ۵۷
یه سوال
پشته از ابتدا خالی هست یا پر؟
اگه پر هست چطوری پره؟ مگه اولی با PDA کار می کنیم پشته نباید خالی باشد؟
و حتی در بعضی سوال‌ها خودش یک مقدار رو به عنوان مقدار اولیه در نظر میگیره بجز مقدار فرضی Z
(۲۱ دى ۱۳۹۰ ۰۵:۱۷ ب.ظ)پشتکار نوشته شده توسط: یه سوالتوی کتاب های مختلف قراردادهای مختلفی وجود داره.ماشین سوال ۵۷ طبق تعریف ماشین های پشته ای تو کتاب لینز نوشته شده.براساس تعریف کتاب لینز علامتی مثل z(هر علامتی دیگه ای هم میتونه باشه نه فقط لزوما z)همیشه به صورت پیش فرض تو پشته وجود داره و هر وقت روی پشته z باشه یعنی پشته خالیه
پشته از ابتدا خالی هست یا پر؟
اگه پر هست چطوری پره؟ مگه اولی با PDA کار می کنیم پشته نباید خالی باشد؟
جواب آقای ahmadnouri درمورد سوال ۵۷ درسته. درمورد بقیه سوالات نظری ندارم.
توی پشته در حالت اوله یه z هست. به ازای هر a که گرفت یک A به پشته اضاه میکنه. چه قبلا A بوده و چه نبوده. با تعداد bها اصلاً کاری نداره. تا حالا رشتمون یه تعداد a و b داره و توی پشتمون یا Z داریم یا یه تعداد A (به تعداد a که توی رشته داشتیم) روی Z.
همین که اولین c رو گرفت تا اونجایی که پشت سرهم c میاد رشته رو قبول میکنه و با پشته کاری نداره. اگه تا حالا a نخوند به بالا و اگه حداقل یه a خوند به پایین میره.
توی حالت پایانی بالا هرچی a خوند بازم توی حالت پایانی میمونه. اگه توجه کنین قبل از c هیچ a و بعد از c هیچ b نداریم.
توی حالت پایینی بعد از گرفتن c، ما حداقل یه a توی ورودی داشتیم و به همون تعداد A توی پشته. بعد از گرفتن c یا cها، با aها کاری نداره و به ازای هر b یه A خط میزنه. با خالی شدن پشته تعداد bهای بعد از c با aهای قبل از c برابر میشه و به حالت پایانی میره. بعدشم هرتعداد a که بگیره تاثیر نداره ولی b نمیگیره.
پس جوابمون گزینه ۱ میشه.
قبول از اول یه Z در پشته در نظر می گیریم. حرفی نیست
حالا چطوری b رو خونده A رو اپ کرده و A رو پوش کرده؟ A از کجا اومده دیگه؟
نکنه از a,Z/AZ اومده؟ اگه اینطوریه پس وقتی AZ رو پوش می کنیم پشته از راست به چپ پر میشه؟ یعنی اول Z سپس A روی Z پوش می شه؟
منظور از a,Z/AZ یعنی این ماشین رشته ورودی را میخونه و یه عنصر از پشته پاپ میکنه. اگه عنصر ورودی a و عنصر روی پشته Z بود، به حالت مشخص شده میره و اول Z و بعد A رو پوش میکنه.
یکی از حرکتها (فکر کنم "حرکت" تعریف خوبی نباشه) به این شکل بود: b,A/L (منظور از L لانداست). از حالتی که توش هستین با این حرکت به یه حالت دیگه میرین. رشته ورودیتون روی حرف b قرار داره. فرض کنین پشته شما به شکل AAZ( آخرین عنصر پشته Z) باشه. با این حرکت پشته شما میشه AZ. یعنی یه A پاپ میشه و چیزی بجاش پوش نمیشه.
سوال ۵۹ هم به نظر من گزینه ۲ میشه.
الف که رشته تولید نمیکنه و یکی از حالاتش به نال میره (مسلماً مستقل از متن نیست.). پس محدودیت نداره.
طبق تعریف زبان خطی که سمت راست فقط یه حرف بزرگ (رشته ساز) میاد گرامر ب خطیه.
ج هم که رشته a*{ab}*bb رو ایجاد میکنه که معلومه منظمه.