اول برای سادگی فرض کنید که مینیمم طول u می‌تونه ۰ باشه، مینیمم طول w می‌تونه ۱ باشه و حداکثر طول v هم می‌تونه ۱ باشه (یعنی v یا اپسیلونه یا فقط یک کاراکتر). در این حالت داریم:

دیگه نمیشه مثل سؤالای قبلیتون عمل کرد، چون این زبان فقط و فقط رشته‌های خاصی رو می‌پذیره که حداقل دو زیررشته‌ی متقارن در انتهای رشته اومده باشه که بینشون حدکثر یک کاراکتر فاصله هست. مثلاً $abbb\mathbf{abba}$ یا $abbb\mathbf{ab}a\mathbf{ba}$ رو می‌پذیره ولی abcab رو دیگه زبانمون نمیپذیره. این زبان نظم خاصی مثل قبلیا نداره و مثل قبلیا نمیتونیم از یک حالت خاصش برسیم به کل زبان، بلکه دقیقاً هر عدد متفاوت برای طول w و wR و u و v به ما کلی رشته‌ی جدید میده که توی حالت‌های دیگه نیست. تا اینجای تحلیل هنوز نمیشه نتیجه گرفت که منظمه یا نه (توی قبلیا تا همین مرحله می‌دیدیم که یک حالت خاص همه رشته‌های ممکن رو تولید می‌کنه و کار تموم می‌شد). ولی ما برای این زبان مجبوریم که حتماً حتماً از یک حافظه استفاده کنیم تا w و wR رو تشخیص بدیم، وگرنه کلی از رشته‌هایی که تولید نشدند رو نمی‌تونیم تولید کنیم. همین حافظه باعث میشه که زبان نامنظم باشه.

حالا اگه اون پیش‌شرط‌های خط اول توضیحمو یکی یکی حذف کنید می‌بینین که باز هم تأثیری روی استدلالمون نمی‌ذاره و همچنان زبانمون منظم باقی میمونه :-)

بدون لم تزریق و ابزارهای تشخیص منظم بودن و نبودن زبان یک کم وقت می‌بره تا بتونین با یه نگاه بگین منظمه یا نه، برای همین طبیعیه اگه بخش‌هایی از حرف‌هام رو متوجه نشین (بگذریم از این که منم احتمالاً خوب نگفتم :دی).

اگه جایی نیاز به توضیح بیشتر داره در خدمتم :-)

اول تشکر از دوستانی که همکاری کردند. واقعا دوستان قسمت نظریه زبان ، فعال و دقیق هستند

$\left \{ uwvw^{R\R}:u,v,w\epsilon \sum^{*},\left|u\right|\geqslant 10 ,\left|v\right |\leqslant 10 ,\left | w \right |\geqslant10\right \}$

هر چند دوستان جواب رو دادند ولی من بازم یه نتیجه گیری میکنم
برای زبان بالا اول حداقل رشته رو در نظر میگیریم. یعنی زمانی که v=0 و u=10 و w=10
یعنی رشته بدست آمده میشه این : $uww^{R\R}$ . بعبارتی میشه رشته ای که اولش ۱۰ عنصر از زبان را داشته باشه و بعدش یک رشته ۲۰ عنصری که ۱۰ تای دومش معکوس ۱۰ تای اول باشه.
و اگر همینطور طول رشته های w و u را زیاد کنیم، رشته های جدیدی بدست می آید که با مجموعه رشته های قبلی متفاوت است. و بقول دوستمون azk84 از این تفاوت نمیشه برداشت کرد که نامنظمه بلکه فقط به این نتیجه میرسیم که از حالت خاص نمیتونیم به حالت کلی زبان برسیم.

نامنظم بودن زبان از اونجا مشخص میشه که در مجموعه رشته های تولیدی همیشه باید عبارت $wvw^{R\R}$ را داشته باشیم. حالا چه v اون وسط باشه و چه نباشه. در ضمن v محدوده. پس برای تولید این رشته باید حافظه ای داشته باشیم تا بتوانیم w را ذخیره کرده و سپس $w^{R\R}$ را بسازیم که خب زبان های منظم هم حافظه ندارند و نتیجه میشود که زبان مورد نظر ما نامنظمه.
البته با لم تزریق هم میشه اثبات کرد و توسط دوستان گفته شد ولی از حوصله کنکوری ما خارجه.

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

خودشه :دی

پ.ن. : در مورد این عقیده که لم تزریق به درد کنکور نمیخوره باید بگم اگه روی لم تزریق هم مسلط بشین به درد کنکور می‌خوره. کنکور کارشناسی ارشد یه فرق اساسیش با کنکور سراسری اینه که وقت به اندازه‌ی کافی برای هر تست هست و میشه از راه‌های طولانی‌تر هم در صورت لزوم استفاده کرد. بالاخره لم تزریق هم یک ابزار هستش و بعضی جاها به درد کارمون می‌خوره، پس کلاً نذارینش کنار و سعی کنین روش مسلط شین :-)

