زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۷:۳۳ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد

ارسال:
  

zimenswall پرسیده:

چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد

من تو این پست خواستم این چندتا زبان رو کنار هم بذارم که تفاوتها و شباهت هاش مشخص باشه که مدیران لطف کردن و بستنش چون قانون انجمن اینه که هر سوالی جدا پرسیده بشه

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

در ضمن من توی انجمن جستجو کردم بیشتر اینها رو ندیدم و اگر هم پرسیده شده باشه معمولا جواب های کلیشه ای بهش داده شده که
۱/ چون dfa و nfa میشه براش کشید منظمه
۲/ چون نمیتونیم لم تزریق براش بیاریم منظمه
۳/ چون با عبارت منظم میشه نوشتش پس منظمه
۴/ چون نمیتونیم بگیم نامنظمه پس منظمه

هدف من تحلیل کلی و تستی واسه اینجور مسائل بود. و چون شکل زبانها باهم مرتبط بود بهتر بود در کنار هم بررسی بشه که بهتر فهمیده بشه.
اما من روم مثل سنگ پای قزوینه Wink سوالا رو جدا جدا پرسیدم


۴. زبان [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 که اصلا ارتباطی ندارن و هر چی خواستن باشن. پس در کل این زبان هم به نظر من سیگما استار هست
اگه همین جور پیش بره تمام زبانها رو سیگما استار فرض میکنم Big Grin

۱
ارسال:
  

azk84 پاسخ داده:

RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل نشد

(۲۱ شهریور ۱۳۹۲ ۰۸:۱۷ ب.ظ)zimenswall نوشته شده توسط:  من تو این پست خواستم این چندتا زبان رو کنار هم بذارم که تفاوتها و شباهت هاش مشخص باشه که مدیران لطف کردن و بستنش چون قانون انجمن اینه که هر سوالی جدا پرسیده بشه

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

در ضمن من توی انجمن جستجو کردم بیشتر اینها رو ندیدم و اگر هم پرسیده شده باشه معمولا جواب های کلیشه ای بهش داده شده که
۱/ چون dfa و nfa میشه براش کشید منظمه
۲/ چون نمیتونیم لم تزریق براش بیاریم منظمه
۳/ چون با عبارت منظم میشه نوشتش پس منظمه
۴/ چون نمیتونیم بگیم نامنظمه پس منظمه

هدف من تحلیل کلی و تستی واسه اینجور مسائل بود. و چون شکل زبانها باهم مرتبط بود بهتر بود در کنار هم بررسی بشه که بهتر فهمیده بشه.
اما من روم مثل سنگ پای قزوینه Wink سوالا رو جدا جدا پرسیدم


۴. زبان [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 که اصلا ارتباطی ندارن و هر چی خواستن باشن. پس در کل این زبان هم به نظر من سیگما استار هست
اگه همین جور پیش بره تمام زبانها رو سیگما استار فرض میکنم Big Grin

خوب خودت تقریباً درست تحلیل کردی، ولی این زبان نمیتونه سیگما استار باشه، چون حتی اگه w و v رو برابر اپسیلون در نظر بگیریم، باز هم خود u حداقل اندازه‌اش ۱۰ هستش و بنابراین هیچ رشته‌ای با طول کم‌تر از ۱۰ عضو زبان ما نمی‌تونه باشه ;-)

اگه حالت خاص v = w = eps رو در نظر بگیریم، شکل رشته‌های ما میشه u با شرط u| >= 10| که در حقیقت مجموعه‌ی تمام رشته‌های موجود با طول بزرگ‌تر مساوی ۱۰ هستش.
حالا اگه v و w برابر eps هم نباشند، هر چیزی که تولید میشه باز هم جزو همون مجموعه‌ی سابقه و کل زبان ما چیزی بهش اضافه نمیشه. بنابراین کل زبان ما میشه مجموعه‌ی تمام رشته‌های با طول بزرگ‌تر یا مساوی ۱۰ و میدونیم که مجموعه‌ی تمام رشته‌های با طول بزرگ‌تر مساوی ۱۰ یک زبان منظم هستش (هم میشه براش عبارت منظم نوشت و هم لم تزریق و هم NFA و DFA و ...! همه روش‌های موجود برای اثباتش راحته).
مشاهده‌ی وب‌سایت کاربر

ارسال:
  

zimenswall پاسخ داده:

RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل نشد

(۲۱ شهریور ۱۳۹۲ ۰۸:۴۵ ب.ظ)azk84 نوشته شده توسط:  
(21 شهریور ۱۳۹۲ ۰۸:۱۷ ب.ظ)zimenswall نوشته شده توسط:  من تو این پست خواستم این چندتا زبان رو کنار هم بذارم که تفاوتها و شباهت هاش مشخص باشه که مدیران لطف کردن و بستنش چون قانون انجمن اینه که هر سوالی جدا پرسیده بشه

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

در ضمن من توی انجمن جستجو کردم بیشتر اینها رو ندیدم و اگر هم پرسیده شده باشه معمولا جواب های کلیشه ای بهش داده شده که
۱/ چون dfa و nfa میشه براش کشید منظمه
۲/ چون نمیتونیم لم تزریق براش بیاریم منظمه
۳/ چون با عبارت منظم میشه نوشتش پس منظمه
۴/ چون نمیتونیم بگیم نامنظمه پس منظمه

هدف من تحلیل کلی و تستی واسه اینجور مسائل بود. و چون شکل زبانها باهم مرتبط بود بهتر بود در کنار هم بررسی بشه که بهتر فهمیده بشه.
اما من روم مثل سنگ پای قزوینه Wink سوالا رو جدا جدا پرسیدم


۴. زبان [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 که اصلا ارتباطی ندارن و هر چی خواستن باشن. پس در کل این زبان هم به نظر من سیگما استار هست
اگه همین جور پیش بره تمام زبانها رو سیگما استار فرض میکنم Big Grin

خوب خودت تقریباً درست تحلیل کردی، ولی این زبان نمیتونه سیگما استار باشه، چون حتی اگه w و v رو برابر اپسیلون در نظر بگیریم، باز هم خود u حداقل اندازه‌اش ۱۰ هستش و بنابراین هیچ رشته‌ای با طول کم‌تر از ۱۰ عضو زبان ما نمی‌تونه باشه ;-)

اگه حالت خاص v = w = eps رو در نظر بگیریم، شکل رشته‌های ما میشه u با شرط u| >= 10| که در حقیقت مجموعه‌ی تمام رشته‌های موجود با طول بزرگ‌تر مساوی ۱۰ هستش.
حالا اگه v و w برابر eps هم نباشند، هر چیزی که تولید میشه باز هم جزو همون مجموعه‌ی سابقه و کل زبان ما چیزی بهش اضافه نمیشه. بنابراین کل زبان ما میشه مجموعه‌ی تمام رشته‌های با طول بزرگ‌تر یا مساوی ۱۰ و میدونیم که مجموعه‌ی تمام رشته‌های با طول بزرگ‌تر مساوی ۱۰ یک زبان منظم هستش (هم میشه براش عبارت منظم نوشت و هم لم تزریق و هم NFA و DFA و ...! همه روش‌های موجود برای اثباتش راحته).

تشکر از شما
این تحلیل قبلی من بود و به اشتباه خودم هم پی بردم Angelکه زیادی زبان ها رو سیگما استار در نظر میگرفتم
در صورتی که این زبان هیچ رشته کمتر از طول ۱۰ را نمیسازه. پس سیگما استار نمیتونه باشه.

البته بعد از پی بردن به اشتباهم اینطوری جوابم رو اصلاح کردم که قسمت چون متناهی هست پس این قسمتش منظمه و رشته u هم هر چیزی هست (البته با طول بیشتر از ۱۰) پس این زبان راحت میشه براش nfa پیاده کرد. بعبارتی اگر w=v=eps را در نظر بگیریم رشته u یه سیگما استاره با این شرط که حتما طولش بیشتر از ۱۰ باشه .
حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده.
برای nfa هم ساختن رشته u کفایت میکنه به شکلی که اولش ۱۰ تا کاراکتر دلخواه بسازه و بعد هر چی خواست یا نخواست بسازه. و رشته هم که با تعاریف بالا قابل حذفه.


البته قبلا یه اشتباه دیگه ای هم کرده بود در تصور NFA برای این زبان
nfa صحیح ولی غیر بهینه و با تصور غلط: اول رشته u را بسازیم به شکلی که اولش ۱۰ تا کاراکتر دلخواه بسازه و بعد هر چی خواست یا نخواست بسازه و سپس که حالات متناهی دارن رو پیاده میکنیم و به رشته u الحاق میکنیم.
و بعد متوجه شدم که این قسمت دومی همش حالت پایانی شد. پس باید حذف بشه.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

azk84 پاسخ داده:

RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد

(۲۱ شهریور ۱۳۹۲ ۰۹:۱۴ ب.ظ)zimenswall نوشته شده توسط:  حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده.
"رشته قبلی" رو نداریم، بلکه رشته‌های جدیدی که توی این حالت تولید میشن، زیرمجموعه‌ی مجموعه‌ی رشته‌ای هستند که فقط توسط u به تنهایی (توی حالت خاص v = w = eps) تولید میشن. در نتیجه چیز جدیدی به کل مجموعه‌ی ما اضافه نمیشه.

بقیه‌ی تحلیلتون درسته الان :-). پس الان دیگه مشکلی نموند دیگه؟
مشاهده‌ی وب‌سایت کاربر

