Context-Sensitive Grammars

Learn how context-sensitive grammars extend context-free grammars by allowing a non-terminal to be replaced only when it appears in a specific surrounding context, and why this extra power matters.

Intuition — What Does 'Context-Sensitive' Mean?

In a context-free grammar (CFG), a non-terminal A can be replaced anywhere, regardless of what appears around it. The rule A → α fires wherever A appears.

In a context-sensitive grammar (CSG), a non-terminal A can only be replaced if it is surrounded by specific symbols — that is, the replacement depends on the context (the neighbours) of A.

Analogy: Think of the word "lead" in English.

In the context "lead the team" → it means to guide
In the context "a lead pipe" → it means a metal

The meaning (and therefore the correct replacement) depends on the surrounding context. That is exactly the idea in context-sensitive grammars.

Context-free rule:

Example

A → γ (A can be replaced by γ anywhere)

Context-sensitive rule:

Example

αAβ → αγβ (A can be replaced by γ only when

it is preceded by α and followed by β)

The context α and β must appear on both sides of the rule — they are preserved unchanged.

Formal Definition

A grammar G = (V, T, P, S) is context-sensitive (Type 1 in the Chomsky Hierarchy) if every production rule in P has the form:

Example

αAβ → αγβ

where:

A ∈ V (A is a non-terminal)
α, β ∈ (V ∪ T)* (α and β are any strings of grammar symbols, possibly empty)
γ ∈ (V ∪ T)⁺ (γ is a non-empty string — the right-hand side is never shorter)
The context α and β appear identically on both sides

Critical constraint — non-shortening:

Example

|αγβ| ≥ |αAβ|

⟹ |γ| ≥ 1

The right-hand side can never be shorter than the left-hand side. This prevents the grammar from "shrinking" a string (except for the special case S → ε, which is allowed only if S never appears on a right-hand side).

One allowed exception:

Example

S → ε is allowed if S does not appear in any RHS.

This exception lets the language include the empty string.

Classic Example — {aⁿbⁿcⁿ | n ≥ 1}

The language L = {aⁿbⁿcⁿ | n ≥ 1} = {abc, aabbcc, aaabbbccc, ...} cannot be generated by any context-free grammar (this is proven by the Pumping Lemma for CFGs). However, a context-sensitive grammar can generate it.

Grammar:

Example

S → aSBC | aBC

CB → BC

aB → ab

bB → bb

bC → bc

cC → cc

Let us trace the derivation for n = 2 → "aabbcc":

Example

Step Sentential Form Rule Applied

──── ───────────────── ──────────────────

0 S

1 aSBC S → aSBC

2 aaBCBC S → aBC (inner S replaced)

3 aaBBCC CB → BC (rearrange to get all B's before C's)

4 aabBCC aB → ab (leftmost aB → ab)

5 aabbCC bB → bb

6 aabbcC bC → bc

7 aabbcc cC → cc

Context-sensitive rules in action:

aB → ab: the rule fires only when B is immediately preceded by a. The context is "a _ " and B becomes b.
bB → bb: the rule fires only when B is immediately preceded by b.
CB → BC: this swaps C and B — the context is the pair "CB" acting as one unit.

These rules would be impossible to write in a context-free grammar, where A can only be replaced regardless of neighbours.

More Examples of Context-Sensitive Rules

Example 1 — Doubling a string

Language: L = {ww | w ∈ {a, b}*} — strings that are their own repetition.

Example

e.g., abab, abaaba, bab bab

This is context-sensitive. The grammar needs to "copy" the first half w over to produce the second half w — requiring context-awareness at each position.

Example 2 — Simple context rule

Rule: aBc → abc

This means: "B can be replaced by b, but only when it appears between 'a' on the left and 'c' on the right."

Example

Valid: ...aBc... → ...abc... ✓

Invalid: ...dBc... → (rule does not apply here)

Invalid: ...aBd... → (rule does not apply here)

Example 3 — Multiple context steps

Grammar:

Example

S → ab | aSb

aAb → aab

This is NOT a proper CSG because the rule S → ab and S → aSb have a lone non-terminal on the left (which is fine for CFG). The rule aAb → aab IS context-sensitive since A is replaced only between a and b.

Contrast with CFG:

Feature	CFG Rule	CSG Rule
Form	A → γ	αAβ → αγβ
Context required?	No	Yes (α and β)
RHS shorter than LHS?	Allowed (A → ε)	Never (except S → ε)
Power	Less powerful	More powerful
Recogniser	Pushdown Automaton	Linear-Bounded Automaton

Properties of Context-Sensitive Languages

1. Strictly contains all CFLs: Every context-free language is also context-sensitive, but not vice versa.

Example

Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable

2. Closed under:

Union: if L₁ and L₂ are CSLs, then L₁ ∪ L₂ is also a CSL
Concatenation: if L₁ and L₂ are CSLs, then L₁L₂ is also a CSL
Kleene star: if L is a CSL, then L* is also a CSL
Complement: if L is a CSL, then its complement is also a CSL

