گرامر مستقل از متن به گرامری (G=(V،T،S،P گفته می شود که قانون های تولید آن به شکل زیر باشند: A→x که A € V و *(x € (V∪T
زبان L یک زبان مستقل از متن است اگر و تنها اگر گرامر مستقل از متنی مانند G وجود داشته باشد که رابطه ( L=L(G برقرار باشد.همه گرامرهای منظم مستقل از متن هستند؛ بنابراین یک زبان منظم مستقل از متن نیز می باشد اما زبان های نامنظمی مانند{a^n b^n}(^ توان) نیز وجود دارند که مستقل از متن باشند. هبرای این مثال یک گرامر مستقل از متن وجود دارد. بنابراین خانوادهٔ زبان های منظم زیر مجموعه سره ای از خوانده زبان های مستقل از متن می باشند. نام گرامرهای مستقل از متن از این حقیقت آمده که جانشینی متغیرهای سمت چپ قانون تولید، هرزمان که یکی از آن ها در یک فرم جمله ای ظاهر شود امکان پذیر است. بدین معنی که این جانشینی به دیگر نشانه های فرم جمله ای(متن) وابسته نیست. این ویژگی از این ناشی می شود که تنها یک متغیردر سمت چپ قانون های تولید قرار می گیرد.
مثال های از زبان های مستقل از متن مثال یک: گرامر (S}،{a،b}،S،P}) با قانون های تولید s→aSa s→bSb s→Y مستقل از متن است. نمونه ای از یک اشتقاق در این گرامر به صورت s→aSa→aaSaa→aabSbaa→aabbaa می باشد. این اشتقاق و دیگر اشتقاق های مشابه نشان می دهند که زبان {L(G)={wwR:w€{a،b یک زبان مستقل از متن است؛ اما این زبان منظم نیست. مثال دو: s→abB A→aaBb B→bbAa A→Y مستقل از متن است. زبان متناظر با این گرامر {L(G)={ab(bbaa)^nbba(ba)^n:n>=0 می باشد. هر دوی این مثال ها گرامرهایی را نشان می دهند که علاوه بر مستقل از متن بودن، خطی نیز هستند. گرامرهای منظم و خطی مطمئناً مستقل از متن نیز می باشند. اما یک گرامر مستقل از متن لزوماً خطی نیست.
زبان L یک زبان مستقل از متن است اگر و تنها اگر گرامر مستقل از متنی مانند G وجود داشته باشد که رابطه ( L=L(G برقرار باشد.همه گرامرهای منظم مستقل از متن هستند؛ بنابراین یک زبان منظم مستقل از متن نیز می باشد اما زبان های نامنظمی مانند{a^n b^n}(^ توان) نیز وجود دارند که مستقل از متن باشند. هبرای این مثال یک گرامر مستقل از متن وجود دارد. بنابراین خانوادهٔ زبان های منظم زیر مجموعه سره ای از خوانده زبان های مستقل از متن می باشند. نام گرامرهای مستقل از متن از این حقیقت آمده که جانشینی متغیرهای سمت چپ قانون تولید، هرزمان که یکی از آن ها در یک فرم جمله ای ظاهر شود امکان پذیر است. بدین معنی که این جانشینی به دیگر نشانه های فرم جمله ای(متن) وابسته نیست. این ویژگی از این ناشی می شود که تنها یک متغیردر سمت چپ قانون های تولید قرار می گیرد.
مثال های از زبان های مستقل از متن مثال یک: گرامر (S}،{a،b}،S،P}) با قانون های تولید s→aSa s→bSb s→Y مستقل از متن است. نمونه ای از یک اشتقاق در این گرامر به صورت s→aSa→aaSaa→aabSbaa→aabbaa می باشد. این اشتقاق و دیگر اشتقاق های مشابه نشان می دهند که زبان {L(G)={wwR:w€{a،b یک زبان مستقل از متن است؛ اما این زبان منظم نیست. مثال دو: s→abB A→aaBb B→bbAa A→Y مستقل از متن است. زبان متناظر با این گرامر {L(G)={ab(bbaa)^nbba(ba)^n:n>=0 می باشد. هر دوی این مثال ها گرامرهایی را نشان می دهند که علاوه بر مستقل از متن بودن، خطی نیز هستند. گرامرهای منظم و خطی مطمئناً مستقل از متن نیز می باشند. اما یک گرامر مستقل از متن لزوماً خطی نیست.
wiki: گرامر مستقل از متن