سوال علوم کامپیوتر ۸۷
[attachment=1767]
گزینه ۱/
زبان داده شده امکان پیاده سازی با یک پشته را ندارد.
جواب گزینه ۱ نییییییییییییییییییست.
(۰۵ آذر ۱۳۹۰ ۱۲:۵۳ ب.ظ)Mojtaba نوشته شده توسط:جواب گزینه ۳ هست ولی من اشتباه کردم از روی گزینه‌ها نمیشه فهمید اگر گزینه گفته بود حساس به متن نیست ولی مستقل از متن هست اونوقت بدون نگاه کردن به صورت سوال معلوم بود که غلطه اما الان باید صورت سوال رو هم بررسی کرد!(05 آذر ۱۳۹۰ ۱۲:۴۸ ب.ظ)afagh1389 نوشته شده توسط: جواب گزینه ۱ نییییییییییییییییییست.
جواب این مسئله که خیلی خیلی سادهست به قول آفاق خانم از روی صورت سوال هم معلومه پاسخ گزینه ۳ هستش.
اگه ممکنه گرامر یا ماشین این زبان که با یک پشته جواب می دهد را بیان کنید؟
یه ایده به ذهنم رسید ولی خوب همه حالتها رو پوشش نمیده.
فکر کنم بتونید به صورت اجتماع دو زبان بنویسید یه بار i>j و یه بار i<=j بعد
در حالت اول i=j+k
[tex]a^{k}a^{j}b^{j}c^{k}[/tex]
تعداد c ها, bها هیچوقت از تعداد aها بیشتر نمیشه ولی همه حالتها رو پوشش نمیده
حالت دوم
j=i+k
[tex]a^{i}b^{i}b^{k}c^{k}[/tex]
تعداد cها و aها هیچوقت از تعداد bها بیشتر نمیشه ولی همه حالتها رو پوشش نمیده:
b دلخواه و بزرگتر از یک
a بزرگتر و مساوی c
S----->aSc|DB
D----->aD|a
B----->bB|bc
a دلخواه و بزرگتر از یک
b بزرگتر و مساوی c
S------>FG
F-------->aF|a
G------->bGc|H
H----->bH|bc
حالا اجتماعشون رو بنویسین گرامر مستقل از متن سوال میشه.
اینو فقط به اینجهت نوشتم که معلوم بشه گرامر مستقل از متن هم هست. تحقیق در مورد صحت بقیه گزینه‌ها آسان است.
من از طریق پشته ای‌ها حلش کردم چون طبق شرط ماکسیمم I و J متغیرهایی در پشته قرار میدند( a، b )و با متغیر k میتونیم پشته( c)را خالی کنیم پس مستقل از متن است درمورد حساس به متن چون تو شرط متغیرها به هم وابسته است پس نتیجه میگیریم که حساس به متن است در مورد گزینه آخر هم چون مستقل از متن است دارای پشته نامتناهی می باشد بنابرین آتاماتای نامتناهی پس گزینه غلط گزینه ۳ هستش
(۰۶ آذر ۱۳۹۰ ۱۱:۴۹ ب.ظ)Mojtaba نوشته شده توسط: قسمت اول گرامر رشته aaabc را تولید میکنه که اصلا قابل پذیرش نیست.(حالا بقیه گرامر را هم نادیده بگیریم).
خوب تو این زبانی که نوشتی i=3 و j=1 و k=1
(k<max(i,j
پس مورد پذیرشه.هیچ تضادی با مسئله نداره.
هیچ لزومی نداره که a کوچکتر از b باشه یا b کوچکتر‌تر از a باشه فقط c باید کوچکتر از ماکزیمم a,b باشه.
ضمنا من گزینه های دیگه رو نقض نکردم. فقط گرامر مستقل از متن رو براش نوشتم.
سلام دوست من.
کاملا حق با شماست.حالا اگه شرط روی k به این صورت باشه چی پیش می یاد.k>=Max(i,j .
خیلی ممنون از تذکری که دادین.
(۰۷ آذر ۱۳۹۰ ۱۲:۳۹ ب.ظ)Mojtaba نوشته شده توسط: سلام دوست من.
کاملا حق با شماست.حالا اگه شرط روی k به این صورت باشه چی پیش می یاد.k>=Max(i,j .
خیلی ممنون از تذکری که دادین.
سلام
خواهش میکنم.
در سوال اول چون میشد با a یا با b مقداره c رو کنترل کرد میشد گرامر مستقل از متن براش نوشت.
ولی در سوال جدیدتون چون c باید بتونه همزمان مقادیر a,b رو کنترل کنه فکر نمیکنم بشه براش گرامر مستقل از متن نوشت. چون اول باید تشخیص بده که a بزرگتره یا b بعد بتونه از ماکزیممشون بیشتر باشه. یعنی باید بدونه a بزرگتره یا b تا بتونه به تعداد بزرگتر مساوی از مقداری که a در پشته قرار میده یا b در پشته قرار میده برداره.