نه مستقل از متن نیست چه جوری با یه پشته میخواین تشخیص بدین که اندازه 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 نوشته شده توسط:  واقعاً فکر میکنی گرامر این دو زبان فرقی نمیکنند برای زمانی که میخواهی توان را در گرامر نشان بدی اصلاً نمیتونی از گرامرهای مستقل از متن استفاده کنی . مفهوم گرامر این دو زبان دلیل محکمی است برای اینکه این دو زبان را یکی ندونیم چرا که اصلاً گرامرهای مشابهی ندارند و باید برای توان حتما از گرامرهای حساس به متن استفاده کرد و گرامرهای مستقل از متن چنین قابلیتی را ندارند.
مثلاً در گرامر زبان که توان ندارد میتوانید رشته‌ای که تعداد b=5 و a=3 را قبول کنی و بپذیری ولی در حالتی که توان داری این رشته را نمیپذیرد چرا که این‌ها مربع هیچ عدد صحیحی نیستند .

توان دوم a , bها ۳ و۵ تا نمیشه.چون مثلا مگه میشه تعداد aها تو ورودی ۱/۵ تا باشه؟!

برای این که ثابت کنیم $L1=L2$ باید ثابت کنیم:
۱/ $L1\subseteq L2$
۲/ $L2\subseteq L1$

و اگه برای این دو تا زبان بررسی کنیم، میبینیم که این دو شرط براش برقراره، پس دو زبان مساوی هستند!
یعنی تمام رشته هایی که اولی تولید میکنه توی دومی هست و تمام رشته هایی که دومی تولید میکنه توی اولی هست!

مهم نیست ظاهر زبان چی باشه! مهم اینه که واقعاً چه رشته هایی رو تولید میکنه! (به قول معروف‌: بکوش عظمت در نگاه تو باشد نه در چیزی که به آن مینگری )

به نظر من هردوش مستقل از متنه!

(۰۳ بهمن ۱۳۸۹ ۰۱:۱۳ ب.ظ)۵۴m4n3h نوشته شده توسط:  برای این که ثابت کنیم $L1=L2$ باید ثابت کنیم:
۱/ $L1\subseteq L2$
۲/ $L2\subseteq L1$

و اگه برای این دو تا زبان بررسی کنیم، میبینیم که این دو شرط براش برقراره، پس دو زبان مساوی هستند!
یعنی تمام رشته هایی که اولی تولید میکنه توی دومی هست و تمام رشته هایی که دومی تولید میکنه توی اولی هست!

مهم نیست ظاهر زبان چی باشه! مهم اینه که واقعاً چه رشته هایی رو تولید میکنه! (به قول معروف‌: بکوش عظمت در نگاه تو باشد نه در چیزی که به آن مینگری )

به نظر من هردوش مستقل از متنه!

من هم با حرف و استدلال سمانه جان موافقم

زبان مستقل از متن نیست!
زبان هایی که نیاز به محاسبات توانی یا فاکتوریل دارند ،توسط ماشین مستقل از متن قابل پیاده سازی نیستند.حتی زبان ظاهرا ساده a^n^2 هم مستقل از متن نیست!

زبانی که تعداد b‌ها از تعداد a‌ها بیشتره رشته bbbbbaaa رو می پذیره! اما اگر همین رشته رو به ماشین زبان توان دار بدیم، اون رو رد می کنه! و این کاملا مشخصه! و نمی دونم چرا دوستان این دو زبان رو با هم مقایسه می کنند!

البته مستقل از متن نبودن این زبان توسط لم پامپینگ هم ثابت می شه که توی کتاب لینز تمرین های مشابه اون هست.

(۰۳ بهمن ۱۳۸۹ ۰۳:۴۱ ب.ظ)sani نوشته شده توسط:  زبان هایی که نیاز به محاسبات توانی یا فاکتوریل دارند ،توسط ماشین مستقل از متن قابل پیاده سازی نیستند.حتی زبان ظاهرا ساده a^n^2 هم مستقل از متن نیست!

