۱۳ نفر بازدید کردند اما ۱ نفر هم جوابمو نداده....مرسی!

این چیزی که میگم واسه اثبات نیست ولی واسه خودتون توی تستها میتونید استفاده کنید.

واسه اینکه بگیم منظم نیست باید ببینیم نیاز به حافظه هست یا نه مثلا اگر به شما بگن زبان a^n b^n منظمه شما سعی میکنید واسش dfa بکشید اما می بینید که کشیدن dfa ممکن نیست چون شما نیاز دارید که بدونید چقدر a خوندید که به همون تعداد b بخونید.پس منظم نیست.

اگر بشه با پشته پیاده سازیش کرد یا واسش گرامر مستقل از متن نوشت مستقل از متنه.
مثلا همون گرامری که نشد واسش dfa کشید میشه راحت واسش گرامر نوشت یا اینکه گفت توی پشته به ازای هر b که میخونیم یه a خط میزنیم و ..... (یه ایده کلی که بدونیم میشه با پشته پیاده سازی کرد)

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

کلا این و یادتون باشه که زبان های منظم نیاز به حافظه ندارن.مثلا اون مثالی که آفاق خانوم فرمودن ما برای تولید یک رشته از این زبان‌، چون تعداد a‌ها و b‌ها با هم برابره پس وقتی n تا a تولید می کنیم باید n تا هم b تولید بکنیم که این نیاز به حافظه داره پس منظم نیست. ولی می تونیم این زبان و با یک ماشین pda یعنی یه دونه پشته پیاده سازی بکنیم.به تعداد a‌ها push می کنیم و به تعداد b‌ها pop.پس تونستیم با یه دونه پشته پیاده سازی بکنیم بنابراین CF یا همون مستقل از متن هستش. ولی اگه مثلا a^n b^n c^n بود می بینیم که نمی تونیم با یدونه پشته پیاده سازی بکنیم .بنابراین مثلا اگه n=2 باشه دو تا پشته نیاز داریم که می تونیم تو پشته اول دو تا a رو push بکنیم.بعد دو تا b رو تو پشته اول pop می کنیم و همزمان تو پشته دوم push می کنیم.بعدش به تعداد c هامون که دو تا هستش از پشته دوم pop می کنیم.می بینیم که دو تا پشته خالی شدن.پس این زبان چون به دو تا پشته نیاز داره یعنی ۲-pda هستش بنابراین CS یا وابسته به متن هستش

خیلی متشکر دوستان
فقط منظور از حافظه مثلا چیزی مثل پشته است؟ یا به اصطلاح مثلا یه جایی که بشه توش نوشت که مثلا چندتا a تا الآن دیده؟!

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

ساده ترین حالت یعنی اینکه باید تعداد قبلی و بدونی و نصبت به اون عمل بکنی

امروز داشتم یه نگاهی به جزوه باغبانی می‌کردم، (جزوه‌ای که بچه‌ها برای دانلود گذاشته بودن.) تو عکسی که گذاشتم، منظورش از حافظه متناهی چیه؟
من که فکر میکنم مدرس اینجا دچار اشتباه شده، حافظه، حافظه است، و اگه به حافظه نیاز باشه، زبان منظم نیست.

(۲۴ آذر ۱۳۹۰ ۰۴:۴۳ ب.ظ)ali.alhambra نوشته شده توسط:  امروز داشتم یه نگاهی به جزوه باغبانی می‌کردم، (جزوه‌ای که بچه‌ها برای دانلود گذاشته بودن.) تو عکسی که گذاشتم، منظورش از حافظه متناهی چیه؟
من که فکر میکنم مدرس اینجا دچار اشتباه شده، حافظه، حافظه است، و اگه به حافظه نیاز باشه، زبان منظم نیست.

سلاام
داشتم کامنت دوستان رو مرور میکردم گفتم خالی از لطف نباشه یه سری توضیحات تکمیلی در باب تکمل توضیح دوستان بدم .
اولا جزوه یی که نوشتید کاملا درسته اما چطور!!!
یه نگرش نادرست وجود داره که میگن اگر زبانی حافظه خواست منظم نیست ..این نحو بیان اشتباهست و اینگونه نیست در واقع ما در زبان منظم هم حافظه داریم اما این حافظه محدود هست و با حالتها شبیه سازی میشه وقتی از یک حالت به حالت دیگر میرویم یعنی داریم گذشته رشته رو به خاطر میسپاریم و این یعنی حافظه .
مثلا زبان $a^{1000000}b^{1000000}$

یک زبان منظم هست و ماشین منظم این زبان $2 * 1000000$ حالت دارد .در واقع همانطور که واقف هستید ما این حافظه رو با حالتها ایجاد کردیم ووقتی از یکی حالت به حالت دیگر میرویم گذشته شته رو به خاطر میسپاریم .
من عمدا تعداد ارقام رو زیاد وارد کردم چون میخوام یه نتیجه گیری کنم .
ببنید اگر ما نیاز به حافظه محدود و مشخص داشته باشیم انوقت میوانیم این حافظه محدود را با حالتها شبیه سازی کنیم و زبان منظم خواهد بود اگر در این مثال یک ملیارد یا بیشتر هم می بود باز هم منظم هست .
اما در رشته $a^{n}b^{n}$
از انجا که مقدار $n$
مشخص نیست لذا نمی توانیم هیچ تصمیم گیری در رابطه با اینکه رشته ما به چقدر حافظه نیاز دارد داشته باشیم لذاا این زبان نیاز به حافظه نامشخص و به عبارتی نامحدود دارد که قابل شبیه سازی به وسیله حالتها نیست
نتیجه گیری:
پس ما در زبان منظم هم حافظه داریم اما حافظه محدود و کاملا مشخص هست (چون تعداد حالتها مشخص هست )و این حافظه با حالتها شبیه سازی میشود .
امیدوارم تونسته باشم کمکی کرده باشم.