ارسال:
  

zimenswall پاسخ داده:

RE: چرا زبان { (u w v w^R } منظمه؟ با شرط w<10 حل شد

(۲۱ شهریور ۱۳۹۲ ۱۰:۱۴ ب.ظ)azk84 نوشته شده توسط:  
(21 شهریور ۱۳۹۲ ۰۹:۱۴ ب.ظ)zimenswall نوشته شده توسط:  حالا اگر w و v را بزرگتر کنیم و به آخر u بچسبونیم علنا همون رشته قبلی را داریم که بزرگتر شده و تغییری نکرده.
"رشته قبلی" رو نداریم، بلکه رشته‌های جدیدی که توی این حالت تولید میشن، زیرمجموعه‌ی مجموعه‌ی رشته‌ای هستند که فقط توسط u به تنهایی (توی حالت خاص v = w = eps) تولید میشن. در نتیجه چیز جدیدی به کل مجموعه‌ی ما اضافه نمیشه.

بقیه‌ی تحلیلتون درسته الان :-). پس الان دیگه مشکلی نموند دیگه؟


مشکلات حل شد هر چند از لحاظ فلسفی یه سوالی برام پیش اومد که
"رشته های جدید همون رشته قبلی را داریم" با " رشته جدید زیر مجموعه رشته قبلیه" چه فرقی داره؟
اگر از لحاظ حالت رشته در نظر بگیریم، فرقی بین دوتا جمله بالا نیست ولی اگر بخواهیم u , w , v را در نظر بگیریم حرف شما درسته و رشته جدید ، هیچوقت رشته قبلی نیستند.
درست گفتم دیگه ؟؟
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