در این که شما میگید شکی نیست، اما در صورتی که ماشین خودش مجبور به انجام محاسبه باشه! مثلاً توی $a^{n^{2}}$ ماشین باید بیاد $n^{2}$ رو حساب کنه! اما این جا ما اومدیم گفتیم زبانی که داریم دقیقاً با یه زبان ساده‌تر میدونیم مستقل از متن هست مساویه!
شما اگه تونیستید ثابت کنید اون دو زبان مساوی نیستند، حق با شماست!

(۰۳ بهمن ۱۳۸۹ ۰۳:۴۱ ب.ظ)sani نوشته شده توسط:  زبان مستقل از متن نیست!
زبان هایی که نیاز به محاسبات توانی یا فاکتوریل دارند ،توسط ماشین مستقل از متن قابل پیاده سازی نیستند.حتی زبان ظاهرا ساده a^n^2 هم مستقل از متن نیست!

زبانی که تعداد b‌ها از تعداد a‌ها بیشتره رشته bbbbbaaa رو می پذیره! اما اگر همین رشته رو به ماشین زبان توان دار بدیم، اون رو رد می کنه! و این کاملا مشخصه! و نمی دونم چرا دوستان این دو زبان رو با هم مقایسه می کنند!

البته مستقل از متن نبودن این زبان توسط لم پامپینگ هم ثابت می شه که توی کتاب لینز تمرین های مشابه اون هست.

دوست عزیز فکر کنم شما اومدین یه راس صفحه آخر و نظرنتون رو نوشتین!!
اگه از اولش بخونین متوجه میشین که به احتمال ۹۰ درصد این زبان مستقل از متن است!

سر کلاس دکتر سید جوادی بحث شد و نتیجه گیری شد که مستقل از متن نیست (حساس به متن هست)به دلیل خاصیت فرمولی بودنش
ما نمیتونیم فرمول رو باز کنیم و تجزیه تحلیل روش انجام بدیم.....
۲ گرامری که واسه این نوشته میشه با اون حالت ساده ترش فرق میکنه

(۰۴ بهمن ۱۳۸۹ ۰۸:۵۲ ب.ظ)saria نوشته شده توسط:  سر کلاس دکتر سید جوادی بحث شد و نتیجه گیری شد که مستقل از متن نیست (حساس به متن هست)به دلیل خاصیت فرمولی بودنش
ما نمیتونیم فرمول رو باز کنیم و تجزیه تحلیل روش انجام بدیم.....
۲ گرامری که واسه این نوشته میشه با اون حالت ساده ترش فرق میکنه

اما من قبول ندارم!
زبان رو نباید به شکلی که داده شده بهش نگاه کرد، بلکه زبان رو باید به صورت مجموعه ای از رشته‌ها دید، که توی هر دوی این زبان‌ها رشته های یکسانی هست، پس هر دو یک زبان هستند!

سمانه خانم این زبانی که میگید مستقل از متنه چون میشه به جای W,W^R لاندا گذاشت.

(۰۴ بهمن ۱۳۸۹ ۰۹:۳۹ ب.ظ)afagh1389 نوشته شده توسط:  سمانه خانم این زبانی که میگید مستقل از متنه چون میشه به جای W,W^R لاندا گذاشت.

البته منظورتون منظمه دیگه؟ نه؟

من اون مثال رو زدم که بگم برای قضاوت در مورد زبان نباید فقط به قیافه ش توجه کرد، بلکه باید تجزیه تحلیلش کرد!

آره منظم هم هست

(۰۴ بهمن ۱۳۸۹ ۱۰:۰۳ ب.ظ)afagh1389 نوشته شده توسط:  آره منظم هم هست

این چجوری منظمه؟!

این زبان اگه $w \epsilon (a,b)$ باشه منظمه و اگر $w \epsilon (a,b)*$
باشه مستقل از متنه.

