انجمنصفحه اولجستجوی انجمن

[mehrdad372]

تعدادی از بچه ها این جا مخالف اعتراض کردن به سوالا هستن
واقعا براشون متاسفم

[mehrdad372]

هنوز کمیته تخصصی سوالات کارشو شروع نکرده بعضی از دوستان اومدن اظهار نظر کردن که دکتر قدسی گفته فقط یک سوال حذف میشه
آخه بر چه اساس حرف میزنی دوست عزیز
تازه امروز مهلت پایان ارسال اعتراض هاست

[Computer92]

من برای بعضی از سوالاتی که دلیل اعتراضو گذاشتم یه سری حروف انگلیسی و علامتها رو جابجا می کنه. ( بعد از ارسال کامل توی پیامی که آخر کار میاره ).

بهتره عکس از دلیلتون بگیرید بفرستید. البته گفته نام و نام خانوادگی و نام پدر و شماره شناسنامه هم بالای عکس باید باشه.

[nimam]

(۰۶ اسفند ۱۳۹۱ ۰۳:۵۲ ق.ظ)alireza89 نوشته شده توسط:  میشه ساز و کارش رو بگی چطور
اشتباه رایج اینه که فکر میکنید شما u . v رو میدید در صورتی که باید هیچ افراضی از اون برابر نباشه که با پشته یا حتی عدم قطعیت حل نمیشه در گفتم ساز و کار خالی و پرشدن پشته شو بگید حداقل اگه pdaنداره در هر صورت حرف دکتر دانشگر تو دانشگاه شریف برای من قابل قبول هستش که گفت گزینه ۱ جواب تست ۵۷ و من ۵ تا از دوستام هم اعتراض دادیم و قرار ایشون نامه بدن بسنجش هم تست۵۵ و هم ۵۷/

اینکه برای شما قابل قبول نیست طبیعیه. من هم اول باورم نمی‌شد و این بخاطر این هست که عدم قطعیت خیلی ملموس نیست. زمانی که در ucw می‌خواهید ببینید که آیا u و w برابر هست نیاز دارید همه‌ی حروف متناظر در u و w را بررسی کنید. اما برای اینکه ببینید این دو رشته برابر نیستند نیاز دارید تا تنها یک اختلاف در بین حروف متناظر پیدا کنید. خوب، شما فکر کنید رشته‌ی ورودی ۱۲۳۴c۱۷۳۴ باشه. شما اگر از DPDA استفاده کنید می‌توانید فقط یک اختلاف (یعنی ۲ و ۷) را بررسی کنید. یعنی حرف ۲را در پشته می‌گذارید، بعد بقیه را تا رسیدن به c دور میریزید. بعد از رشته‌ی دوم فقط با نویسه‌ی دوم آن را مقایسه می‌کنید. پس اینجوری شما می‌توانید یک اختلاف را شناسایی کنید. حالا اگر PDA شما non-deterministic باشد به اصطلاح حدس می‌زند که حرف چندم را باید بررسی کند. و این حدس همیشه بخاطر استفاده از عدم‌قطعیت درست است و این جایی هست که برای دوستان شبهه‌برانگیز می‌شود. در نهایت اینکه من خودم برای کنکور علوم خوندم و این آزمون رو تفننی شرکت کردم و منفعتی از اینکه به یک سوال اعتراض بشه یا نه ندارم. فقط چیزی که احساس کردم به شما دوستان کمک می‌کند رو اینجا نوشتم. در ضمن در کنکور مهندسی قبلا هم یکبار از این قضیه سوال اومده بود ولی واقعا حسش نیست برم پیداش کنم

---

خوب، من این سوال رو عینا در کتاب Linz پیدا کردم. خوشبختانه این از سوالاتی هست که Linz در آخر کتاب خودش جواب داده.
سوال ۱۰ سری اول سوالات فصل ۸ از ویرایش پنجم کتاب لینز:

