(۰۹ اسفند ۱۳۹۰ ۰۵:۰۴ ب.ظ)anyone نوشته شده توسط: در مورد سوال ۵۳
به نظر شما زبانی وجود دارد که بشه براش گرامری نوشت اما الگوریتمی براش وجود نداشته باشه؟
وجود گرامر برای تشخیص اینکه زبان تصمیم پذیر هست کافی نیست؟
خوب زبان های بازگشتی الگوریتم دارند ولی زبان های شمارش پذیر بازگشتی نه و زبان های شمارش پذیر بازگشتی گرامرهای بدون محدودیت دارند. پس آره می تونه وجود داشته باشه. :این نظر من هست و شاید اشتباه باشه ولی فکر نکنم!
سوال ۵۳ درست هست
اکثر دوستان مفهوم شمارش پذیری رو با متناهی بودن اشتباه میگیرند
اگه کسی مایل هست یه مثال نقض برای گزینه الف پیدا کنه !!!!!!!!!
سوال ۵۳
گزینه ج )برای هر زبان دلخواه از الفبای سیکما می توان یک گرامر صوری تولید کننده در نظر گرفت
اگر الف درست باشه ج هم باید درست باشه چون هر زبانی بازگشتی برشمردنی باشه می توان برای ان یک گرامر نامقید پیدا کرد
اگر الفبای یک سیکما متناهی باشه انگاه ان مجموعه شمارش پذیره ولی هر زبان ان مجموعه شمارش پذیر نیست این تصویر کتاب لینز که پیوست کردم میگه به ازای هر سیکمای غیر تهی زبانهای وجود دارند که بازگشتی برشمردنی نیستند بعد هم نگفته مجموعه متناهی باشه یا نامتناهی
(۱۳ اسفند ۱۳۹۰ ۰۹:۰۴ ب.ظ)tarang نوشته شده توسط: سوال ۵۳
گزینه ج )برای هر زبان دلخواه از الفبای سیکما می توان یک گرامر صوری تولید کننده در نظر گرفت
اگر الف درست باشه ج هم باید درست باشه چون هر زبانی بازگشتی برشمردنی باشه می توان برای ان یک گرامر نامقید پیدا کرد
اگر الفبای یک سیکما متناهی باشه انگاه ان مجموعه شمارش پذیره ولی هر زبان ان مجموعه شمارش پذیر نیست این تصویر کتاب لینز که پیوست کردم میگه به ازای هر سیکمای غیر تهی زبانهای وجود دارند که بازگشتی برشمردنی نیستند بعد هم نگفته مجموعه متناهی باشه یا نامتناهی
قسمت د که غلط بودنش مشخص هست و اصلا روش هیچ بحثی نیست باید به جای کلمه بازگشتی از بازگشتی برشمردنی استفاده میکرد ( قسمت د غلط)
در همین پیوست خودتون :
آخرین جمله داره تاکید میکنه که هر زبان سیگما قابل شمارش نیست (یعنی ج غلط)
همین طور داره میگه بر طبق تئوری ۱۱/۱ مجموعه زبان های سیگما هم غیر قابل شمارش هست (ب غلط)
پس تا همینجا میشه گزینه چهارم رو به عنوان جواب انتخاب کرد
شما در صورتی میتونی قسمت الف رو رد کنی که یا یه جمله در لینز پیدا کنی که صریحا مخالف الف باشه
ویا هم ارزی دو جمله الف و ج رو از لینز بیان کنی من کمی تردید دارم که هم ارز باشند !!
در هر صورت من هم سر کنکور بین همین تردید داشتم ولی از اونجایی که اون سه تای دیگه به صورت واضح و مشخص غلط بود و گزینه ای هم نبود که بگه هر چهار تا غلطه گزینه چهارم رو انتخاب کردم
در مورد سوال ۵۴ ، نظرتون چیه ؟؟؟
چطور میشه گزینه ۳ درست میشه؟؟
اصلا b چطوری می تونه پیشوند باشه یعنی x=b یا y=b باشه ؟؟؟
گزینه ۴ درست نیست بنظرتون ؟؟؟
در مورد سوال ۵۶ من نمی تونم دلیل منظم بودنشو درک کنم کسی میتونه اینو اثبات کنه؟
نظرم اینه که اینکه یه زبان زیر مجموعه یه زبان منظم باشه دلیلی بر منظم بودن خودش نیست (مثلا a به توان n فاکتوریل)
در مورد سوال ۵۳ من زیاد اطلاعی ندارم ولی ببینید فکر کنم این فایل بدرد بخوره
(۱۳ اسفند ۱۳۹۰ ۱۰:۰۱ ب.ظ)موج نوشته شده توسط:(13 اسفند ۱۳۹۰ ۰۹:۰۴ ب.ظ)tarang نوشته شده توسط: سوال ۵۳
گزینه ج )برای هر زبان دلخواه از الفبای سیکما می توان یک گرامر صوری تولید کننده در نظر گرفت
اگر الف درست باشه ج هم باید درست باشه چون هر زبانی بازگشتی برشمردنی باشه می توان برای ان یک گرامر نامقید پیدا کرد
اگر الفبای یک سیکما متناهی باشه انگاه ان مجموعه شمارش پذیره ولی هر زبان ان مجموعه شمارش پذیر نیست این تصویر کتاب لینز که پیوست کردم میگه به ازای هر سیکمای غیر تهی زبانهای وجود دارند که بازگشتی برشمردنی نیستند بعد هم نگفته مجموعه متناهی باشه یا نامتناهی
قسمت د که غلط بودنش مشخص هست و اصلا روش هیچ بحثی نیست باید به جای کلمه بازگشتی از بازگشتی برشمردنی استفاده میکرد ( قسمت د غلط)
در همین پیوست خودتون :
آخرین جمله داره تاکید میکنه که هر زبان سیگما قابل شمارش نیست (یعنی ج غلط)
همین طور داره میگه بر طبق تئوری ۱۱/۱ مجموعه زبان های سیگما هم غیر قابل شمارش هست (ب غلط)
پس تا همینجا میشه گزینه چهارم رو به عنوان جواب انتخاب کرد
شما در صورتی میتونی قسمت الف رو رد کنی که یا یه جمله در لینز پیدا کنی که صریحا مخالف الف باشه
ویا هم ارزی دو جمله الف و ج رو از لینز بیان کنی من کمی تردید دارم که هم ارز باشند !!
در هر صورت من هم سر کنکور بین همین تردید داشتم ولی از اونجایی که اون سه تای دیگه به صورت واضح و مشخص غلط بود و گزینه ای هم نبود که بگه هر چهار تا غلطه گزینه چهارم رو انتخاب کردم
قضیه ۱-۱۱ میگه اگر یک مجموعه نامتناهی شمارا باشد مجموعه توانی آن ناشمارا است.سوال گفته مجموعه متناهییه پس با این قضیه نمیشه گزینه ۲ را رد کرد.به نظر شما این جمله که اگر یک مجموعه متناهی باشه انگاه مجموعه توانی ان شمارش پذیره اشتباست
حالا من زیاد دیگه وارد بحث نمیشم ولی نگاه کنید سوال گفته الفبا متناهی باشد یعنی مثلاً {a,b}= سیگما خوب حالا سیگما * میشه نامتناهی و مجموع توانیش میشه غیر قابل شمارش به نظر شما اینطور نیست؟ چون اگه دقت کنید تو فایل هم اول اومده
{ s={a,b بعد استارش شده غیر متناهی. بازم تاکید می کنم نگفته زبان متناهی یعنی اگه مثلاً الفبا a , b بود وزبان می شد مثلاً
{a,b} به توان ۱۰۰ در این صورت الف درست بود ولی گفته الفبا متناهی دقت کنید.
(۱۴ اسفند ۱۳۹۰ ۰۸:۳۹ ب.ظ)tarang نوشته شده توسط: قضیه ۱-۱۱ میگه اگر یک مجموعه نامتناهی شمارا باشد مجموعه توانی آن ناشمارا است.سوال گفته مجموعه متناهییه پس با این قضیه نمیشه گزینه ۲ را رد کرد.به نظر شما این جمله که اگر یک مجموعه متناهی باشه انگاه مجموعه توانی ان شمارش پذیره اشتباست
من عینا ترجمه متن همون پیوست لینزتون رو گفتم
theorem 11.1 tells us that the set of all languages on "E" is not countable
تئوری ۱۱/۱ این را بیان میکند که مجموعه همه زبانها بر روی الفبای سیگما قابل شمارش نیستند (دقیقا ناقض ب هست)
در ضمن نقض این قسمت هم مثل قسمت د کاملا آشکاره و کسی که یه دور هم سرسرکی نظریه خونده باشه میتونه این دو تا رو اول رد کنه
موفق باشید
سلام موج عزیز
در مورد سوال ۵۳
روی سوال به زبانهای شمارا اشاره دارد معادل با زبانهای بازگشتی است یعنی برای آنها الگوریتم عضویتی وجود دارد منظور همان زبانهای ®. فراتر از اینها همان زبانهای شمارای بازگشتی هستند که در کتاب به آنها شمارای بازگشتی می گن همان(RE) که براش الگوریتم عضویت نداریم. دسته گرامرهایی که برای RE استفاده میشه همان بدون محدودیت ها هستند گزینه ج هم به این خاطر نادرست است. اما اگه بخواهیم نادرستی الف رو نشون بدیم مثلا یه عبارتی بنویسیم مثه اونهایی که برای منظم و مستقل مینویسیم نمیشه باید به طور غیر مستقیم نشون داد که اگه صفحات لینز رو بعد از قضیه ۲-۱۱ مطالعه بشه حله اونجا به طور غیرمستقیم نوشته . یه چیز دیگه هم اینه که ج را به این خاطر رد میکنیم چون دسته گرامرهای به نام بدون محدودیت داریم که معرف زبانهای RE هستند یعنی بازگشتی شمارا (RE).پس الف هم نادرسته .
این نظر منه شاید هم دارم اشتبا میکنم.
(۱۴ اسفند ۱۳۹۰ ۱۲:۳۹ ق.ظ)esi نوشته شده توسط: در مورد سوال ۵۴ ، نظرتون چیه ؟؟؟استدلال من تو پستهای قبلی مشکل داشت یا قابل فهم نبود؟
چطور میشه گزینه ۳ درست میشه؟؟
اصلا b چطوری می تونه پیشوند باشه یعنی x=b یا y=b باشه ؟؟؟
گزینه ۴ درست نیست بنظرتون ؟؟؟
(۱۴ اسفند ۱۳۹۰ ۱۱:۱۰ ب.ظ)mohammad_13690 نوشته شده توسط:(14 اسفند ۱۳۹۰ ۱۲:۳۹ ق.ظ)esi نوشته شده توسط: در مورد سوال ۵۴ ، نظرتون چیه ؟؟؟استدلال من تو پستهای قبلی مشکل داشت یا قابل فهم نبود؟
چطور میشه گزینه ۳ درست میشه؟؟
اصلا b چطوری می تونه پیشوند باشه یعنی x=b یا y=b باشه ؟؟؟
گزینه ۴ درست نیست بنظرتون ؟؟؟
من واقعا متوجه نشدم ، من کلا مشترک ۳ تا غلط زدم که یکیش همینه ، اما واقعا منظورتونو دقیق ندونستم ، اصلا مگه b می تونه پیشوند باشه !!؟؟؟ شاید هم من قاطی کردم !!!؟؟؟
(۱۴ اسفند ۱۳۹۰ ۰۲:۴۷ ب.ظ)anyone نوشته شده توسط: در مورد سوال ۵۶ من نمی تونم دلیل منظم بودنشو درک کنم کسی میتونه اینو اثبات کنه؟منم نمیتونم بفهمم چطوری این زبان منظم حساب میشه!
نظرم اینه که اینکه یه زبان زیر مجموعه یه زبان منظم باشه دلیلی بر منظم بودن خودش نیست (مثلا a به توان n فاکتوریل)
لطفا اگه کسی میدونه توضیح بده.
(۱۴ اسفند ۱۳۹۰ ۱۱:۳۹ ب.ظ)esi نوشته شده توسط: من واقعا متوجه نشدم ، من کلا مشترک ۳ تا غلط زدم که یکیش همینه ، اما واقعا منظورتونو دقیق ندونستم ، اصلا مگه b می تونه پیشوند باشه !!؟؟؟ شاید هم من قاطی کردم !!!؟؟؟
تبریک میگم که فقط سه تا اشتباه زدی، سفید هم زیاد نداشتی؟
مطمئنی پست من رو خوندی؟ پس چرا باز می پرسی b میتونه پیشوند باشته؟ پستم رو کپی می کنم:
با اضافه کردن هیچ چیز به b نمیشه اون رو عضو L کرد و به همین دلیل سرگروه یکی از کلاس های هم ارزیه که همکلاسی هاش رشته هایی هستن که مثل خود b ، نمیتونن عضو L بشن؛ مثل ba,baba,bba,...
فرض کنید x=b و y=baba و z هم که گفته هر رشته دلخواه؛ قبول دارید در این صورت x و y هم ارزند؟ چون برای هر z که xz عضو L باشه، yz هم عضو L هست (البته اگر z پیدا میشد اما الآن فرض همیشه اشتباه و استنتاج همیشه صحیح است)
______
پست اولم و پست دوستای دیگه که راجع به مفهوم کلاس هم ارزیه بخون اگه خواستی بگو مفصل تر توضیح بدم