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

سلام
درمورد تشخیص اینکه آیا زبان منظم و یا مستقل از متن هست روشی به غیر از روش های( آیا حافظه و یا استک نیاز داره )وجود داره ؟
ممنون

میشه این حالت رو هم در نظر گرفت که:
اگر یک زبان متناهی بود دیگه لازم نیس به گرامر دقت کنیم و سریع میگیم منظمه؟

(26 آبان 1390 11:47 ب.ظ)NoOne نوشته شده توسط: [ -> ]میشه این حالت رو هم در نظر گرفت که:
اگر یک زبان متناهی بود دیگه لازم نیس به گرامر دقت کنیم و سریع میگیم منظمه؟

سلام
زبانی که منظم هست به علت اینکه داره از DFA استفاده میکنه، برای نگهداری حافظه محدودیت داره
ولی زبان مستقل از متن اینطور نیست، با استفاده از پشته این محدودیت رو نداره.
مثال:
1 a^10000000b^1000000
a^100b^100 2
a^nb^n 3
a*b* 4
زبان 1 و 2و 4 منظم هستند چون ما بعد از اینکه تعداد محدودی a در رشته داریم، b آمده
ولی در مورد زبان 3 اینطور نیست، چون تعداد a که باید قبل b در رشته تولید شود، معلوم نیست