(۰۵ بهمن ۱۳۸۹ ۱۲:۲۹ ق.ظ)shahryar نوشته شده توسط:  این زبان اگه $w \epsilon (a,b)$ باشه منظمه و اگر $w \epsilon (a,b)*$
باشه مستقل از متنه.

بله دقیقا برعکس گفتید اگه $w \epsilon (a,b)$ دیگه منظم نیست!!!
چون دیگه نمیشه جاش لاندا گذاشت. اگه هم بخواین a,b بگذارین جواب نمیده !!

باید به جای W و WR لاندا بگذاریم که همه رشته‌ها رو بپذیره و منظمه.چون این سوال همه رشته‌ها رو شامل میشه و فقط شامل WWR نیست!!!

اینجوری که شما میگید مثلا aabb عضو زبان نیست ولی اگه u=aa , v=bb باشه این رشته عضو زبانه در حالی که روشی که شما گفتین این رشته رو نمیپذیره!!

الان که تو کتاب نگا کردم تو صورت سوال نوشته + نه * و با + آقای لینز گفته منظمه!

نه هر دوشون منظم هستند.
زبان $uww^{R}v:w,u,v\epsilon {(a,b)}*$
میشه $(a b)^{*}$

زبان $uww^{R}v:u,v,w\epsilon{(a,b)^{ }}$
میشه $(a b)^{ }(aa bb)(a b)^{ }$

(۰۵ بهمن ۱۳۸۹ ۰۲:۰۴ ق.ظ)sepid نوشته شده توسط:  نه هر دوشون منظم هستند.
زبان $uww^{R}v:w,u,v\epsilon {(a,b)}*$
میشه $(a b)^{*}$

زبان $uww^{R}v:u,v,w\epsilon{(a,b)^{ }}$
میشه $(a b)^{ }(aa bb)(a b)^{ }$

نه!
تو حالتی که * داره فرض کنید به جای u و v تهی بذاریم .اون وقت ماشین باید w WR رو که مستقل از متنه قبول کنه.پس منظم نیست.

نیازی به لاندا گذاشتن واسه u و v نیست ما وقفی میتونیم همه رشته‌ها رو پوشش بدیم نیازی به این کار نیست.
شما هر رشته ای که داشته باشی میتونی با لاندا گذاشتن w به این نتیجه برسی که این شرط برای اون رشته صادقه پس اصلا به این فکر نکنید که u , v رو لاندا بگذارید.

من در مورد جواب این سوال مطمئنم چون جزو تستهای کنکوره.

(۰۵ بهمن ۱۳۸۹ ۰۲:۱۴ ق.ظ)afagh1389 نوشته شده توسط:  نیازی به لاندا گذاشتن واسه u و v نیست ما وقفی میتونیم همه رشته‌ها رو پوشش بدیم نیازی به این کار نیست.
شما هر رشته ای که داشته باشی میتونی با لاندا گذاشتن w به این نتیجه برسی که این شرط برای اون رشته صادقه پس اصلا به این فکر نکنید که u , v رو لاندا بگذارید.

من در مورد جواب این سوال مطمئنم چون جزو تستهای کنکوره.

چرا نمیشه؟!آقا من دوس دارم به جای u و v تهی بذارم!مشکلش چیه؟
حرف شما رو منم قبول دارم اگه به جای * + باشه.

اینجا اینکه ما W رو چی بگذاریم اختیاری است و پذیرش این زبان مثل یه شرطی میمونه که اجزاش باهم OR شدن وقتی یکی برقراره دیگه نیازی نیست بقیه رو نگاه کنیم ببینیم که برقراره یا نه چون OR شده این هم شبیه همونه یعنی وقتی W لاندا باشه شرط برقراره نیازی نیست به ازای بقیه مقادیر چک کنیم. البته اگر به نحوی بود که با قرار دادن W =لاندا شرط برقرار نمیشد بله میرفتیم ببینیم بقیه برقراره یا نه!

---

