المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:نظریه زبان ها و ماشین ها:سوال ۲

سوال ۲

تعیین کنید زبان‌های زیر مستقل از متن هستند یا خیر ؟ اگر جواب‌تان منفی است اثبات کنید و اگر مثبت است یا گرامر آن را بنویسید یا ‎NPDA‎ آن را رسم کنید.

  1. ‎ ‎$L_1 = \{0^m1^n2^p| m \neq n\ \ or\ \ n \neq p‎, ‎\ \ m‎, ‎n‎, ‎p > 0 \}$
  2. ‎ ‎$L_2 = \{0,1,2\}^*‎ - ‎L_1$

ابزار صفحه