تشخیص منظم یا منظم نبودن یک گرامر برام آسونه آیا راهی وجود داره تا بشود منظم بودن یا نبودن زبان را هم تشخیص داد.؟
مثلاً چطور می شود فهمید [tex]L=\{a^{n!}\: :\: n\ge0\}[/tex] منظم نیست؟
سلام. برای اثبات منظم بودن باید ماشین متناهی طراحی کنید و برای ردش باید از لم تزریق استفاده کنید.
(۲۱ اردیبهشت ۱۳۹۳ ۰۸:۲۲ ب.ظ)Jooybari نوشته شده توسط: سلام. برای اثبات منظم بودن باید ماشین متناهی طراحی کنید و برای ردش باید از لم تزریق استفاده کنید.
برای زبان مستقل از متنم از همین روشها استفاده می شود ؟
آیا منبع مناسبی برای یادگیری لم تزریق وجود دارد؟
(۲۲ اردیبهشت ۱۳۹۳ ۰۲:۳۰ ق.ظ)joyebright نوشته شده توسط:(21 اردیبهشت ۱۳۹۳ ۰۸:۲۲ ب.ظ)Jooybari نوشته شده توسط: سلام. برای اثبات منظم بودن باید ماشین متناهی طراحی کنید و برای ردش باید از لم تزریق استفاده کنید.
برای زبان مستقل از متنم از همین روشها استفاده می شود ؟
آیا منبع مناسبی برای یادگیری لم تزریق وجود دارد؟
جهت اثبات مستقل از متن بودن یک زبان باید برای آن گرامر مستقل از متن ارائه شود و اثبات مستقل از متن نبودن یک زبان با استفاده از لم پامپینگ زبان های مستقل از متن امکان پذیر است.
برای تمرین و یادگیری لم پامپینگ می توانید کتاب لینز را مطالعه کنید و تمرین های آن را حل کنید.
(۲۲ اردیبهشت ۱۳۹۳ ۰۲:۳۰ ق.ظ)joyebright نوشته شده توسط: برای زبان مستقل از متنم از همین روشها استفاده می شود ؟
آیا منبع مناسبی برای یادگیری لم تزریق وجود دارد؟
برای زبان های مستقل از متن راه راحت تر اینه که بیینید آیا می شه واسش ماشین پشته ای طراحی کرد یا نه
مثلا زبان
[tex]L=\{a^nb^kc^nd^k\}[/tex]
a ها رو می ریزیم تو پشته چون باید تعدادآن ها را نگه داریم تا با تعداد c ها مقایسه کنیم
b ها رو هم می ریزیم تو پشته چون باید تعدادآن ها را نگه داریم تا با تعداد d ها مقایسه کنیم
پس الان پایین پشته یه سری a و بالای پشته یه سری b داریم اما الان نوبت مقایسه کردن c ها با تعداد a هاست ولی چیززی که بالای پشته س b است نه a پس با ساختار پشته نمی توان این زبان را پذیرش کرد
این روند برای تشخیص مستقل از متن بودن یا نبودن زبان ها بسیار کارگشاست مثلا اکثر زبان هایی که مستقل از متن نیستند با ساختار lifo پشته مشکل دارند یا نیاز به تعداد استیت های نامتناهی هستند یا ...
البته خودم خیلی از این روند استفاده کردم همیشه جواب داده به جز یه مورد که اونم یه سوال کنکور علوم بود که فک نمی کنم برای مهندسی ها بدن.(البته احتمالا ایراد از دانایی کم من بوده نه از روش)