azk84 پاسخ داده:

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 تولید می‌کنه همون سیگما استاره).

کلاً اشکالی که گرفته بودم فقط جنبه‌ی فنی داشت ;-)
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

ارسال:
  

zimenswall پاسخ داده:

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 تولید می‌کنه همون سیگما استاره).

کلاً اشکالی که گرفته بودم فقط جنبه‌ی فنی داشت ;-)


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

ظاهرا یه کم باید در جنبه فنی دانشم تجدید نظر کنم که مثل اون مسئله نشه که هر چی زبان میبینم سریع میگم سیگما استاره.Wink
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جزوه اسکن شده " سیستم های توزیع شده " دکتر پدرام arash691 ۸ ۱۴,۰۹۵ ۱۰ آذر ۱۴۰۱ ۰۲:۵۵ ق.ظ
آخرین ارسال: negarrah
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۴۳۴ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  تا به حال شده خدا فرصت زندگی کردن دوباره رو بهت بده؟مرگ از جلوی چشمات رد شده؟ abraham ۲۱ ۱۴,۴۹۷ ۲۰ دى ۱۳۹۹ ۱۰:۵۶ ب.ظ
آخرین ارسال: raam
  چرا یادگیری برنامه نویسی ؟ elecomco ۰ ۲,۲۳۵ ۰۲ خرداد ۱۳۹۹ ۰۲:۵۷ ب.ظ
آخرین ارسال: elecomco
  چرا اعتقادات مذهبی کمرنگ شده؟ m_sardaari ۱۶ ۱۴,۷۱۶ ۰۳ بهمن ۱۳۹۸ ۰۱:۱۲ ق.ظ
آخرین ارسال: saad
  چرا سایت آمازون موفق است؟ mefarhad ۱ ۲۳ ۲۳ آبان ۱۳۹۸ ۰۱:۰۷ ب.ظ
آخرین ارسال: xiaomi
  چرا رأس تنها، عضو ماکسیمال هست؟ پشتکار ۱ ۲,۲۷۹ ۱۰ دى ۱۳۹۶ ۰۷:۳۱ ب.ظ
آخرین ارسال: msour44
  چرا ال جی موفق شد؟ zibaara ۰ ۸ ۱۶ آبان ۱۳۹۶ ۰۶:۱۱ ب.ظ
آخرین ارسال: zibaara
  ایا ریاضیات گسسته همون ساختمان گسسته هستش؟ چرا سنجش اسمش رو تغییر داده؟ ynsdamobb ۲ ۲,۲۱۴ ۲۷ مهر ۱۳۹۶ ۰۲:۲۸ ق.ظ
آخرین ارسال: Jooybari
  چرا ایرانی متخصص عزاداری است؟ H-Arshad ۱ ۳۴ ۰۳ مهر ۱۳۹۶ ۰۳:۰۱ ب.ظ
آخرین ارسال: pishosan

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


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

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close