Determine whether or no the following language is context-free.
[tex]L = \left \{ w_1cw_2 : w1, w2 \in \left \{ a, b \right \}^*, w_1 \neq w_2 \right \}[/tex]

Surprisingly this language is context-free. Construct an npda that counts to some value k (by putiing k tokens on the stak) and remembersthe kth symbol. It then examines the kth symbol in w2. If this does not match the remembered symbol, the string is accepted. if [tex]w \in L[/tex], there must be some k for which this happens. The npda chooses the k non-deterministically

گمان کنم اگر این را به استادتان نشان بدهید تصدیق کنند که حرف Linz درست است.

[Dr_spam]

(۰۶ اسفند ۱۳۹۱ ۱۱:۵۶ ق.ظ)nimam نوشته شده توسط:  

(06 اسفند ۱۳۹۱ ۰۳:۵۲ ق.ظ)alireza89 نوشته شده توسط:  میشه ساز و کارش رو بگی چطور
اشتباه رایج اینه که فکر میکنید شما u . v رو میدید در صورتی که باید هیچ افراضی از اون برابر نباشه که با پشته یا حتی عدم قطعیت حل نمیشه در گفتم ساز و کار خالی و پرشدن پشته شو بگید حداقل اگه pdaنداره در هر صورت حرف دکتر دانشگر تو دانشگاه شریف برای من قابل قبول هستش که گفت گزینه ۱ جواب تست ۵۷ و من ۵ تا از دوستام هم اعتراض دادیم و قرار ایشون نامه بدن بسنجش هم تست۵۵ و هم ۵۷/

اینکه برای شما قابل قبول نیست طبیعیه. من هم اول باورم نمی‌شد و این بخاطر این هست که عدم قطعیت خیلی ملموس نیست. زمانی که در ucw می‌خواهید ببینید که آیا u و w برابر هست نیاز دارید همه‌ی حروف متناظر در u و w را بررسی کنید. اما برای اینکه ببینید این دو رشته برابر نیستند نیاز دارید تا تنها یک اختلاف در بین حروف متناظر پیدا کنید. خوب، شما فکر کنید رشته‌ی ورودی ۱۲۳۴c۱۷۳۴ باشه. شما اگر از DPDA استفاده کنید می‌توانید فقط یک اختلاف (یعنی ۲ و ۷) را بررسی کنید. یعنی حرف ۲را در پشته می‌گذارید، بعد بقیه را تا رسیدن به c دور میریزید. بعد از رشته‌ی دوم فقط با نویسه‌ی دوم آن را مقایسه می‌کنید. پس اینجوری شما می‌توانید یک اختلاف را شناسایی کنید. حالا اگر PDA شما non-deterministic باشد به اصطلاح حدس می‌زند که حرف چندم را باید بررسی کند. و این حدس همیشه بخاطر استفاده از عدم‌قطعیت درست است و این جایی هست که برای دوستان شبهه‌برانگیز می‌شود. در نهایت اینکه من خودم برای کنکور علوم خوندم و این آزمون رو تفننی شرکت کردم و منفعتی از اینکه به یک سوال اعتراض بشه یا نه ندارم. فقط چیزی که احساس کردم به شما دوستان کمک می‌کند رو اینجا نوشتم. در ضمن در کنکور مهندسی قبلا هم یکبار از این قضیه سوال اومده بود ولی واقعا حسش نیست برم پیداش کنم

---

خوب، من این سوال رو عینا در کتاب Linz پیدا کردم. خوشبختانه این از سوالاتی هست که Linz در آخر کتاب خودش جواب داده.
سوال ۱۰ سری اول سوالات فصل ۸ از ویرایش پنجم کتاب لینز:

Determine whether or no the following language is context-free.
[tex]L = \left \{ w_1cw_2 : w1, w2 \in \left \{ a, b \right \}^*, w_1 \neq w_2 \right \}[/tex]

