Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 59 · Context-Sensitive and Other Models

Context-Sensitive Grammars and Languages

Learn context-sensitive grammars: the non-contracting rule, the grammar for a^n b^n c^n, derivations, and a Python tool that classifies grammars by Chomsky type.

Context-free grammars have rules A → α that rewrite a variable regardless of what surrounds it. That is why they cannot enforce a^n b^n c^n: no rule can look at the neighbors of a symbol to check that the three counts agree. A context-sensitive grammar (CSG) lifts this restriction. Its rules may mention a context around the symbol being rewritten, and they may never make the string shorter. The resulting languages, the context-sensitive languages (CSLs), sit between context-free languages and the recursive languages in the Chomsky hierarchy.

Type 1 in the Chomsky hierarchy

Type 3 Regular. Finite automata.
Type 2 Context-free. Pushdown automata.
Type 1 Context-sensitive. Linear bounded automata.
Type 0 Unrestricted. Turing machines.

Each level properly contains the one above it in this list.

1 / 2

The rule shape

A grammar is context-sensitive if every production has the form

α A β → α γ β with γ non-empty

where A is a variable and α, β are (possibly empty) strings of variables and terminals. The variable A is rewritten to γ only when it appears between α and β. That is the "context". The one exception is S → ε, allowed when S never appears on the right of any rule.

An equivalent and easier definition, used in most proofs and exercises, is non-contracting (or monotone): every production α → β has |α| ≤ |β|. The two definitions generate exactly the same languages, since any monotone grammar can be rewritten into the strict form. Either way, the key consequence is:

During a derivation, sentential forms never get shorter.

So to find out whether a word w is derivable, you only need to explore sentential forms of length at most |w|. That finite search makes membership decidable for context-sensitive grammars, which is not the case for unrestricted grammars.

A grammar for a^n b^n c^n

The language { a^n b^n c^n : n ≥ 1 } is the standard example of a language that is context-sensitive but not context-free. This grammar generates it:

TEXT
S  → aSBC | aBC
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc

How does it work? The first two rules build a^n (BC)^n: equal numbers of Bs and Cs, but shuffled. The rule CB → BC is a pure swap (context-sensitive: it needs two neighbors) that sorts all Bs in front of all Cs. Then the rules aB → ab, bB → bb, bC → bc, cC → cc convert variables to terminals left to right, each one only if its left neighbor is already a terminal of the right kind. This ordering prevents a mismatch.

For aabbcc:

S ⇒ aSBC ⇒ aaBCBC ⇒ aaBBCC ⇒ aabBCC ⇒ aabbCC ⇒ aabbcC ⇒ aabbcc

Let us compute the language by brute force. The program explores all sentential forms up to a length bound; because rules never shorten a string, this is complete for words up to that length.

Python Generate the language of a CSG

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output shows exactly abc, aabbcc and aaabbbccc, and the printed chain is a valid derivation of aabbcc. Remember that the search is complete only because the sentential forms cannot shrink.

Context-sensitive but not context-free

Why can't a context-free grammar do the same? Intuitively, a PDA checking a^n b^n c^n would push for the as and pop for the bs, and then have nothing left to compare with the cs. The formal proof uses the pumping lemma for context-free languages: any long word a^p b^p c^p can be split so that pumping affects at most two of the three blocks, making the counts unequal. So a^n b^n c^n is not context-free.

Other classic CSL examples:

Language Why it needs context-sensitivity
{ a^n b^n c^n : n ≥ 1 } three coordinated counts
{ w w : w ∈ {a, b}* } copy language: matches in the same order
{ a^{n²} : n ≥ 1 } perfect squares in unary
{ a^{2^n} : n ≥ 0 } powers of two in unary
{ a^p : p is prime } primality in unary

Classifying grammars automatically

Given a list of productions, we can decide which level of the Chomsky hierarchy the grammar sits in by inspecting each rule's shape. The classifier below uses the monotone definition for type 1; uppercase letters are variables.

Python Which Chomsky type is this grammar?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note that S → ε inside a type-2 grammar is fine, but in a type-1 grammar it is allowed only if S never occurs on a right-hand side; the check above handles that case.

Closure and decision properties

Context-sensitive languages have a pleasant list of closure properties, better than the context-free ones:

  • Closed under union, intersection, concatenation, Kleene star, reversal and, by the Immerman–Szelepcsényi theorem, complement.
  • Membership (is w in L(G)?) is decidable, but PSPACE-complete in general.
  • Emptiness and equivalence are undecidable.
  • Every context-sensitive language is decidable, so CSL ⊂ recursive languages (strictly).

The machine model for CSLs is a Turing machine with a bounded tape, which is the subject of the next lesson.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which property defines a (monotone) context-sensitive grammar?

    Non-contracting rules never shorten a derivation, which is what makes the language class context-sensitive.
  2. 2. What does the rule CB → BC do in the grammar for a^n b^n c^n?

    Before B's and C's turn into terminals, CB → BC swaps them into the right order.
  3. 3. Why is membership decidable for context-sensitive grammars?

    Rules never shorten the string, so only finitely many sentential forms of bounded length can occur.
  4. 4. Which language is context-sensitive but not context-free?

    a^n b^n c^n requires three counts to be equal, which no pushdown automaton can check, but a context-sensitive grammar can.

Summary

  • Context-sensitive rules rewrite a variable in a context, and a grammar is context-sensitive if no rule shortens a string (except possibly S → ε).
  • Type 1 sits between context-free (type 2) and unrestricted (type 0) grammars.
  • a^n b^n c^n has a classic CSG using the swap rule CB → BC.
  • Because forms never shrink, membership is decidable by bounded search.
  • CSLs are closed under complement; their machines are linear bounded automata.

Next: Linear bounded automata