سوال ۴۹ کنکور ارشد مهندسی کامپیوتر ۱۴۰۳ — کدام مورد، درست است؟

Question

کدام مورد، درست است؟

Accepted Answer

اگر گرامر یک زبان مستقل از متن، گرامری ساده (s-grammar) باشد، آنگاه می‌توان الگوریتم پویش (parsing) با مرتبه خطی از طول رشته‌های آن زبان داشت.

Answer

الگوریتم پویش (parsing) برای زبان‌های مستقل از متن، همیشه از مرتبه نمایی است و به فرم گرامر وابسته نیست.

Answer

اگر گرامر یک زبان مستقل از متن، به فرم نرمال چامسکی باشد، آنگاه می‌توان الگوریتم پویش (parsing) با مرتبه خطی از طول رشته‌های آن زبان داشت.

Answer

اگر قوانین لامبدا (اپسیلون) ( λ - Productions) را از یک گرامر مستقل از متن حذف کنیم، آنگاه می‌توان الگوریتم پویش (parsing) با مرتبه خطی از طول رشته‌های آن زبان داشت.

Parsing complexity of context-free grammars