(۱۵ دى ۱۳۹۰ ۰۷:۲۱ ب.ظ)ahmadnouri نوشته شده توسط:  به نظرم
سوال ۵۷ گزینه ۱درسته
سوال ۵۹ گزینه ۲ درسته الف حساس به متن نیست چون در حساس به متن نمیتونیم رشته تهی رو تولید کنیم
گرامری حساس به متن است که برزای تمام قانون های به فرم U--->V طول U کوچکتر مساوی V باشه

اگه ممکنه با استدلال بگید. گزینه های صحیح رو می دونم
مرسی

(۱۵ دى ۱۳۹۰ ۰۶:۵۳ ب.ظ)پشتکار نوشته شده توسط:  سوال ۵۹ جلوی هر گزینه ای نوشته‌ام چیه ولی اشتباهه.
کسی میتونه اشتباهاتمو بگه؟

مدل های سوال ۵۸ رو چطوری میشه حل کرد؟
سوالاتی مثل ۵۷ رو خیلی دیدم ولی نمی دونم چرا نمی تونم بپذیرمش. آخه چطوری هنوز نه a داریم نه b و پشته هم خالیه ولی روی حالت ابتدایی نوشته a یا b رو بخون و A رو پاپ کن!!!!!!!!!!

پیشاپیش از لطفتون سپاسگزارم

به نظر منم ۵۷ یه جورایی اشتباهه! هیچکدوم گزینه هاش کاملو درست نیست!!!

۵۷ من گزینه چهار را انتخاب کردم. البته جوابا را نگاه نکردم ببینم کدام گزینه را درست زده.
استدلالم این بود:
این ماشین میتواند c+a+ را بپذیره پس گزینه یک غلط هست چون طول a و b برابر نیست. گزینه دو هم به همین دلیل غلط و گزینه سه هم غلط چون این زبان می تونه c را بپذیره پس طول c‌ها با b‌ها برابر نیست.

(۱۵ دى ۱۳۹۰ ۱۰:۵۷ ب.ظ)pos نوشته شده توسط:  ۵۷ من گزینه چهار را انتخاب کردم. البته جوابا را نگاه نکردم ببینم کدام گزینه را درست زده.
استدلالم این بود:
این ماشین میتواند c+a+ را بپذیره پس گزینه یک غلط هست چون طول a و b برابر نیست. گزینه دو هم به همین دلیل غلط و گزینه سه هم غلط چون این زبان می تونه c را بپذیره پس طول c‌ها با b‌ها برابر نیست.

منم ۴ زدم!

جواب را چند زده؟

(۱۵ دى ۱۳۹۰ ۱۱:۰۳ ب.ظ)pos نوشته شده توسط:  جواب را چند زده؟

۱

جوابش درست هست. اشتباه از ما بوده.

ای بابا
یکی نیست درد ما را درمان کند
چطوری توی پشته ای که دفعه اول خالیه یه A پاپ کنم و دوتا A پوش؟؟؟
کسی نمی دونه؟؟؟
چطوری حلش کردید؟

اخوی پشته که خالی نیست. z مقدار اولیه پشته هست. و به ازای هر کدام از a و b‌ها دو تا حالت تعریف کرده. مثلا:
a,z/Az‌: یعنی اگر روی نوار a بود و محتوای پشته z آنگاه a را به بالای پشته اضافه کن.
a,A/AA‌: یعنی اگر روی نوار a بود و بالای پشته (یعنی یکبار حداقل حالت قبلی اتفاق افتاده و الان بالای پشته A هست) آنگاه یک A دیگر به بالای پشته اضافه کن.
و همین کار برای b هم شده.

امیدوارم متوجه منظورتان شده باشم.

(۱۵ دى ۱۳۹۰ ۰۸:۰۰ ب.ظ)پشتکار نوشته شده توسط:  اگه ممکنه با استدلال بگید. گزینه های صحیح رو می دونم
مرسی