Surprisingly this language is context-free. Construct an npda that counts to some value k (by putiing k tokens on the stak) and remembersthe kth symbol. It then examines the kth symbol in w2. If this does not match the remembered symbol, the string is accepted. if [tex]w \in L[/tex], there must be some k for which this happens. The npda chooses the k non-deterministically

گمان کنم اگر این را به استادتان نشان بدهید تصدیق کنند که حرف Linz درست است.

تو کنکور ۹۰ نمونش اومده بود.

[LordAriana]

(۰۶ اسفند ۱۳۹۱ ۱۲:۳۷ ب.ظ)Dr_spam نوشته شده توسط:  

(06 اسفند ۱۳۹۱ ۱۱:۵۶ ق.ظ)nimam نوشته شده توسط:  

(06 اسفند ۱۳۹۱ ۰۳:۵۲ ق.ظ)alireza89 نوشته شده توسط:  میشه ساز و کارش رو بگی چطور
اشتباه رایج اینه که فکر میکنید شما u . v رو میدید در صورتی که باید هیچ افراضی از اون برابر نباشه که با پشته یا حتی عدم قطعیت حل نمیشه در گفتم ساز و کار خالی و پرشدن پشته شو بگید حداقل اگه pdaنداره در هر صورت حرف دکتر دانشگر تو دانشگاه شریف برای من قابل قبول هستش که گفت گزینه ۱ جواب تست ۵۷ و من ۵ تا از دوستام هم اعتراض دادیم و قرار ایشون نامه بدن بسنجش هم تست۵۵ و هم ۵۷/

اینکه برای شما قابل قبول نیست طبیعیه. من هم اول باورم نمی‌شد و این بخاطر این هست که عدم قطعیت خیلی ملموس نیست. زمانی که در ucw می‌خواهید ببینید که آیا u و w برابر هست نیاز دارید همه‌ی حروف متناظر در u و w را بررسی کنید. اما برای اینکه ببینید این دو رشته برابر نیستند نیاز دارید تا تنها یک اختلاف در بین حروف متناظر پیدا کنید. خوب، شما فکر کنید رشته‌ی ورودی ۱۲۳۴c۱۷۳۴ باشه. شما اگر از DPDA استفاده کنید می‌توانید فقط یک اختلاف (یعنی ۲ و ۷) را بررسی کنید. یعنی حرف ۲را در پشته می‌گذارید، بعد بقیه را تا رسیدن به c دور میریزید. بعد از رشته‌ی دوم فقط با نویسه‌ی دوم آن را مقایسه می‌کنید. پس اینجوری شما می‌توانید یک اختلاف را شناسایی کنید. حالا اگر PDA شما non-deterministic باشد به اصطلاح حدس می‌زند که حرف چندم را باید بررسی کند. و این حدس همیشه بخاطر استفاده از عدم‌قطعیت درست است و این جایی هست که برای دوستان شبهه‌برانگیز می‌شود. در نهایت اینکه من خودم برای کنکور علوم خوندم و این آزمون رو تفننی شرکت کردم و منفعتی از اینکه به یک سوال اعتراض بشه یا نه ندارم. فقط چیزی که احساس کردم به شما دوستان کمک می‌کند رو اینجا نوشتم. در ضمن در کنکور مهندسی قبلا هم یکبار از این قضیه سوال اومده بود ولی واقعا حسش نیست برم پیداش کنم

---

خوب، من این سوال رو عینا در کتاب Linz پیدا کردم. خوشبختانه این از سوالاتی هست که Linz در آخر کتاب خودش جواب داده.
سوال ۱۰ سری اول سوالات فصل ۸ از ویرایش پنجم کتاب لینز:

Determine whether or no the following language is context-free.
[tex]L = \left \{ w_1cw_2 : w1, w2 \in \left \{ a, b \right \}^*, w_1 \neq w_2 \right \}[/tex]