خوب شما دوست داری لاندا بگذار تست رو هم غلط بزن من که رفتم !
------

خب باشه شما u, v رو بزار لاندا.
میخاین بگین رشته هایی مثل abba رو زبان نمیتونه تولید کنه دیگه یعنی همه wwr ها.
حالا من میگم خیر میتونه چون به جای u میزاره ab وبه جای v میزاره ba و به جای w هم میزاره لاندا.
یعنی با یک راه دیگه wwr‌ها توسط زبان تولید شد .

آفاق و سپید خانم:
منظورتون رو فهمیدم.هردو منظم هستند.دیشب ساعت ۲ واقعا دیگه مخم قاطی کرده بود.دیگه آخراش داشتم هزیون می گفتم!به خاطر همین نظر آخریم رو پاک کردم.همش تقصیره طراحی الگوریتمه!

در منظم بودن اون زبان شکی نیست! من فقط مثال زدم که بگم چون یه زبان قیافه ش شبیه زبان های مستقل از متن هست، دلیل نمیشه که بگیم مستقل از متنه! باید با دقت بررسیش کنیم! و می تونیم تجزیه تحلیلش کنیم ببینیم چه رشته هایی تولید میکنه! همین!

معذرت میخوام کسی میدونه زبون دومی که مطرح شد یعنی زبانی که تعداد a هاش بیشتر از b هاش باشه یا اینکه تعداد a‌ها بین b‌ها و دوبرابر b‌ها باشه،چطور با یه پشته پیاده سازی میشه؟؟؟

با پشته رو نمیدونم اما برای قسمت دوم به راحتی میشه براش گرامر نوشت گرامر از اجتماع ۲ گرامر بدست میاد که یکی تعداد a‌ها با b‌ها برابره و دیگری تعداد a‌ها دو برابر تعداد b هاست.
پس به ازای هر a که تولید بشه یا bb , یا b تولید میشه و هیچ وقت تعداد a‌ها بیشتر از دو برابر تعداد b‌ها و کمتر از تعداد b‌ها نمیشه اگه گرامرش رو بنویسید خودتون متوجه میشید.

---

واسه قسمت اول هم شما به ازای هر b یک a پاپ میکنید در آخر اگر a توی پشته موند یعنی تعداد a‌ها بیشتر بوده.

(۰۵ بهمن ۱۳۸۹ ۰۳:۳۴ ب.ظ)مانشتی نوشته شده توسط:  زبانی که تعداد a هاش بیشتر از b هاش باشه

باید دقت کنید که توی این زبان نمی دونیم که aها قبل از bها میان یا bها قبل از aها، یا کلاً هیچ ترتیبی ندارند! اون که آفاق جان توضیح دادن برای حالتی هست که مطمئن باشیم همیشه تعداد aهایی که تا الآن مشاهده کردیم، از تعداد bهایی که تا الآن مشاهده کردیم بیشتر باشند، یعنی مثلاً abaab رو میپذیره اما baa رو نمیپذیره! چون وقتی bی اول رو میبینیم هیچ aی توی استک نیست که pop کنیم.
برای این زبان باید این طوری عمل کنیم:
وقتی a دیدیم اگه B بالای پشته بود pop کنیم اگر نه یه A پوش کنیم
وقتی b دیدیم اگه A بالای پشته بود pop کنیم اگر نه یه B پوش کنیم
اگه آخر سر A توی استک باقی موند، یعنی رشته متعلق به زبان هست پس Aهای باقی مونده رو pop میکنیم تا استک خالی شه!

در ضمن به نظرم بهتر بود سوالتون رو توی یه تاپیک جدید میپرسیدید!

شهریار جان خیلی پرت می‍‏‏زدیا! نزدیک بود که کارت زرد رو بهت بدم!

وای بچه‌ها سرم گیج رفت بهتره حالا که مشخص شد آخرین نتیجه‌ی درست!!! رو در نهایت بنویسین

هر دو منظم هستند.

سلام. آره. مستقل از متنه.