تالار گفتمان مانشت

دوستان راهنمایی کنید
چه جوری میشه گزینه یک؟

زبان L1 یک زبان مستقل از متنه. هر چند تعداد حالاتش محدوده ولی با همین تعداد حالات میتونه زبانی نامتناهی را بپذیره (یه موقع منظم در نظر نگیرید)
زبان L2 منظمه. چون وقتی پشته محدود به ظرفیت خاصی بشه ، زبانی که توسط این پشته پذیرفته بشه ، منظمه
L1 -L2 تفاضل منظم در مجموعه زبان های مستقل از متنه و زبان های مستقل نسبت به تفاضل منظم بسته هستند
پس زبان نهایی میشه مستقل از متن
هر زبان مستقل از متن هم توسط یک PDA پذیرفته میشه و طبق یک قضیه ای برای PDA یک PDA معادل با دو حالت میتوان ساخت که زبان مورد نظر را بپذیره

(21 بهمن 1392 03:05 ب.ظ)masoud67 نوشته شده توسط: [ -> ]زبان L1 یک زبان مستقل از متنه. هر چند تعداد حالاتش محدوده ولی با همین تعداد حالات میتونه زبانی نامتناهی را بپذیره (یه موقع منظم در نظر نگیرید)
زبان L2 منظمه. چون وقتی پشته محدود به ظرفیت خاصی بشه ، زبانی که توسط این پشته پذیرفته بشه ، منظمه
L1 -L2 تفاضل منظم در مجموعه زبان های مستقل از متنه و زبان های مستقل نسبت به تفاضل منظم بسته هستند
پس زبان نهایی میشه مستقل از متن
هر زبان مستقل از متن هم توسط یک PDA پذیرفته میشه و طبق یک قضیه ای برای PDA یک PDA معادل با دو حالت میتوان ساخت که زبان مورد نظر را بپذیره

ممنونم.
الهام جان از شما هم ممنون