سلام دوستان.
میگم این زبان به نظر شما مستقل از متنه؟
[tex]w\epsilon {a,b}}\ast[/tex]
[tex]n_{a}(w)^{2} <n_{b}(w)^{2}[/tex]
اگه نیست مگه فرقی با این زبان داره؟
[tex]n_{a}(w) < n_{b}(w)[/tex]
پارسه میگه مستقل از متن نیست.
نه مستقل از متن نیست چه جوری با یه پشته میخواین تشخیص بدین که اندازه aها کمتر از توان دوم b هست یا نه شما فقط یه پشته دارید از این یه پشته دست تنها چه انتظاری دارید؟
فکر کنم مستقل از متن باشه خوب میشه یه گرامر مستقل از متن نوشت که فقط رشته هایی رو بپذیره که تعداد a از تعداد bها کمتر باشه خوب اگه a<b باشه و هم a و هم b دو عدد صحیح مثبت باشه توان دوم اونا هم از همدیگه کمترند و نیاز به چک کردن نداره.
(۰۱ بهمن ۱۳۸۹ ۰۲:۱۰ ب.ظ)امیدوار نوشته شده توسط: فکر کنم مستقل از متن باشه خوب میشه یه گرامر مستقل از متن نوشت که فقط رشته هایی رو بپذیره که تعداد a از تعداد bها کمتر باشه خوب اگه a<b باشه و هم a و هم b دو عدد صحیح مثبت باشه توان دوم اونا هم از همدیگه کمترند و نیاز به چک کردن نداره.
مستقل از متنه به همون دلیلی که امیدوار جان گفتن!
به نظر خودم هم مستقل از متنه.به خاطر اون دلیلی که تو صورت سوال نوشتم!
ولی متاسفانه پارسه تو جواباش نوشته مستقل از متن نیست.
آره چون تعداد a و b مثبت و صحیحه میشه این نتیجه رو گرفت.
نه مستقل از متن نیست شما که نمی‌توانید صورت سوال را عوض کنید .شما باید حتما توان دوم‌ها را چک کنید و پشته چنین توانایی را نداره پس نمیتونه مستقل از متن باشه اگه این طوری بود که می شود تعداد زیادی dfa هم کشید که بگه تعداد b ها از aها بیشتره پس حتماً مستقل از متن هم نیست و منظم میشه این حرفا صورت مسئله را پاک کردنه
من بازم گیجم هر کدومتون یه چیزی میگید همتونم درست میگید!!
آیا هست یا نه!!!
(۰۲ بهمن ۱۳۸۹ ۰۱:۵۴ ق.ظ)hatami84 نوشته شده توسط: نه مستقل از متن نیست شما که نمی‌توانید صورت سوال را عوض کنید .شما باید حتما توان دوم‌ها را چک کنید و پشته چنین توانایی را نداره پس نمیتونه مستقل از متن باشه اگه این طوری بود که می شود تعداد زیادی dfa هم کشید که بگه تعداد b ها از aها بیشتره پس حتماً مستقل از متن هم نیست و منظم میشه این حرفا صورت مسئله را پاک کردنه
یعنی پس به نظرتون تو این جور سوالا نباید محاسبات ریاضی رو دخالت داد؟!
محاسبات ریاضی را میشه دخالت داد به شرطی که صورت سوال و مفهوم سوال عوض نشه.این محاسبات که برای توان در بالا در نظر گرفته شده داره کلاً مفهوم استفاده از پشته را از بین میبره
(۰۲ بهمن ۱۳۸۹ ۰۳:۰۰ ب.ظ)hatami84 نوشته شده توسط: محاسبات ریاضی را میشه دخالت داد به شرطی که صورت سوال و مفهوم سوال عوض نشه.این محاسبات که برای توان در بالا در نظر گرفته شده داره کلاً مفهوم استفاده از پشته را از بین میبره
به نظر شما اگه ما بخایم یه دو تا گرامر واسه این دو تا زبان بنویسیم با هم فرق می کنند؟اگه ما یه گرامر مستقل از متن واسه زبان دومی بنویسیم به طور حتم جواب سوال اولی رو هم داده ایم.اگه نمیشه یه یک مثال نقض بیارید.
واقعاً فکر میکنی گرامر این دو زبان فرقی نمیکنند برای زمانی که میخواهی توان را در گرامر نشان بدی اصلاً نمیتونی از گرامرهای مستقل از متن استفاده کنی . مفهوم گرامر این دو زبان دلیل محکمی است برای اینکه این دو زبان را یکی ندونیم چرا که اصلاً گرامرهای مشابهی ندارند و باید برای توان حتما از گرامرهای حساس به متن استفاده کرد و گرامرهای مستقل از متن چنین قابلیتی را ندارند.
مثلاً در گرامر زبان که توان ندارد میتوانید رشته‌ای که تعداد b=5 و a=3 را قبول کنی و بپذیری ولی در حالتی که توان داری این رشته را نمیپذیرد چرا که این‌ها مربع هیچ عدد صحیحی نیستند .
(۰۳ بهمن ۱۳۸۹ ۰۱:۲۴ ق.ظ)hatami84 نوشته شده توسط: مثلاً در گرامر زبان که توان ندارد میتوانید رشته‌ای که تعداد b=5 و a=3 را قبول کنی و بپذیری ولی در حالتی که توان داری این رشته را نمیپذیرد چرا که این‌ها مربع هیچ عدد صحیحی نیستند .
قراره تعداد b برابر ۵ باشه نه توان ۲ی اون!
(۰۳ بهمن ۱۳۸۹ ۰۱:۲۴ ق.ظ)hatami84 نوشته شده توسط: واقعاً فکر میکنی گرامر این دو زبان فرقی نمیکنند برای زمانی که میخواهی توان را در گرامر نشان بدی اصلاً نمیتونی از گرامرهای مستقل از متن استفاده کنی . مفهوم گرامر این دو زبان دلیل محکمی است برای اینکه این دو زبان را یکی ندونیم چرا که اصلاً گرامرهای مشابهی ندارند و باید برای توان حتما از گرامرهای حساس به متن استفاده کرد و گرامرهای مستقل از متن چنین قابلیتی را ندارند.توان دوم a , bها ۳ و۵ تا نمیشه.چون مثلا مگه میشه تعداد aها تو ورودی ۱/۵ تا باشه؟!
مثلاً در گرامر زبان که توان ندارد میتوانید رشته‌ای که تعداد b=5 و a=3 را قبول کنی و بپذیری ولی در حالتی که توان داری این رشته را نمیپذیرد چرا که این‌ها مربع هیچ عدد صحیحی نیستند .
برای این که ثابت کنیم [tex]L1=L2[/tex] باید ثابت کنیم:
۱/ [tex]L1\subseteq L2[/tex]
۲/ [tex]L2\subseteq L1[/tex]
و اگه برای این دو تا زبان بررسی کنیم، میبینیم که این دو شرط براش برقراره، پس دو زبان مساوی هستند!
یعنی تمام رشته هایی که اولی تولید میکنه توی دومی هست و تمام رشته هایی که دومی تولید میکنه توی اولی هست!
مهم نیست ظاهر زبان چی باشه! مهم اینه که واقعاً چه رشته هایی رو تولید میکنه! (به قول معروف: بکوش عظمت در نگاه تو باشد نه در چیزی که به آن مینگری
)به نظر من هردوش مستقل از متنه!