3. The membership problem is decidable: Given a string w and a CSG G, we can decide (in finite time) whether w ∈ L(G). This is unlike unrestricted grammars (Type 0) where the membership problem is undecidable.

4. Recognised by a Linear-Bounded Automaton (LBA): An LBA is a Turing Machine that is restricted to using only as much tape space as the length of the input string. This space restriction corresponds directly to the non-shortening constraint of CSGs.

Why CSGs Rarely Appear in Compiler Design

Real programming languages (C, Java, Python) are designed to be context-free — this makes parsing much more efficient (O(n³) with CYK, O(n) with LALR). Context-sensitive features like "a variable must be declared before use" are handled separately by the semantic analysis phase, not by the grammar itself.

CSGs are important theoretically — they show where CFGs run out of expressive power — and are studied to understand the boundary between what parsing can and cannot handle.

Intuition — What Does 'Context-Sensitive' Mean?

In a context-free grammar (CFG), a non-terminal A can be replaced anywhere, regardless of what appears around it. The rule A → α fires wherever A appears.

Analogy: Think of the word "lead" in English.

In the context "lead the team" → it means to guide
In the context "a lead pipe" → it means a metal

The meaning (and therefore the correct replacement) depends on the surrounding context. That is exactly the idea in context-sensitive grammars.

Context-free rule:

Example

A → γ (A can be replaced by γ anywhere)

Context-sensitive rule:

Example

αAβ → αγβ (A can be replaced by γ only when

it is preceded by α and followed by β)

The context α and β must appear on both sides of the rule — they are preserved unchanged.

Formal Definition

A grammar G = (V, T, P, S) is context-sensitive (Type 1 in the Chomsky Hierarchy) if every production rule in P has the form:

Example

αAβ → αγβ

where:

A ∈ V (A is a non-terminal)
α, β ∈ (V ∪ T)* (α and β are any strings of grammar symbols, possibly empty)
γ ∈ (V ∪ T)⁺ (γ is a non-empty string — the right-hand side is never shorter)
The context α and β appear identically on both sides

Critical constraint — non-shortening:

Example

|αγβ| ≥ |αAβ|

⟹ |γ| ≥ 1

One allowed exception:

Example

S → ε is allowed if S does not appear in any RHS.

This exception lets the language include the empty string.

Classic Example — {aⁿbⁿcⁿ | n ≥ 1}

Grammar:

Example

S → aSBC | aBC

CB → BC

aB → ab

bB → bb

bC → bc

cC → cc

Let us trace the derivation for n = 2 → "aabbcc":

Example

Step Sentential Form Rule Applied

──── ───────────────── ──────────────────

0 S

1 aSBC S → aSBC

2 aaBCBC S → aBC (inner S replaced)

3 aaBBCC CB → BC (rearrange to get all B's before C's)

4 aabBCC aB → ab (leftmost aB → ab)

5 aabbCC bB → bb

6 aabbcC bC → bc

7 aabbcc cC → cc

Context-sensitive rules in action:

aB → ab: the rule fires only when B is immediately preceded by a. The context is "a _ " and B becomes b.
bB → bb: the rule fires only when B is immediately preceded by b.
CB → BC: this swaps C and B — the context is the pair "CB" acting as one unit.

These rules would be impossible to write in a context-free grammar, where A can only be replaced regardless of neighbours.

More Examples of Context-Sensitive Rules

Example 1 — Doubling a string

Language: L = {ww | w ∈ {a, b}*} — strings that are their own repetition.

Example

e.g., abab, abaaba, bab bab

This is context-sensitive. The grammar needs to "copy" the first half w over to produce the second half w — requiring context-awareness at each position.

Example 2 — Simple context rule

Rule: aBc → abc

This means: "B can be replaced by b, but only when it appears between 'a' on the left and 'c' on the right."

Example

Valid: ...aBc... → ...abc... ✓

Invalid: ...dBc... → (rule does not apply here)

Invalid: ...aBd... → (rule does not apply here)

Example 3 — Multiple context steps

Grammar:

Example

S → ab | aSb

aAb → aab

Contrast with CFG:

Feature	CFG Rule	CSG Rule
Form	A → γ	αAβ → αγβ
Context required?	No	Yes (α and β)
RHS shorter than LHS?	Allowed (A → ε)	Never (except S → ε)
Power	Less powerful	More powerful
Recogniser	Pushdown Automaton	Linear-Bounded Automaton

Properties of Context-Sensitive Languages

1. Strictly contains all CFLs: Every context-free language is also context-sensitive, but not vice versa.

Example

Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable

2. Closed under:

Union: if L₁ and L₂ are CSLs, then L₁ ∪ L₂ is also a CSL
Concatenation: if L₁ and L₂ are CSLs, then L₁L₂ is also a CSL
Kleene star: if L is a CSL, then L* is also a CSL
Complement: if L is a CSL, then its complement is also a CSL

Why CSGs Rarely Appear in Compiler Design

CSGs are important theoretically — they show where CFGs run out of expressive power — and are studied to understand the boundary between what parsing can and cannot handle.