(۲۶ شهریور ۱۳۹۲ ۰۷:۵۸ ب.ظ)azk84 نوشته شده توسط:  پ.ن. : در مورد این عقیده که لم تزریق به درد کنکور نمیخوره باید بگم اگه روی لم تزریق هم مسلط بشین به درد کنکور می‌خوره. کنکور کارشناسی ارشد یه فرق اساسیش با کنکور سراسری اینه که وقت به اندازه‌ی کافی برای هر تست هست و میشه از راه‌های طولانی‌تر هم در صورت لزوم استفاده کرد. بالاخره لم تزریق هم یک ابزار هستش و بعضی جاها به درد کارمون می‌خوره، پس کلاً نذارینش کنار و سعی کنین روش مسلط شین :-)

ممنون
من تا حد زیادی لم و nfa کار کردم ولی نمیدونم چرا بازم مشکل داشتم.
شاید توی مفهوم منظم بودن و نبودن مشکل داشتم. ولی این تحلیل هایی که گفته شد واقعا خدا بود.

ولی فعلا لم و nfa و عبارت منظم رو گذاشتم زاپاس.

(۲۶ شهریور ۱۳۹۲ ۱۰:۴۵ ب.ظ)zimenswall نوشته شده توسط:  من تا حد زیادی لم و nfa کار کردم ولی نمیدونم چرا بازم مشکل داشتم.
شاید توی مفهوم منظم بودن و نبودن مشکل داشتم. ولی این تحلیل هایی که گفته شد واقعا خدا بود.

ولی فعلا لم و nfa و عبارت منظم رو گذاشتم زاپاس.

خوشحالم این بحث‌ها براتون مفید بوده :-)

سلام. اینی که سوالات مشابه رو کنار هم قرار میدید کاملاً منطقیه فقط چندین بار داده شده به بعضی سوالات پاسخ داده نشده. یعنی کاربرایی که پاسخ میدن لزوماً همه سوالات رو بلد نیستن و یا به بعضیشون پاسخ اشتباه میدن و یا به بعضیشون پاسخ نمیدن. از اینکه رعایت کردید متشکرم.

پاسخ سوالتون: رشته $b^{10}a^Mb^{10}a^M$ رو درنظر بگیرید. درنظر میگیریم $u=b^{10};v=b^{10};w=a^M$. این رشته عضو زبانه. به ازای تمام حالاتی که رشته رو به $xyz$ شکوند رشته $xy^0z$ عضو زبان نخواهد بود. چون اگه از تعداد aهای عضو w کم بشه تقارن بهم میخوره. اگر هم از b های عضو u کم بشه که شرط u نقض میشه.

موفق باشید.

عذرخواهی میکنم. من زبان سوال ۵ رو درنظر گرفتم.

شرط طول رشته ها رو مثل سوال ۵ میگیرم. رشته $b^{10}a^{2M 1}ba^{2M 1}b$ رو درنظر میگیریم. $w=a^{2M 1}$.

(۲۲ شهریور ۱۳۹۲ ۰۳:۴۵ ب.ظ)Jooybari نوشته شده توسط:  سلام. اینی که سوالات مشابه رو کنار هم قرار میدید کاملاً منطقیه فقط چندین بار داده شده به بعضی سوالات پاسخ داده نشده. یعنی کاربرایی که پاسخ میدن لزوماً همه سوالات رو بلد نیستن و یا به بعضیشون پاسخ اشتباه میدن و یا به بعضیشون پاسخ نمیدن. از اینکه رعایت کردید متشکرم.

پاسخ سوالتون: رشته $b^{10}a^Mb^{10}a^M$ رو درنظر بگیرید. درنظر میگیریم $u=b^{10};v=b^{10};w=a^M$. این رشته عضو زبانه. به ازای تمام حالاتی که رشته رو به $xyz$ شکوند رشته $xy^0z$ عضو زبان نخواهد بود. چون اگه از تعداد aهای عضو w کم بشه تقارن بهم میخوره. اگر هم از b های عضو u کم بشه که شرط u نقض میشه.

موفق باشید.

البته zimenswall گفته بودند که نمی‌خوان از طریق لم تزریق و اینا حل بشه. فکر کنم روش شما حل مشکل ایشون نباشه. ولی دستتون درد نکنه :-)

(۲۲ شهریور ۱۳۹۲ ۰۵:۲۳ ب.ظ)azk84 نوشته شده توسط:  البته zimenswall گفته بودند که نمی‌خوان از طریق لم تزریق و اینا حل بشه. فکر کنم روش شما حل مشکل ایشون نباشه. ولی دستتون درد نکنه :-)

ببخشید منظورتون چیه که نمیخان با لم تزریق حل بشه. شما برای اثبات منظم نبودن این زیان راه دیگه ای سراغ دارید؟

(۲۳ شهریور ۱۳۹۲ ۰۹:۲۵ ق.ظ)Jooybari نوشته شده توسط:  

(22 شهریور ۱۳۹۲ ۰۵:۲۳ ب.ظ)azk84 نوشته شده توسط:  البته zimenswall گفته بودند که نمی‌خوان از طریق لم تزریق و اینا حل بشه. فکر کنم روش شما حل مشکل ایشون نباشه. ولی دستتون درد نکنه :-)

