زبان مستقل از متن

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریه زبان رسمی، زبان مستقل از متن، زبانی است که توسط گرامر مستقل از متن تولید شده باشد. مجموعه زبان‌های مستقل از متن برابر مجموعه زبان‌هایی است که توسط اتوماتون پشته‌ای پذیرفته می‌شود.

مثال‌ها[ویرایش]

یک نمونه زبان مستقل از متن L = \{a^nb^n:n\geq1\} است، که زبان تمام رشته‌های نا تهی با طول زوج است، که تمام نیمه a است، و تمام نیمه دوم b است. L توسط گرامر S\to aSb ~|~ ab، تولید می‌شود، و توسط اتوماتون پشته‌ای M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\}) where \delta پذیرفته می‌شود که به این صورت تعریف می‌شود:

\delta(q_0, a, z) = (q_0, az)

\delta(q_0, a, a) = (q_0, aa)

\delta(q_0, b, a) = (q_1, \varepsilon)

\delta(q_1, b, a) = (q_1, \varepsilon)

\delta(\mathrm{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push})

زبان‌های مستقل از متن کاربردهای بسیاری در زبان‌های برنامه نویسی دارند، برای مثال زبان تمام پرانتزهای نظیر شده توسط گرامر S\to SS ~|~ (S) ~|~ \varepsilon تولید می‌شود. همچنین، اکثر عبارات محاسباتی توسط گرامرهای مستقل از متن تولید می‌شوند.

خواص بستاری[ویرایش]

زبان‌های مستقل از متن نسبت به اعمال زیر بسته است. فرض کنیم که L و P مستقل از متن باشند، زبان‌های پیرو نیز مستقل از متن خواهند بود:

زبان‌های مستقل از متن تحت اشتراک، تفاضل یا متمم بسته نیستند.

خواص تصمیم پذیری[ویرایش]

مسائل پیرو برای دو زبان دلخواه مستقل از متن A و B تصمیم ناپذیرند:

  • برابری: آیا L(A)=L(B)؟
  • آیا L(A) \cap L(B) = \emptyset ؟
  • آیا L(A)=\Sigma^*؟
  • L(A) \subseteq L(B)؟

مسائل پیرو برای زبان‌های دلخواه مستقل از متن تصمیم پذیر هستند:

  • آیا L(A)=\emptyset؟
  • L(A)؟

خواص زبان‌های مستقل از متن[ویرایش]

  • معکوس زبان مستقل از متن، مستقل از متن است ولی متمم آن لزوماً مستقل از متن نیست.
  • هر زبان منظمی، مستقل از متن است به دلیل اینکه می‌تواند با یک گرامر مستقل از متن توصیف شود.
  • اشتراک یک زبان مستقل از متن و یک زبان منظم همیشه یک مستقل از متن است.
  • زبان‌های وابسته به متنی هستند که مستقل از متن نیستند.
  • زبان‌های مستقل از متن تحت اجتماع، الحاق، و ستاره کلین بسته‌اند.

منابع[ویرایش]

Wikipedia contributors، Wikipedia، The Free Encyclopedia، http://en.wikipedia.org/w/index.php?title=Context-free_language&oldid=533520412 (accessed January 29، 2013).