۰
subtitle
ارسال: #۱
چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد
من تو این پست خواستم این چندتا زبان رو کنار هم بذارم که تفاوتها و شباهت هاش مشخص باشه که مدیران لطف کردن و بستنش چون قانون انجمن اینه که هر سوالی جدا پرسیده بشه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در ضمن من توی انجمن جستجو کردم بیشتر اینها رو ندیدم و اگر هم پرسیده شده باشه معمولا جواب های کلیشه ای بهش داده شده که
۱/ چون dfa و nfa میشه براش کشید منظمه
۲/ چون نمیتونیم لم تزریق براش بیاریم منظمه
۳/ چون با عبارت منظم میشه نوشتش پس منظمه
۴/ چون نمیتونیم بگیم نامنظمه پس منظمه
هدف من تحلیل کلی و تستی واسه اینجور مسائل بود. و چون شکل زبانها باهم مرتبط بود بهتر بود در کنار هم بررسی بشه که بهتر فهمیده بشه.
اما من روم مثل سنگ پای قزوینه
سوالا رو جدا جدا پرسیدم
۴. زبان [tex]\left \{ uwvw^{R\R}:u,v,w\epsilon \sum^{*},\left|u\right|\geqslant 10 ,\left|v\right |\leqslant 10 ,\left | w \right |\leqslant10\right \}[/tex]
جواب: یه نکته قشنگی که در شرایط این دیدم به شکل [tex]\left \{\left | w \right |\leqslant 10 \right \}[/tex] که خب رشته w را محدود و متناهی کرده و u و v که اصلا ارتباطی ندارن و هر چی خواستن باشن. پس در کل این زبان هم به نظر من سیگما استار هست
اگه همین جور پیش بره تمام زبانها رو سیگما استار فرض میکنم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در ضمن من توی انجمن جستجو کردم بیشتر اینها رو ندیدم و اگر هم پرسیده شده باشه معمولا جواب های کلیشه ای بهش داده شده که
۱/ چون dfa و nfa میشه براش کشید منظمه
۲/ چون نمیتونیم لم تزریق براش بیاریم منظمه
۳/ چون با عبارت منظم میشه نوشتش پس منظمه
۴/ چون نمیتونیم بگیم نامنظمه پس منظمه
هدف من تحلیل کلی و تستی واسه اینجور مسائل بود. و چون شکل زبانها باهم مرتبط بود بهتر بود در کنار هم بررسی بشه که بهتر فهمیده بشه.
اما من روم مثل سنگ پای قزوینه
سوالا رو جدا جدا پرسیدم۴. زبان [tex]\left \{ uwvw^{R\R}:u,v,w\epsilon \sum^{*},\left|u\right|\geqslant 10 ,\left|v\right |\leqslant 10 ,\left | w \right |\leqslant10\right \}[/tex]
جواب: یه نکته قشنگی که در شرایط این دیدم به شکل [tex]\left \{\left | w \right |\leqslant 10 \right \}[/tex] که خب رشته w را محدود و متناهی کرده و u و v که اصلا ارتباطی ندارن و هر چی خواستن باشن. پس در کل این زبان هم به نظر من سیگما استار هست
اگه همین جور پیش بره تمام زبانها رو سیگما استار فرض میکنم
۱
ارسال: #۲
RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل نشد
(۲۱ شهریور ۱۳۹۲ ۰۸:۱۷ ب.ظ)zimenswall نوشته شده توسط: من تو این پست خواستم این چندتا زبان رو کنار هم بذارم که تفاوتها و شباهت هاش مشخص باشه که مدیران لطف کردن و بستنش چون قانون انجمن اینه که هر سوالی جدا پرسیده بشه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در ضمن من توی انجمن جستجو کردم بیشتر اینها رو ندیدم و اگر هم پرسیده شده باشه معمولا جواب های کلیشه ای بهش داده شده که
۱/ چون dfa و nfa میشه براش کشید منظمه
۲/ چون نمیتونیم لم تزریق براش بیاریم منظمه
۳/ چون با عبارت منظم میشه نوشتش پس منظمه
۴/ چون نمیتونیم بگیم نامنظمه پس منظمه
هدف من تحلیل کلی و تستی واسه اینجور مسائل بود. و چون شکل زبانها باهم مرتبط بود بهتر بود در کنار هم بررسی بشه که بهتر فهمیده بشه.
اما من روم مثل سنگ پای قزوینه
۴. زبان [tex]\left \{ uwvw^{R\R}:u,v,w\epsilon \sum^{*},\left|u\right|\geqslant 10 ,\left|v\right |\leqslant 10 ,\left | w \right |\leqslant10\right \}[/tex]
جواب: یه نکته قشنگی که در شرایط این دیدم به شکل [tex]\left \{\left | w \right |\leqslant 10 \right \}[/tex] که خب رشته w را محدود و متناهی کرده و u و v که اصلا ارتباطی ندارن و هر چی خواستن باشن. پس در کل این زبان هم به نظر من سیگما استار هست
اگه همین جور پیش بره تمام زبانها رو سیگما استار فرض میکنم
خوب خودت تقریباً درست تحلیل کردی، ولی این زبان نمیتونه سیگما استار باشه، چون حتی اگه w و v رو برابر اپسیلون در نظر بگیریم، باز هم خود u حداقل اندازه‌اش ۱۰ هستش و بنابراین هیچ رشته‌ای با طول کمتر از ۱۰ عضو زبان ما نمیتونه باشه ;-)
اگه حالت خاص v = w = eps رو در نظر بگیریم، شکل رشته‌های ما میشه u با شرط u| >= 10| که در حقیقت مجموعه‌ی تمام رشته‌های موجود با طول بزرگتر مساوی ۱۰ هستش.
حالا اگه v و w برابر eps هم نباشند، هر چیزی که تولید میشه باز هم جزو همون مجموعه‌ی سابقه و کل زبان ما چیزی بهش اضافه نمیشه. بنابراین کل زبان ما میشه مجموعه‌ی تمام رشته‌های با طول بزرگتر یا مساوی ۱۰ و میدونیم که مجموعه‌ی تمام رشته‌های با طول بزرگتر مساوی ۱۰ یک زبان منظم هستش (هم میشه براش عبارت منظم نوشت و هم لم تزریق و هم NFA و DFA و ...! همه روش‌های موجود برای اثباتش راحته).
ارسال: #۳
RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل نشد
(۲۱ شهریور ۱۳۹۲ ۰۸:۴۵ ب.ظ)azk84 نوشته شده توسط:(21 شهریور ۱۳۹۲ ۰۸:۱۷ ب.ظ)zimenswall نوشته شده توسط: من تو این پست خواستم این چندتا زبان رو کنار هم بذارم که تفاوتها و شباهت هاش مشخص باشه که مدیران لطف کردن و بستنش چون قانون انجمن اینه که هر سوالی جدا پرسیده بشه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در ضمن من توی انجمن جستجو کردم بیشتر اینها رو ندیدم و اگر هم پرسیده شده باشه معمولا جواب های کلیشه ای بهش داده شده که
۱/ چون dfa و nfa میشه براش کشید منظمه
۲/ چون نمیتونیم لم تزریق براش بیاریم منظمه
۳/ چون با عبارت منظم میشه نوشتش پس منظمه
۴/ چون نمیتونیم بگیم نامنظمه پس منظمه
هدف من تحلیل کلی و تستی واسه اینجور مسائل بود. و چون شکل زبانها باهم مرتبط بود بهتر بود در کنار هم بررسی بشه که بهتر فهمیده بشه.
اما من روم مثل سنگ پای قزوینه
۴. زبان [tex]\left \{ uwvw^{R\R}:u,v,w\epsilon \sum^{*},\left|u\right|\geqslant 10 ,\left|v\right |\leqslant 10 ,\left | w \right |\leqslant10\right \}[/tex]
جواب: یه نکته قشنگی که در شرایط این دیدم به شکل [tex]\left \{\left | w \right |\leqslant 10 \right \}[/tex] که خب رشته w را محدود و متناهی کرده و u و v که اصلا ارتباطی ندارن و هر چی خواستن باشن. پس در کل این زبان هم به نظر من سیگما استار هست
اگه همین جور پیش بره تمام زبانها رو سیگما استار فرض میکنم
خوب خودت تقریباً درست تحلیل کردی، ولی این زبان نمیتونه سیگما استار باشه، چون حتی اگه w و v رو برابر اپسیلون در نظر بگیریم، باز هم خود u حداقل اندازه‌اش ۱۰ هستش و بنابراین هیچ رشته‌ای با طول کمتر از ۱۰ عضو زبان ما نمیتونه باشه ;-)
اگه حالت خاص v = w = eps رو در نظر بگیریم، شکل رشته‌های ما میشه u با شرط u| >= 10| که در حقیقت مجموعه‌ی تمام رشته‌های موجود با طول بزرگتر مساوی ۱۰ هستش.
حالا اگه v و w برابر eps هم نباشند، هر چیزی که تولید میشه باز هم جزو همون مجموعه‌ی سابقه و کل زبان ما چیزی بهش اضافه نمیشه. بنابراین کل زبان ما میشه مجموعه‌ی تمام رشته‌های با طول بزرگتر یا مساوی ۱۰ و میدونیم که مجموعه‌ی تمام رشته‌های با طول بزرگتر مساوی ۱۰ یک زبان منظم هستش (هم میشه براش عبارت منظم نوشت و هم لم تزریق و هم NFA و DFA و ...! همه روش‌های موجود برای اثباتش راحته).
تشکر از شما
این تحلیل قبلی من بود و به اشتباه خودم هم پی بردم
که زیادی زبان ها رو سیگما استار در نظر میگرفتمدر صورتی که این زبان هیچ رشته کمتر از طول ۱۰ را نمیسازه. پس سیگما استار نمیتونه باشه.
البته بعد از پی بردن به اشتباهم اینطوری جوابم رو اصلاح کردم که قسمت چون متناهی هست پس این قسمتش منظمه و رشته u هم هر چیزی هست (البته با طول بیشتر از ۱۰) پس این زبان راحت میشه براش nfa پیاده کرد. بعبارتی اگر w=v=eps را در نظر بگیریم رشته u یه سیگما استاره با این شرط که حتما طولش بیشتر از ۱۰ باشه .
حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده.
برای nfa هم ساختن رشته u کفایت میکنه به شکلی که اولش ۱۰ تا کاراکتر دلخواه بسازه و بعد هر چی خواست یا نخواست بسازه. و رشته هم که با تعاریف بالا قابل حذفه.
البته قبلا یه اشتباه دیگه ای هم کرده بود در تصور NFA برای این زبان
nfa صحیح ولی غیر بهینه و با تصور غلط: اول رشته u را بسازیم به شکلی که اولش ۱۰ تا کاراکتر دلخواه بسازه و بعد هر چی خواست یا نخواست بسازه و سپس که حالات متناهی دارن رو پیاده میکنیم و به رشته u الحاق میکنیم.
و بعد متوجه شدم که این قسمت دومی همش حالت پایانی شد. پس باید حذف بشه.
۰
ارسال: #۴
RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد
(۲۱ شهریور ۱۳۹۲ ۰۹:۱۴ ب.ظ)zimenswall نوشته شده توسط: حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده."رشته قبلی" رو نداریم، بلکه رشته‌های جدیدی که توی این حالت تولید میشن، زیرمجموعه‌ی مجموعه‌ی رشته‌ای هستند که فقط توسط u به تنهایی (توی حالت خاص v = w = eps) تولید میشن. در نتیجه چیز جدیدی به کل مجموعه‌ی ما اضافه نمیشه.
بقیه‌ی تحلیلتون درسته الان :-). پس الان دیگه مشکلی نموند دیگه؟
ارسال: #۵
RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد
(۲۱ شهریور ۱۳۹۲ ۱۰:۱۴ ب.ظ)azk84 نوشته شده توسط:(21 شهریور ۱۳۹۲ ۰۹:۱۴ ب.ظ)zimenswall نوشته شده توسط: حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده."رشته قبلی" رو نداریم، بلکه رشته‌های جدیدی که توی این حالت تولید میشن، زیرمجموعه‌ی مجموعه‌ی رشته‌ای هستند که فقط توسط u به تنهایی (توی حالت خاص v = w = eps) تولید میشن. در نتیجه چیز جدیدی به کل مجموعه‌ی ما اضافه نمیشه.
بقیه‌ی تحلیلتون درسته الان :-). پس الان دیگه مشکلی نموند دیگه؟
مشکلات حل شد هر چند از لحاظ فلسفی یه سوالی برام پیش اومد که
"رشته های جدید همون رشته قبلی را داریم" با " رشته جدید زیر مجموعه رشته قبلیه" چه فرقی داره؟
اگر از لحاظ حالت رشته در نظر بگیریم، فرقی بین دوتا جمله بالا نیست ولی اگر بخواهیم u , w , v را در نظر بگیریم حرف شما درسته و رشته جدید ، هیچوقت رشته قبلی نیستند.
درست گفتم دیگه ؟؟
ارسال: #۶
RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد
(۲۲ شهریور ۱۳۹۲ ۱۲:۵۵ ق.ظ)zimenswall نوشته شده توسط:(21 شهریور ۱۳۹۲ ۱۰:۱۴ ب.ظ)azk84 نوشته شده توسط:(21 شهریور ۱۳۹۲ ۰۹:۱۴ ب.ظ)zimenswall نوشته شده توسط: حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده."رشته قبلی" رو نداریم، بلکه رشته‌های جدیدی که توی این حالت تولید میشن، زیرمجموعه‌ی مجموعه‌ی رشته‌ای هستند که فقط توسط u به تنهایی (توی حالت خاص v = w = eps) تولید میشن. در نتیجه چیز جدیدی به کل مجموعه‌ی ما اضافه نمیشه.
بقیه‌ی تحلیلتون درسته الان :-). پس الان دیگه مشکلی نموند دیگه؟
مشکلات حل شد هر چند از لحاظ فلسفی یه سوالی برام پیش اومد که
"رشته های جدید همون رشته قبلی را داریم" با " رشته جدید زیر مجموعه رشته قبلیه" چه فرقی داره؟
اگر از لحاظ حالت رشته در نظر بگیریم، فرقی بین دوتا جمله بالا نیست ولی اگر بخواهیم u , w , v را در نظر بگیریم حرف شما درسته و رشته جدید ، هیچوقت رشته قبلی نیستند.
درست گفتم دیگه ؟؟
بیشتر منظورم این بود که هر کدوم اینها یک "مجموعه" از رشته‌ها هستند نه یک رشته! بنابراین باید براشون اصطلاح زیرمجموعه و ... اینا رو به کار برد. نباید بگیم رشته‌ی سیگما استار، باید حتماً بگیم مجموعه‌ی سیگما استار. یا مثلاً توی این پست قبلیتون نباید بگیم:
" حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده. "،
بلکه باید دقت کنیم که با مجموعه سر و کار داریم و نه با رشته. درستش اینه:
" حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم عملاً تمام مجموعه رشته‌های جدیدی که به وجود میان زیرمجموعه‌ی مجموعه‌ی قبلی هستند. ".
یا مثلاً اینجا که گفتین "رشته u یه سیگما استاره" دقیق‌ترش اینه که بگین "مجموعه‌ی رشته‌ای که u تولید میکنه همون سیگما استاره).
کلاً اشکالی که گرفته بودم فقط جنبه‌ی فنی داشت ;-)
ارسال: #۷
RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد
(۲۲ شهریور ۱۳۹۲ ۰۱:۲۲ ق.ظ)azk84 نوشته شده توسط:(22 شهریور ۱۳۹۲ ۱۲:۵۵ ق.ظ)zimenswall نوشته شده توسط:(21 شهریور ۱۳۹۲ ۱۰:۱۴ ب.ظ)azk84 نوشته شده توسط:(21 شهریور ۱۳۹۲ ۰۹:۱۴ ب.ظ)zimenswall نوشته شده توسط: حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده."رشته قبلی" رو نداریم، بلکه رشته‌های جدیدی که توی این حالت تولید میشن، زیرمجموعه‌ی مجموعه‌ی رشته‌ای هستند که فقط توسط u به تنهایی (توی حالت خاص v = w = eps) تولید میشن. در نتیجه چیز جدیدی به کل مجموعه‌ی ما اضافه نمیشه.
بقیه‌ی تحلیلتون درسته الان :-). پس الان دیگه مشکلی نموند دیگه؟
مشکلات حل شد هر چند از لحاظ فلسفی یه سوالی برام پیش اومد که
"رشته های جدید همون رشته قبلی را داریم" با " رشته جدید زیر مجموعه رشته قبلیه" چه فرقی داره؟
اگر از لحاظ حالت رشته در نظر بگیریم، فرقی بین دوتا جمله بالا نیست ولی اگر بخواهیم u , w , v را در نظر بگیریم حرف شما درسته
و رشته جدید ، هیچوقت رشته قبلی نیستند.
درست گفتم دیگه ؟؟
بیشتر منظورم این بود که هر کدوم اینها یک "مجموعه" از رشته‌ها هستند نه یک رشته! بنابراین باید براشون اصطلاح زیرمجموعه و ... اینا رو به کار برد. نباید بگیم رشته‌ی سیگما استار، باید حتماً بگیم مجموعه‌ی سیگما استار. یا مثلاً توی این پست قبلیتون نباید بگیم:
" حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده. "،
بلکه باید دقت کنیم که با مجموعه سر و کار داریم و نه با رشته. درستش اینه:
" حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم عملاً تمام مجموعه رشته‌های جدیدی که به وجود میان زیرمجموعه‌ی مجموعه‌ی قبلی هستند. ".
یا مثلاً اینجا که گفتین "رشته u یه سیگما استاره" دقیق‌ترش اینه که بگین "مجموعه‌ی رشته‌ای که u تولید میکنه همون سیگما استاره).
کلاً اشکالی که گرفته بودم فقط جنبه‌ی فنی داشت ;-)
اشکالاتی که به من گرفتید کاملا درسته . اصطلاحات رو اشتباه یا در جایی غیر از مکان مناسبش میگم
رشته و مجوعه و سیگما و سیگما استار و زبان و همه چی رو دارم درهم میگم.
چون فکرم بیشتر درگیر اینه که تستای این قسمت رو با استدلال بزنم و شاید مسائل فنی اش خیلی برام مهم نباشه.
ظاهرا یه کم باید در جنبه فنی دانشم تجدید نظر کنم که مثل اون مسئله نشه که هر چی زبان میبینم سریع میگم سیگما استاره.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close