ببخشید منظورتون چیه که نمیخان با لم تزریق حل بشه. شما برای اثبات منظم نبودن این زیان راه دیگه ای سراغ دارید؟

منظورم این بود که مشخصاً توی پست اول اعلام کرده که نمی‌خواد از لم تزریق استفاده بشه، وگرنه حق کاملاً با شماست و راهتون هم درسته :-)

بله خوب، بالاخره لم تزریق یک ابزاره، ابزارهای دیگه‌ای هم هست. ولی با توجه به پست اول به نظرم خواسته شده یه جورایی به صورت شهودی اثبات بشه که نامنظمه، نه با استفاده از ابزارها. توی پست دوم هم حدوداً سعی شده به صورت شهودی گفته بشه :دی

(۲۳ شهریور ۱۳۹۲ ۰۹:۲۵ ق.ظ)Jooybari نوشته شده توسط:  

(22 شهریور ۱۳۹۲ ۰۵:۲۳ ب.ظ)azk84 نوشته شده توسط:  البته zimenswall گفته بودند که نمی‌خوان از طریق لم تزریق و اینا حل بشه. فکر کنم روش شما حل مشکل ایشون نباشه. ولی دستتون درد نکنه :-)

ببخشید منظورتون چیه که نمیخان با لم تزریق حل بشه. شما برای اثبات منظم نبودن این زیان راه دیگه ای سراغ دارید؟

تشکر از jooybari
دلیل اینکه نمیخواستم از لم تزریق استفاده بشه چون حس میکنم لم تزریق یه چیز بدرد نخور سر جلسه کنکوره. مخصوصا حالا بیا و مقدار m رو پیدا کن چنده. هر چند لم تزریق رو خوب بلدم و مثال هم خوب ازش حل کردم ولی حس میکنم لم گیج کنندست.
و تازه به درد اثبات منظم بودن زبان هم نمیخوره.

ولی استدالال هایی که توی چند تا پست قبلی در مورد منظم بودن گفته شد مخصوصا توسط آقای azk84، واقعا بهتر از استفاده از لم تزریق و کشیدن dfa هست و آدم کمتر گیج میشه.

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

قصد من حل تست گونه اینجور سوالات بود نه حل تشریحی. من و دوستان به شخصه خیلی روی بحث عبارات منظم مسلط شدیم، امیدوارم دوستان دیگه هم مثل ما فیض ببرن.

(۲۳ شهریور ۱۳۹۲ ۱۰:۵۱ ق.ظ)zimenswall نوشته شده توسط:  قصد من حل تست گونه اینجور سوالات بود نه حل تشریحی. من و دوستان به شخصه خیلی روی بحث عبارات منظم مسلط شدیم، امیدوارم دوستان دیگه هم مثل ما فیض ببرن.

به نظر من خیلی مفید بودن این سوالاتون و تحلیلای بچه ها .من که نسبت به قبل خیلی یاد گرفتم
اگه بازم از این سوالا داشتین بذارین مثلا در مورد مستقل از متنا و .... که با اونا هم آشنا بشیم .
موفق باشید

(۲۳ شهریور ۱۳۹۲ ۱۱:۰۳ ق.ظ)nazanin_sh نوشته شده توسط:  

(23 شهریور ۱۳۹۲ ۱۰:۵۱ ق.ظ)zimenswall نوشته شده توسط:  قصد من حل تست گونه اینجور سوالات بود نه حل تشریحی. من و دوستان به شخصه خیلی روی بحث عبارات منظم مسلط شدیم، امیدوارم دوستان دیگه هم مثل ما فیض ببرن.

به نظر من خیلی مفید بودن این سوالاتون و تحلیلای بچه ها .من که نسبت به قبل خیلی یاد گرفتم
اگه بازم از این سوالا داشتین بذارین مثلا در مورد مستقل از متنا و .... که با اونا هم آشنا بشیم .
موفق باشید

هر چند هنوز مستقل از متن رو نخوندم ولی با مواردی که از مستقل از متن تو ذهنم مونده به یقین از این تحلیلها میشه استفاده کرد.

سلام
فکر کنم با مقایسه دوتا سوال بشه جواب قانع کننده داد.
در سوال اول ما میتوانیم w=0 & v=0 قرار دهیم در نتیجه فقط رشته ی u>=10 میماند. هر رشته ای که با طول بیشتر از ۱۰ تولید شد دو حالت داشت : یا اینکه به شکل uwvwR بودند که در اینصورت عضو زبان بودند . یا اینکه از این شکل پیروی نمیکردند وفقط طول رشته بیشتر از ۱۰ بود که باز هم توسط زبان پذیرفته میشدند چون همانطور که ذکر شد با شرط v =0 & w =0 میتوان این رشته ها را تولید کرد .
اما در این زبان ما در هر صورت باید حد اقل wwR را انتهای رشته هایمان داشته باشیم و نمیتوانیم w =0 در نظر بگیریم . بنابراین برای پیاده سازی چنین رشته ای حتما به حافظه نیاز خواهیم داشت چون به هیچ شکلی نمیتوان از انتهای آن صرف نظر کرد . بنابراین این زبان نامنظم است .