گرامر حساس به متن

گرامر حساس به متن گرامری است که سمت چ‍‍پ و سمت راست هر قوانین آن ممکن است توسط نمادهای پایانی و غیر پایانی احاطه شده باشد. گرامرهای حساس به متن نسبت به گرامرهای مستقل از متن عمومی تر هستند چرا که بعضی از زبان‌ها شاید نتوان با گرامر مستقل از متن نشان داده شوند اما با گرامر حساس به متن بیان می‌توان بیان کرد. گرامر حساس به متن نسبت به گرامر نامحدود کمتر حالت عمومی دارد؛ یعنی CSGها موقعیت میانی بین گرامرهای مستقل از متن و نامحدود در سلسه مراتب چامسکی را پر می‌کنند.
زبان رسمی که توسط گرامرحساس به متن نشان داده می‌شود - به‌طور معادل (هم ارز) , توسط آتاماتای خطی کران‌دار-زبان حساس به متن نامیده می‌شود. بعضی از کتاب‌ها CSGها را به صورت گرامر غیر متعامد نیز تعریف می‌کنند. این مدل تعریف کردن هیچ تفاوتی در نظریه زبان‌ها به وجود نمی‌آورد (یعنی هر دو تعریف هم ارز بسیار ضعیفی دارند) اما این تفاوت را در نظریه اینکه کدام گرامرها به‌طور ساختاری حساس به متن در نظر گرفته شده‌است وجود دارد. در ادامه متن آنالیز چامسکی در سال ۱۹۶۳ گفته می‌شود.
والتر ساویچ اصطلاح حساس به متن را گمراه کننده خوانند و اصطلاح غیر پاک شونده را پیشنهاد کرد که بهتر تفاوت بین CSG و گرامر نامحدود را مشخص کند.
اگر چه اینکه ویژگی‌ها خاصی از زبان (مانند وابستگی متقابل سریال) مستقل از متن نیستند؛ اما یک سؤال پژوهشی وجود دارد که گرامر مستقل از متن چه مقدار قدرت بیان لازم را دارد تا حساسیت متن موجود در زبان طبیعی را بیابد. تحقیقات بعدی در این منطقه بیشتر روی محاسبات زبان ملایم حساس به متن تمرکز دارد.

تعریف رسمی 
گرامر G به این صورت تعریف می‌شود که G = (N, Σ, P, S)که در آن N مجموعه متغیرهای گرامر و Ʃ مجموعه ترمیتال‌ها و P مجموعه قوانین و Sنماد آغاز گر گرامر است.
در گرامر حساس به متن تمام قوانین در P به صورت زیر است:
αAβ → αγβ

که

A ∈ N α,β ∈ (N∪Σ)* and γ ∈ (N∪Σ)+.
زبان گرامر G مجموعه ایی از همهٔ رشته‌های با نماد ترمینال‌ها که از نماد شروع مشتق می‌شود است.
L(G) = { w ∈ Σ*: S ⇒* w }.

تنها تفاوت بین این تعریف از چامسکی و گرامر بدون محدودیت آن است که γ می‌تواند در گرامر بدون محدودیت تهی باشد.
اسم حساس به متن αو β که فرم A را نشان می‌دهند بیان می‌شود؛ و تعیین می‌کند آیا A می‌تواند با γ جایگزین شود یا خیر. این قاعده متفاوت ازگرامر مستقل از متن است که در آن متن از غیر ترمینال‌ها مورد توجه قرار گرفته‌است. در واقع هر قاعده تولید از گرامر مستقل از متن به فرم است که v یک نماد تک غیر ترمینال است و w یک رشته از ترمینال‌ها است؛ w می‌تواند خالی باشد.

مثال 
گرامر زیر با نماد s شروع شده و استاندارد زبان غیر مستقل از متن زیر را ساخته است.
{ anbncn: n ≥ ۱ }

قواعد ۱ و ۲ s را به
قواعد ۱و ۲
s
را به
an(Bc)n تبدیل می‌کند

قاعده ۷ برای آن است B را با b جایگزین کند.
یک زنجیره تولید برای aaabbbccc به صورت زیر است:

  S
  →2 aSBc
  →2 aaSBcBc
  →1 aaabcBcBc
  →3 aaabWBcBc
  →4 aaabWXcBc
  →5 aaabBXcBc
  →6 aaabBccBc
  →3 aaabBcWBc
  →4 aaabBcWXc
  →5 aaabBcBXc
  →6 aaabBcBcc
  →3 aaabBWBcc
  →4 aaabBWXcc
  →5 aaabBBXcc
  →6 aaabBBccc
  →7 aaabbBccc
  →7 aaabbbccc

پا نوشته‌ها

جستارهای وابسته 
 وراثت چامسکی

چارچوب‌های دستور زبانی
زبان‌های صوری
ویکی‌سازی رباتیک