من که برای سوال ۵۹ دلیل آوردم
اما برای سوال ۵۷
در حالت اول برای هر a که میاد یه A در پشته قرار میده و برای b‌ها هم که کاری نمیکنه اگه ورودی بستار a+b باشه مسیر بالایی رو نموتنه بره و در مسیر پایینی حتما ۱ c یا بیشتر میپذیره و بعد در مسیر باقیمانده به ازای a‌ها کاری نمی کنه و برای هر b یه A رو از پشته حذف میکنه تا اینجا که گزینه ۱ درسته

(۱۵ دى ۱۳۹۰ ۱۰:۵۷ ب.ظ)pos نوشته شده توسط:  این ماشین میتواند c+a+ را بپذیره پس گزینه یک غلط هست

این ماشین که نمیتونه همچین رشته ای رو بپذیره؟!!!! چون اگه ورودی با a شروع بشه که باید بالای پشته A پوش کنه و دیگه نمی تونه از مسیر بالا بره
پس برای چک کردن مسیر بالا باید ورودی با b شروع بشه و هیچ a ای بعد از اون نیاد حالا می تونیم از مسیر بالا بریم پس باز میتونه ۱ c یا بیشتر بپذیره و بعدش میتونه هر چند تا a هم که می خواد داشته باشه که باز در چارچوب زبان گزینه ۱ هست

---

در مورد سوال ۵۸ هم فکر میکنم گزینه ۳ درسته اگه این سوال کنکور بود من نمیزدم

(۱۶ دى ۱۳۹۰ ۰۲:۴۳ ق.ظ)ahmadnouri نوشته شده توسط:  

نقل قول: این ماشین میتواند c+a+ را بپذیره پس گزینه یک غلط هست

این ماشین که نمیتونه همچین رشته ای رو بپذیره؟!!!! چون اگه ورودی با a شروع بشه که باید بالای پشته A پوش کنه و دیگه نمی تونه از مسیر بالا بره
پس برای چک کردن مسیر بالا باید ورودی با b شروع بشه و هیچ a ای بعد از اون نیاد حالا می تونیم از مسیر بالا بریم پس باز میتونه ۱ c یا بیشتر بپذیره و بعدش میتونه هر چند تا a هم که می خواد داشته باشه که باز در چارچوب زبان گزینه ۱ هستدر مورد سوال ۵۸ هم فکر میکنم گزینه ۳ درسته اگه این سوال کنکور بود من نمیزدم

من منظورم رشته سی پلاس آ پلاس بود که بد افتاده و این رشته را می پذیره. ولی در صورت پذیرفتن این رشته هم گزینه یک رد نمیشه و جواب همان گزینه یک میشه

در مورد سوال ۵۷

(۲۱ دى ۱۳۹۰ ۰۲:۴۵ ب.ظ)marzieh نوشته شده توسط:  در مورد سوال ۵۷

یه سوال
پشته از ابتدا خالی هست یا پر؟
اگه پر هست چطوری پره؟ مگه اولی با PDA کار می کنیم پشته نباید خالی باشد؟

(۲۱ دى ۱۳۹۰ ۰۵:۱۷ ب.ظ)پشتکار نوشته شده توسط:  یه سوال
پشته از ابتدا خالی هست یا پر؟
اگه پر هست چطوری پره؟ مگه اولی با PDA کار می کنیم پشته نباید خالی باشد؟

توی کتاب های مختلف قراردادهای مختلفی وجود داره.ماشین سوال ۵۷ طبق تعریف ماشین های پشته ای تو کتاب لینز نوشته شده.براساس تعریف کتاب لینز علامتی مثل z(هر علامتی دیگه ای هم میتونه باشه نه فقط لزوما z)همیشه به صورت پیش فرض تو پشته وجود داره و هر وقت روی پشته z باشه یعنی پشته خالیه

جواب آقای 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 رو ایجاد میکنه که معلومه منظمه.