Surprisingly this language is context-free. Construct an npda that counts to some value k (by putiing k tokens on the stak) and remembersthe kth symbol. It then examines the kth symbol in w2. If this does not match the remembered symbol, the string is accepted. if [tex]w \in L[/tex], there must be some k for which this happens. The npda chooses the k non-deterministically

گمان کنم اگر این را به استادتان نشان بدهید تصدیق کنند که حرف Linz درست است.

تو کنکور ۹۰ نمونش اومده بود.

این عبارت [tex]w1cw2[/tex] و شرط [tex]w1\neq w2[/tex]
با این عبارت [tex]w1w2[/tex] و شرط [tex]w1\neq w2[/tex] فرق می کنه

[ebi87]

(۰۶ اسفند ۱۳۹۱ ۰۳:۵۲ ق.ظ)alireza89 نوشته شده توسط:  

(05 اسفند ۱۳۹۱ ۱۱:۴۶ ق.ظ)nimam نوشته شده توسط:  عدم تساوی u و v در ucw (برخلاف تساوی) مستقل از متن است و با استفاده از عدم قطعیت میشه اون رو تشخیص داد. این یکی از جالب ترین نکاتی بود که من از کلاس دکتر کارگهی یاد گرفتم.

میشه ساز و کارش رو بگی چطور
اشتباه رایج اینه که فکر میکنید شما u . v رو میدید در صورتی که باید هیچ افراضی از اون برابر نباشه که با پشته یا حتی عدم قطعیت حل نمیشه در گفتم ساز و کار خالی و پرشدن پشته شو بگید حداقل اگه pdaنداره در هر صورت حرف دکتر دانشگر تو دانشگاه شریف برای من قابل قبول هستش که گفت گزینه ۱ جواب تست ۵۷ و من ۵ تا از دوستام هم اعتراض دادیم و قرار ایشون نامه بدن بسنجش هم تست۵۵ و هم ۵۷/

---

