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

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

مجموعه همه زبانهای مستقل از متن با مجموعه زبانهای پذیرفته شده توسط ماشین پشته ای یکسان است که باعث می‌شود این زبان متمایل به تجزیه شود. در واقع برای گرامر مستقل از متن داده شده یک راه مستقیم برای تولید یک ماشین پشته ای برای آن گرامر وجود دارد و برای ساخت یک گرامر از ماشین پشته ای نیز راهی وجود دارد.^[1]

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

مثال‌ها

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

(δ(q₀,a,z) = (q₀, az

(δ(q₀,a,a) = (q₀, aa

(δ(q₀,b,a) = (q₁, ε

(δ(q₁,b,a) = (q₁, ε

زبان‌های مستقل از متن غیر مبهم یک زیرمجموعه مخصوص از زبان‌های مستقل از متن هستند: زبان‌های مستقل از متن ذاتاً مبهم وجود دارد. یک مثال برای زبان مستقل از متن ذاتاً مبهم اجتماع {aⁿb^mc^mdⁿ|n,m>0} با {aⁿbⁿc^md^m | n,m >0} است. این مجموعه مستقل از متن است زیرا اجتماع دو زبان مستقل از متن، مستقل از متن است. اما هیچ راهی برای تجزیه کردن غیر مبهم رشته‌ها در زیر مجموعه {aⁿbⁿcⁿdⁿ | n > 0} که اشتراک این دو زبان است، وجود ندارد.

زبان‌هایی که مستقل از متن نیستند

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

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

خصوصیات بستار

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

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

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

زبان‌های مستقل از متن تحت اشتراک بسته نیستند. این می‌تواند در زبان {A = {aⁿbⁿc^m | n,m ≥ ۰ و {B = {a^mbⁿcⁿ | n,m ≥ ۰ که هر دو مستقل از متن هستند دیده شود.

اشتراک به صورت {A∩B = {aⁿbⁿcⁿ | n ≥ ۰ است که می‌تواند توسط لم تزریق برای زبان‌های مستقل از متن نشان داده شود که مستقل از متن نیست.

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

A∩B = (A^cυB^c)^c

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

L^c = Σ^* \ L

منابع

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

1. Sipser, Michael. Introduction to the Theory of Computation (به انگلیسی). Boston, MA, USA: CENGAGE Learning. pp. 117–124.
2. Sipser, Michael. Introduction to the Theory of Computation (به انگلیسی). Boston, MA, USA: CENGAGE Learning. p. 121.