سلام من یه اشکال اســـــــــاسی نظریه دارم. وقتی یه تست میدن و میگن کدوم یک از زبان های زیر منظم است، منظم نیست، مستقل از متن هست، نیست و.... باید چه طوری تشخیص داد؟؟؟؟؟
فقط میدونم اگر متناهی باشه منظمه!!
کلا کسی میتونه یه جمعبندی از این نکته‌ها یا تکنیک هایی که بشه باهاهش تشخیص داد زبان منظمه، مستقل از متنه و... بکنه؟!
ممنون
۱۳ نفر بازدید کردند اما ۱ نفر هم جوابمو نداده....مرسی!
این چیزی که میگم واسه اثبات نیست ولی واسه خودتون توی تستها میتونید استفاده کنید.
واسه اینکه بگیم منظم نیست باید ببینیم نیاز به حافظه هست یا نه مثلا اگر به شما بگن زبان 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 تا الآن دیده؟!
ساده ترین حالت یعنی اینکه باید تعداد قبلی و بدونی و نصبت به اون عمل بکنی
امروز داشتم یه نگاهی به جزوه باغبانی میکردم، (جزوه‌ای که بچه‌ها برای دانلود گذاشته بودن.) تو عکسی که گذاشتم، منظورش از حافظه متناهی چیه؟
من که فکر میکنم مدرس اینجا دچار اشتباه شده، حافظه، حافظه است، و اگه به حافظه نیاز باشه، زبان منظم نیست.
[attachment=1974]
(۲۴ آذر ۱۳۹۰ ۰۴:۴۳ ب.ظ)ali.alhambra نوشته شده توسط: امروز داشتم یه نگاهی به جزوه باغبانی میکردم، (جزوه‌ای که بچه‌ها برای دانلود گذاشته بودن.) تو عکسی که گذاشتم، منظورش از حافظه متناهی چیه؟سلاام
من که فکر میکنم مدرس اینجا دچار اشتباه شده، حافظه، حافظه است، و اگه به حافظه نیاز باشه، زبان منظم نیست.
داشتم کامنت دوستان رو مرور میکردم گفتم خالی از لطف نباشه یه سری توضیحات تکمیلی در باب تکمل توضیح دوستان بدم .
اولا جزوه یی که نوشتید کاملا درسته اما چطور!!!
یه نگرش نادرست وجود داره که میگن اگر زبانی حافظه خواست منظم نیست ..این نحو بیان اشتباهست و اینگونه نیست در واقع ما در زبان منظم هم حافظه داریم اما این حافظه محدود هست و با حالتها شبیه سازی میشه وقتی از یک حالت به حالت دیگر میرویم یعنی داریم گذشته رشته رو به خاطر میسپاریم و این یعنی حافظه .
مثلا زبان [tex]a^{1000000}b^{1000000}[/tex]
یک زبان منظم هست و ماشین منظم این زبان [tex]2 * 1000000[/tex] حالت دارد .در واقع همانطور که واقف هستید ما این حافظه رو با حالتها ایجاد کردیم ووقتی از یکی حالت به حالت دیگر میرویم گذشته شته رو به خاطر میسپاریم .
من عمدا تعداد ارقام رو زیاد وارد کردم چون میخوام یه نتیجه گیری کنم .
ببنید اگر ما نیاز به حافظه محدود و مشخص داشته باشیم انوقت میوانیم این حافظه محدود را با حالتها شبیه سازی کنیم و زبان منظم خواهد بود اگر در این مثال یک ملیارد یا بیشتر هم می بود باز هم منظم هست .
اما در رشته [tex]a^{n}b^{n}[/tex]
از انجا که مقدار [tex]n[/tex]
مشخص نیست لذا نمی توانیم هیچ تصمیم گیری در رابطه با اینکه رشته ما به چقدر حافظه نیاز دارد داشته باشیم لذاا این زبان نیاز به حافظه نامشخص و به عبارتی نامحدود دارد که قابل شبیه سازی به وسیله حالتها نیست
نتیجه گیری:
پس ما در زبان منظم هم حافظه داریم اما حافظه محدود و کاملا مشخص هست (چون تعداد حالتها مشخص هست )و این حافظه با حالتها شبیه سازی میشود .
امیدوارم تونسته باشم کمکی کرده باشم.
(۲۴ آذر ۱۳۹۰ ۰۵:۰۸ ب.ظ)hadi_m نوشته شده توسط:(24 آذر ۱۳۹۰ ۰۴:۴۳ ب.ظ)ali.alhambra نوشته شده توسط: امروز داشتم یه نگاهی به جزوه باغبانی میکردم، (جزوه‌ای که بچه‌ها برای دانلود گذاشته بودن.) تو عکسی که گذاشتم، منظورش از حافظه متناهی چیه؟سلاام
من که فکر میکنم مدرس اینجا دچار اشتباه شده، حافظه، حافظه است، و اگه به حافظه نیاز باشه، زبان منظم نیست.
داشتم کامنت دوستان رو مرور میکردم گفتم خالی از لطف نباشه یه سری توضیحات تکمیلی در باب تکمل توضیح دوستان بدم .
اولا جزوه یی که نوشتید کاملا درسته اما چطور!!!
یه نگرش نادرست وجود داره که میگن اگر زبانی حافظه خواست منظم نیست ..این نحو بیان اشتباهست و اینگونه نیست در واقع ما در زبان منظم هم حافظه داریم اما این حافظه محدود هست و با حالتها شبیه سازی میشه وقتی از یک حالت به حالت دیگر میرویم یعنی داریم گذشته رشته رو به خاطر میسپاریم و این یعنی حافظه .
مثلا زبان [tex]a^{1000000}b^{1000000}[/tex]
یک زبان منظم هست و ماشین منظم این زبان [tex]2 * 1000000[/tex] حالت دارد .در واقع همانطور که واقف هستید ما این حافظه رو با حالتها ایجاد کردیم ووقتی از یکی حالت به حالت دیگر میرویم گذشته شته رو به خاطر میسپاریم .
من عمدا تعداد ارقام رو زیاد وارد کردم چون میخوام یه نتیجه گیری کنم .
ببنید اگر ما نیاز به حافظه محدود و مشخص داشته باشیم انوقت میوانیم این حافظه محدود را با حالتها شبیه سازی کنیم و زبان منظم خواهد بود اگر در این مثال یک ملیارد یا بیشتر هم می بود باز هم منظم هست .
اما در رشته [tex]a^{n}b^{n}[/tex]
از انجا که مقدار [tex]n[/tex]
مشخص نیست لذا نمی توانیم هیچ تصمیم گیری در رابطه با اینکه رشته ما به چقدر حافظه نیاز دارد داشته باشیم لذاا این زبان نیاز به حافظه نامشخص و به عبارتی نامحدود دارد که قابل شبیه سازی به وسیله حالتها نیست
نتیجه گیری:
پس ما در زبان منظم هم حافظه داریم اما حافظه محدود و کاملا مشخص هست (چون تعداد حالتها مشخص هست )و این حافظه با حالتها شبیه سازی میشود .
امیدوارم تونسته باشم کمکی کرده باشم.
صحبت‌های شما درست،،، البته اینکه حالت‌های داخلی اسمش بذاریم حافظه متناهی یا نذاریم خیلی اهمیتی نداره...
ولی تو اون جزوه، اگر فرض بر این بوده که حالت‌های داخلی، حافظه هستند، باز هم اون تقسیم بندی اشتباه میشه،
چون گفته: زبان نامتناهی سه حالت داره (نیاز به حافظه ندارد-نیاز به حافظه متناهی دارد-نیاز به حافظه نامتناهی دارد)
اینجا جمله نیاز به حافظه ندارد نامفهوم میشه، یعنی منظورش اینه که ماشین اصلا حالت‌های داخلی نداره!!!!!!!!!!؟؟؟؟؟؟؟؟
نگاه کنید من گفتم برای زبان منظم حافظه رو شبیه سازی میکنیم و این کار رو با حالتها انجام میدیم .نگفتم که حالتها در زبان منظم منطبق بر حافظه است مثلا برای [tex]a^{*}[/tex] ایا لزومی دارد که گذشته رشته رو به خاطر بسپاریم ؟ مسما نیاز نداریم و فقط کافیست رشته رو پیمایش کنیم ماشین این زبان فقط لازمه که رشته رو از لحاظ اینکه رشته شامل کاراکتر a باشد چک کند و یا به نحوی کنترل کند و برای این کنترل نیاز به به خاطر سپاری گذشته رشته نداریم واین کنترل را به صورت درجا انجا میدهد یعنی در هر لحظه یک کاراکتر میخواند و چک میکند ایا کاراکتر a هست یا خیر؟وبرای چک کردن کاراکتر n ام, گذشته رشته را دور میریزد چون دلیلی برای نگهداری ان ندارد وبه نحوی ماشین این زبان فراموش کار است .
اما برای رشته [tex]a^{ }[/tex] چطور؟ نظرتون راجب این رشته چیه؟ ایا نیاز هست گذشته رشته رو به خاطر بسپاریم ؟اگر هست تا چند کاراکتر؟
در هر حال ما وقتی سراغ حافظه میرویم که نیاز داشته باشیم گذشته رشته رو نگه داری کنیم و اگر این به خاطر سپاری گذشته رشته محدود باشد مطمئنا زبان منظم هست چون میتونا شبیه سازی کرد اما وقتی ندانیم که گذشته رشته را تا کجا باید به خاطر بسپاریم بحث حافظه های قوی تری از جمله پشته و نوار ماشین تورینگ به میان میاد که قدرت بیشتری در به خاطر سپاری گذشته رشته دارند .