(۰۶ اسفند ۱۳۹۱ ۰۳:۴۲ ق.ظ)ebi87 نوشته شده توسط:  کلید سوال ۱۱۳ هوش اشتباهه. گفته که:
چندتا از گزاره های زیر درست هستند؟
درختی وجود دارد که تعداد گره های با درجه ی فرد ان فرد است.
۶ عنصر را می توان با ۹ مقایسه مرتب کرد.
کوتاه ترین مسیر بین دو راس در گراف بدون دور و وزن دار (با وزن های مثبت یا منفی) (G=(E,V را می توان در (|O(|V|+|E به دست اورد.

اولی که درسته فقط کافیه یک مثال بزنید

دومی غلطه چون حداقل مقایسه برای مرتب کردن n عنصر عبارت است از : حد بالای [tex]\log_{2}n![/tex]
که حد بالای [tex]\log_{2}6![/tex] برابر است با [tex]\log_{2}6!= \log_{2}720= 10[/tex] درنتیجه غلطه.

سومی هم که طبق کتاب کرمن که گفته: "یک گراف جهت دار بدون دور و وزن دار را طبق یک مرتب سازی موضعی راس های ان میتوانیم کوتاه ترین مسیرها از یک مبدا واحد را در زمان (Ɵ(V+E محاسبه کنیم". مبدا واحد میتونه هر کدام از راس های گراف جهت دار بدون دور باشه. پس درنتیجه میتونیم کوتاه ترین مسیر بین دو راس در گراف بدون دور و وزن دار (با وزن های مثبت یا منفی) (G=(E,V را می توان در (|O(|V|+|E به دست اورد.
پس دوتاش درسته[/align] درحالی که کلید سنجش زده گزینه ۲ یعنی یکیش درسته

اولی غلطه درختی وجود دارد که تعداد گره های با درجه ی فرد ان زوج است.

این که شما میگین مربوط به گراف هست. همونطور که میدونین تعریف درجه در گراف و درخت متفاوته. در یک درخت درجه هر گره برابر است با تعداد فرزندانش ولی در یک گراف برابر است با کلیه یال هایی که به گره وارد میشن یا ازش خارج میشن. صورت سوال گفته که درختی وجود دارد که تعداد گره های با درجه ی فرد ان فرد است. اگه درجه را برای هر گره تعداد فرزندانش در نظر بگیریم درسته.
درسته که هر درخت یک گرافه و اگه منظورش گراف بوده باید این طوری می گفته:

وجود دارد گرافی که یک درخت است و تعداد گره های با درجه فرد ان فرد است.

به نظرم ما اول باید بریم علم غیب یاد بگیریم تا بدونیم منظور طراح چی بوده.

[arta.66]

(۰۵ اسفند ۱۳۹۱ ۰۹:۳۵ ب.ظ)Computer92 نوشته شده توسط:  برای ۵۳ نظریه اعتراضی نمی دید؟ من سر جلسه برای ۴تا گزینه مثال نقض پیدا کردم. کلید که گزینه ۴ (هم ab و هم ba) رو اعلام کرده مثال نقض abab رو داره. ۳ گزینه دیگر هم مثال نقض داره

دوست من همون ۴ درسته!!مثالی که میگی نقض هست کجاشه؟؟؟abab هم زیر رشته ab داره هم زیر رشته ba !!! سه کاراکتر اولو درنظر بگیر یا سه کاراکتر آخر!! حس میکنم شما همپوشانی رو در نظر نمیگیری

[sadeghpc]

سوال ۹۹ مشکلی ندارد ؟
اولی که غلط دومی درست است .
اما سومی در صورت سوال نگفته که دور دیگری به جز این دور ندارد و هم چنین نگفته که دور دیگری هم دارد .
اگر دور دیگری داشته باشد این هم غلط می شود و همان گزینه طراح است (گزینه ۲) اما اگر دور دیگری نداشته باشد درست می شود و گزینه ۳ می شود :
حالا ما باید فکر طراح را چگونه بخوانیم ؟

[masoud.bala]

(۰۶ اسفند ۱۳۹۱ ۱۱:۱۶ ق.ظ)mehrdad372 نوشته شده توسط:  هنوز کمیته تخصصی سوالات کارشو شروع نکرده بعضی از دوستان اومدن اظهار نظر کردن که دکتر قدسی گفته فقط یک سوال حذف میشه
آخه بر چه اساس حرف میزنی دوست عزیز
تازه امروز مهلت پایان ارسال اعتراض هاست

برادر من بهش ایمیل بزن جوابتو بگیر !

[lvlina_r]

(۰۶ اسفند ۱۳۹۱ ۰۳:۵۶ ب.ظ)arta.66 نوشته شده توسط:  دوست من همون ۴ درسته!!مثالی که میگی نقض هست کجاشه؟؟؟abab هم زیر رشته ab داره هم زیر رشته ba !!! سه کاراکتر اولو درنظر بگیر یا سه کاراکتر آخر!! حس میکنم شما همپوشانی رو در نظر نمیگیری

منظوره دوستمون اینه که با این که هم ab و هم ba را داره، ولی ماشین داده شده اون را قبول نمی کنه...

[hosseini2012]

دوستان سوالم شاید خیلی درست نباشه ولی یه جوری شده که به هر چیزی باید حداقل یه بار شک کرد! این که بعد از اعتراض تو سامانه سنجش میگه "پاسخ اظهارنظرها را در کارنامه خود ملاحظه خواهید کرد" اینطور نیست که هر کی که فقط اعتراض کرده باشه ترتیب اثر داده بشه که؟ من خودم چند تا درخواست فرستادم اما نه برای همه سوالاتی که شک داشتم.

[mortez28]

(۰۶ اسفند ۱۳۹۱ ۰۴:۲۸ ب.ظ)hosseini2012 نوشته شده توسط:  دوستان سوالم شاید خیلی درست نباشه ولی یه جوری شده که به هر چیزی باید حداقل یه بار شک کرد! این که بعد از اعتراض تو سامانه سنجش میگه "پاسخ اظهارنظرها را در کارنامه خود ملاحظه خواهید کرد" اینطور نیست که هر کی که فقط اعتراض کرده باشه ترتیب اثر داده بشه که؟ من خودم چند تا درخواست فرستادم اما نه برای همه سوالاتی که شک داشتم.

نه دوست عزیز،این چه حرفیه
اگه جوابیه تصحیح بشه برای همه اعمال میشه نه فقط اونایی که اعتراض کردن، مطمئن باش

[foe]

(۰۶ اسفند ۱۳۹۱ ۰۳:۰۰ ب.ظ)ebi87 نوشته شده توسط:  

(06 اسفند ۱۳۹۱ ۰۳:۵۲ ق.ظ)alireza89 نوشته شده توسط:  

(05 اسفند ۱۳۹۱ ۱۱:۴۶ ق.ظ)nimam نوشته شده توسط:  عدم تساوی u و v در ucw (برخلاف تساوی) مستقل از متن است و با استفاده از عدم قطعیت میشه اون رو تشخیص داد. این یکی از جالب ترین نکاتی بود که من از کلاس دکتر کارگهی یاد گرفتم.

میشه ساز و کارش رو بگی چطور
اشتباه رایج اینه که فکر میکنید شما u . v رو میدید در صورتی که باید هیچ افراضی از اون برابر نباشه که با پشته یا حتی عدم قطعیت حل نمیشه در گفتم ساز و کار خالی و پرشدن پشته شو بگید حداقل اگه pdaنداره در هر صورت حرف دکتر دانشگر تو دانشگاه شریف برای من قابل قبول هستش که گفت گزینه ۱ جواب تست ۵۷ و من ۵ تا از دوستام هم اعتراض دادیم و قرار ایشون نامه بدن بسنجش هم تست۵۵ و هم ۵۷/

---

(۰۶ اسفند ۱۳۹۱ ۰۳:۴۲ ق.ظ)ebi87 نوشته شده توسط:  کلید سوال ۱۱۳ هوش اشتباهه. گفته که:
چندتا از گزاره های زیر درست هستند؟
درختی وجود دارد که تعداد گره های با درجه ی فرد ان فرد است.
۶ عنصر را می توان با ۹ مقایسه مرتب کرد.
کوتاه ترین مسیر بین دو راس در گراف بدون دور و وزن دار (با وزن های مثبت یا منفی) (G=(E,V را می توان در (|O(|V|+|E به دست اورد.

اولی که درسته فقط کافیه یک مثال بزنید

دومی غلطه چون حداقل مقایسه برای مرتب کردن n عنصر عبارت است از : حد بالای [tex]\log_{2}n![/tex]
که حد بالای [tex]\log_{2}6![/tex] برابر است با [tex]\log_{2}6!= \log_{2}720= 10[/tex] درنتیجه غلطه.

سومی هم که طبق کتاب کرمن که گفته: "یک گراف جهت دار بدون دور و وزن دار را طبق یک مرتب سازی موضعی راس های ان میتوانیم کوتاه ترین مسیرها از یک مبدا واحد را در زمان (Ɵ(V+E محاسبه کنیم". مبدا واحد میتونه هر کدام از راس های گراف جهت دار بدون دور باشه. پس درنتیجه میتونیم کوتاه ترین مسیر بین دو راس در گراف بدون دور و وزن دار (با وزن های مثبت یا منفی) (G=(E,V را می توان در (|O(|V|+|E به دست اورد.
پس دوتاش درسته[/align] درحالی که کلید سنجش زده گزینه ۲ یعنی یکیش درسته

اولی غلطه درختی وجود دارد که تعداد گره های با درجه ی فرد ان زوج است.

این که شما میگین مربوط به گراف هست. همونطور که میدونین تعریف درجه در گراف و درخت متفاوته. در یک درخت درجه هر گره برابر است با تعداد فرزندانش ولی در یک گراف برابر است با کلیه یال هایی که به گره وارد میشن یا ازش خارج میشن. صورت سوال گفته که درختی وجود دارد که تعداد گره های با درجه ی فرد ان فرد است. اگه درجه را برای هر گره تعداد فرزندانش در نظر بگیریم درسته.
درسته که هر درخت یک گرافه و اگه منظورش گراف بوده باید این طوری می گفته:

وجود دارد گرافی که یک درخت است و تعداد گره های با درجه فرد ان فرد است.

به نظرم ما اول باید بریم علم غیب یاد بگیریم تا بدونیم منظور طراح چی بوده.

اون تعریفی که میگید برای درخت های چند تایی نه برای هر درخت

---

(۰۶ اسفند ۱۳۹۱ ۰۱:۰۹ ب.ظ)LordAriana نوشته شده توسط:  

(06 اسفند ۱۳۹۱ ۱۲:۳۷ ب.ظ)Dr_spam نوشته شده توسط:  

(06 اسفند ۱۳۹۱ ۱۱:۵۶ ق.ظ)nimam نوشته شده توسط:  

(06 اسفند ۱۳۹۱ ۰۳:۵۲ ق.ظ)alireza89 نوشته شده توسط:  میشه ساز و کارش رو بگی چطور
اشتباه رایج اینه که فکر میکنید شما u . v رو میدید در صورتی که باید هیچ افراضی از اون برابر نباشه که با پشته یا حتی عدم قطعیت حل نمیشه در گفتم ساز و کار خالی و پرشدن پشته شو بگید حداقل اگه pdaنداره در هر صورت حرف دکتر دانشگر تو دانشگاه شریف برای من قابل قبول هستش که گفت گزینه ۱ جواب تست ۵۷ و من ۵ تا از دوستام هم اعتراض دادیم و قرار ایشون نامه بدن بسنجش هم تست۵۵ و هم ۵۷/

اینکه برای شما قابل قبول نیست طبیعیه. من هم اول باورم نمی‌شد و این بخاطر این هست که عدم قطعیت خیلی ملموس نیست. زمانی که در ucw می‌خواهید ببینید که آیا u و w برابر هست نیاز دارید همه‌ی حروف متناظر در u و w را بررسی کنید. اما برای اینکه ببینید این دو رشته برابر نیستند نیاز دارید تا تنها یک اختلاف در بین حروف متناظر پیدا کنید. خوب، شما فکر کنید رشته‌ی ورودی ۱۲۳۴c۱۷۳۴ باشه. شما اگر از DPDA استفاده کنید می‌توانید فقط یک اختلاف (یعنی ۲ و ۷) را بررسی کنید. یعنی حرف ۲را در پشته می‌گذارید، بعد بقیه را تا رسیدن به c دور میریزید. بعد از رشته‌ی دوم فقط با نویسه‌ی دوم آن را مقایسه می‌کنید. پس اینجوری شما می‌توانید یک اختلاف را شناسایی کنید. حالا اگر PDA شما non-deterministic باشد به اصطلاح حدس می‌زند که حرف چندم را باید بررسی کند. و این حدس همیشه بخاطر استفاده از عدم‌قطعیت درست است و این جایی هست که برای دوستان شبهه‌برانگیز می‌شود. در نهایت اینکه من خودم برای کنکور علوم خوندم و این آزمون رو تفننی شرکت کردم و منفعتی از اینکه به یک سوال اعتراض بشه یا نه ندارم. فقط چیزی که احساس کردم به شما دوستان کمک می‌کند رو اینجا نوشتم. در ضمن در کنکور مهندسی قبلا هم یکبار از این قضیه سوال اومده بود ولی واقعا حسش نیست برم پیداش کنم

---

خوب، من این سوال رو عینا در کتاب Linz پیدا کردم. خوشبختانه این از سوالاتی هست که Linz در آخر کتاب خودش جواب داده.
سوال ۱۰ سری اول سوالات فصل ۸ از ویرایش پنجم کتاب لینز:

Determine whether or no the following language is context-free.
[tex]L = \left \{ w_1cw_2 : w1, w2 \in \left \{ a, b \right \}^*, w_1 \neq w_2 \right \}[/tex]

Surprisingly this language is context-free. Construct an npda that counts to some value k (by putiing k tokens on the stak) and remembersthe kth symbol. It then examines the kth symbol in w2. If this does not match the remembered symbol, the string is accepted. if [tex]w \in L[/tex], there must be some k for which this happens. The npda chooses the k non-deterministically

گمان کنم اگر این را به استادتان نشان بدهید تصدیق کنند که حرف Linz درست است.

تو کنکور ۹۰ نمونش اومده بود.

این عبارت [tex]w1cw2[/tex] و شرط [tex]w1\neq w2[/tex]
با این عبارت [tex]w1w2[/tex] و شرط [tex]w1\neq w2[/tex] فرق می کنه

من هم با درست نبودن ۵۷ موافقم و با برهان خلف تو زمانی که c نداره ثابت میشه کرد(مکمل بگیری و با محدودیت I به تناقض میرسی چون محدودیت Iو II مکلند و زبان مستقل از متن نسبت به مکمل بسته اند در نتیجه هر دو باید مستقل از متن باشند) دوستی که توضیح دادن خودشون گفتن که رشته اول تا c دور ریخته میشه در صورتی که این سوال c نداره و زبان غیر قطعی نمیتونه هم مکان جدا شدن رو حدس بزنه و هم اینکه کدام حرف رو باید مساوی بگیره و بقیه رو دور بریزه فرق این سوال با لینز همینه.جالبه من هم از یکی از دوستانم که دانشجوی دکتراست پرسیدم گفت مستقل از متن نیست حالا مثل اینکه بیشتر باید به جواب این سوال شک کرد چون کسایی که دقیقا مستقل از متن زدن برای همین سوال PDA ارایه نمیدن و همه اون سوال معروف لینز رو میارن میگن انگار ما نمیدونیم

[nimam]

(۰۶ اسفند ۱۳۹۱ ۰۶:۱۲ ب.ظ)foe نوشته شده توسط:  من هم با درست نبودن ۵۷ موافقم و با برهان خلف تو زمانی که c نداره ثابت میشه کرد(مکمل بگیری و با محدودیت I به تناقض میرسی چون محدودیت Iو II مکلند و زبان مستقل از متن نسبت به مکمل بسته اند در نتیجه هر دو باید مستقل از متن باشند) دوستی که توضیح دادن خودشون گفتن که رشته اول تا c دور ریخته میشه در صورتی که این سوال c نداره و زبان غیر قطعی نمیتونه هم مکان جدا شدن رو حدس بزنه و هم اینکه کدام حرف رو باید مساوی بگیره و بقیه رو دور بریزه فرق این سوال با لینز همینه.جالبه من هم از یکی از دوستانم که دانشجوی دکتراست پرسیدم گفت مستقل از متن نیست حالا مثل اینکه بیشتر باید به جواب این سوال شک کرد چون کسایی که دقیقا مستقل از متن زدن برای همین سوال PDA ارایه نمیدن و همه اون سوال معروف لینز رو میارن میگن انگار ما نمیدونیم

من که گفتم اصلا برام مهم نیست، چون من علوم شرکت کردم و مهندسی رو تفننی امتحان دادم و امیدوارم چیزی که شما میگین درست باشه. ولی یه چیزی شما گفتی که مخم سوت کشید! «زبان مستقل از متن نسبت به مکمل بسته اند»!!! زبان‌های مستقل از متن تحت reverse بسته هستند و نه complement! مکمل زبان مستقل از متن ممکنه مستقل از متن باشه ولی نه لزوما (مکمل مستقل از متن لزوما حساس به متن می‌شود). در ضمن لطفا نقل قول‌های طولانی نکنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.