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

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

در نظریه زبان رسمی، یه زبان مستقل از متن زبانیست که از یک گرامر مستقل از متن ساخته شده باشد. گرامرهای مستقل از متن متفاوت میتوانند زبان مستقل از متن یکسانی تولید کنند. مهم است که خصوصیات زبان از خصوصیات گرامر مشخص تمایز داده شود.

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

زبان مستقل از متن کاربرد بسیاری در زبان های برنامه نویسی دارد؛ برای مثال : زبان پرانتزهای هم تراز که توسط گرامر S→SS|(S)|ε ساخته میشود. همچنین بیشتر عبارتهای حسابی توسط گرامر مستقل از متن تولید میشوند.

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

نمونه اولیه یک زبان مستقل از متن {L = {anbn : n ≥ 1، زبان همه رشته های با طول زوج غیر تهی،که تمام نصفه اول a هستند و نصفه دوم b میباشند. L توسط گرامر S→aSb|ab ساخته میشود. این زبان منظم نیست و توسط یک ماشین پشته ای زیر پذیرفته میشود. ({M = ({q0,q1,qf} , {a,b} , {a,z} , δ , q0 , z , {qf که δ به صورت زیر تعریف میشود :

(δ(q0,a,z) = (q0, az

(δ(q0,a,a) = (q0, aa

(δ(q0,b,a) = (q1, ε

(δ(q1,b,a) = (q1, ε

زبان های مستقل از متن غیر مبهم یک زیرمجموعه مخصوص از زبان های مستقل از متن هستند: زبان های مستقل از متن ذاتا مبهم وجود دارد. یک مثال برای زبان مستقل از متن ذاتا مبهم اجتماع {anbmcmdn|n,m>0} با {anbncmdm | n,m >0} است. این مجموعه مستقل از متن است زیرا اجتماع دو زبان مستقل از متن، مستقل از متن است. اما هیچ راهی برای تجزیه کردن غیر مبهم رشته ها در زیر مجموعه {anbncndn | n > 0} که اشتراک این دو زبان است، وجود ندارد.

زبان هایی که مستقل از متن نیستند[ویرایش]

مجموعه {anbncndn | n > 0} یک زبان وابسته به متن است، اما یک گرامر مستقل از متن که این زبان را تولید کنم وجود ندارد. پس زبانهای وابسته به متن وجود دارند که مستقل از متن نیستند.

برای اثبات اینکه یک زبان مستقل از متن نیست، ممکن است از لم تزریق برای زبان های مستقل از متن یا روش های دیگر مانند لم اُگدن یا نظریه پاریخ استفاده شود.

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

زبان های مستقل از متن تحت اعمال زیر بسته اند. اگر L و P زبان های مستقل از متن باشند، زبان های زیر هم مستقل از متن هستند:

  • LυP
  • برگشت L
  • L.P
  • *L
  • برد (φ(L تحت همریختیφ
  • برد (φ-1(L تحت معکوس همریختی φ-1
  • شیفت چرخشی L (زبان {vu : uvєL})

غیر بستار تحت اشتراک و مکمل و تفاوت[ویرایش]

زبان های مستقل از متن تحت اشتراک بسته نیستند. این میتواند در زبان {A = {anbncm | n,m ≥ 0 و {B = {ambncn | n,m ≥ 0 که هر دو مستقل از متن هستند دیده شود.

اشتراک به صورت {A∩B = {anbncn | n ≥ 0 است که میتواند توسط لم تزریق برای زبان های مستقل از متن نشان داده شود که مستقل از متن نیست.

زبان های مستقل از متن همچنین تحت مکمل هم بسته نیستند، برای هر زبان A و B :

A∩B = (AcυBc)c

زبان های مستقل از متن تحت تفاوت هم بسته نیستند :

Lc = Σ* \ L

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

https://en.wikipedia.org/wiki/Context-free_language