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

گرامر حساس به متن گرامری است که سمت چ‍‍پ و سمت راست هر قوانین آن ممکن است توسط نمادهای پایانی و غیر پایانی احاطه شده باشد. گرامرهای حساس به متن نسبت به گرامرهای مستقل از متن عمومی تر هستند چرا که بعضی از زبان ها شاید نتوان با گرامر مستقل از متن نشان داده شوند اما با گرامر حساس به متن بیان می توان بیان کرد. گرامر حساس به متن نسبت به گرامر نامحدود کمتر حالت عمومی دارد؛ یعنی CSGها موقعیت میانی بین گرامرهای مستقل از متن و نامحدود در سلسه مراتب چامسکی را پر می کنند.زبان رسمی که توسط گرامرحساس به متن نشان داده می شود - به طور معادل (هم ارز) , توسط آتاماتای خطی کران دار-زبان حساس به متن نامیده می شود. بعضی از کتاب ها CSGها را به صورت گرامر غیر متعامد نیز تعریف می کنند. این مدل تعریف کردن هیچ تفاوتی در نظریه زبان ها به وجود نمی آورد (یعنی هر دو تعریف هم ارز بسیار ضعیفی دارند) اما این تفاوت را در نظریه اینکه کدام گرامرها به طور ساختاری حساس به متن در نظر گرفته شده است وجود دارد. در ادامه متن آنالیز چامسکی در سال ۱۹۶۳ گفته می شود.والتر ساویچ اصطلاح حساس به متن را گمراه کننده خوانند و اصطلاح غیر پاک شونده را پیشنهاد کرد که بهتر تفاوت بین CSG و گرامر نامحدود را مشخص کند.اگر چه اینکه ویژگی ها خاصی از زبان (مانند وابستگی متقابل سریال) مستقل از متن نیستند؛ اما یک سؤال پژوهشی وجود دارد که گرامر مستقل از متن چه مقدار قدرت بیان لازم را دارد تا حساسیت متن موجود در زبان طبیعی را بیابد. تحقیقات بعدی در این منطقه بیشتر روی محاسبات زبان ملایم حساس به متن تمرکز دارد.
وراثت چامسکی
گرامر G به این صورت تعریف می شود که G = (N, Σ, P, S)که در آن N مجموعه متغیرهای گرامر و Ʃ مجموعه ترمیتال ها و P مجموعه قوانین و Sنماد آغاز گر گرامر است.در گرامر حساس به متن تمام قوانین در P به صورت زیر است:αAβ → αγβ
که
A ∈ N α,β ∈ (N∪Σ)* and γ ∈ (N∪Σ)+.زبان گرامر G مجموعه ایی از همهٔ رشته های با نماد ترمینال ها که از نماد شروع مشتق می شود است.L(G) = { w ∈ Σ*: S ⇒* w }.