A Context-Sensitive Language (CSL) is an important class of formal languages in the Chomsky hierarchy. It is more powerful than a Context-Free Language (CFL), but less powerful than a Recursively Enumerable Language.
1. Definition
A Context-Sensitive Language is a language generated by a Context-Sensitive Grammar (CSG) and recognized by a Linear Bounded Automaton (LBA).
Therefore:\[ \boxed{\text{CSG} \leftrightarrow \text{CSL} \leftrightarrow \text{LBA}} \]
CSL is called Type-1 Language in the Chomsky hierarchy.
2. Position in Chomsky Hierarchy
The Chomsky hierarchy is:
Type 0 → Recursively Enumerable
↓
Type 1 → Context-Sensitive
↓
Type 2 → Context-Free
↓
Type 3 → Regular
Or:\[ \boxed{Regular \subset CFL \subset CSL \subset RE} \]
Memory Trick
0 → TM
1 → LBA
2 → PDA
3 → FA
3. Why is it Called “Context-Sensitive”?
In a Context-Free Grammar, a variable can generally be replaced without considering its surrounding symbols.
In a Context-Sensitive Grammar, the replacement can depend on the context in which the variable occurs.
For example, a general production may be written as:\[ \alpha A\beta \rightarrow \alpha\gamma\beta \]
Here, the non-terminal A is replaced while its surrounding context α and β is preserved.
This is the basic idea behind the name context-sensitive.
4. Production Rules of Context-Sensitive Grammar
A Context-Sensitive Grammar generally follows the non-contracting rule:\[ |\text{RHS}| \geq |\text{LHS}| \]
That means the length of the string produced should not be smaller than the original string.
For example:
AB → ABC
is allowed because:
LHS length = 2
RHS length = 3
But:
ABC → AB
is generally not allowed because the length decreases.
Important exception
The special production:\[ S\rightarrow\epsilon \]
may be permitted under specific conditions when the language contains the empty string.
5. Example of Context-Sensitive Language
A standard example is:\[ L=\{a^n b^n c^n\mid n\geq1\} \]
It contains strings such as:
abc
aabbcc
aaabbbccc
aaaabbbbcccc
Notice that the number of:
asbscs
must be equal.
For example:
aaabbbccc
↑ ↑ ↑
3 3 3
But:
aaabbccc
3 2 3
is not in the language.
6. Why is this Language Important?
The language\[ \{a^n b^n c^n\} \]
cannot be recognized by an ordinary PDA because a PDA has only one stack and cannot generally maintain the required three-way equality.
However, it can be handled by a Linear Bounded Automaton (LBA).
Therefore, it is a standard example used to demonstrate the greater power of CSL over CFL.
7. Linear Bounded Automaton (LBA)
A Linear Bounded Automaton is a restricted form of Turing Machine used to recognize Context-Sensitive Languages.
The important restriction is:
The amount of tape available to the LBA is bounded by a linear function of the input length.
If the input length is n, the available tape is approximately proportional to n.
Example
For input:
aaabbbccc
the LBA works within a bounded region:
| a | a | a | b | b | b | c | c | c |
←────── bounded working area ──────→
It cannot use unlimited tape like an unrestricted Turing Machine.
8. CSL vs CFL
This comparison is important.
| Context-Free Language | Context-Sensitive Language |
|---|---|
| Type-2 | Type-1 |
| Generated by CFG | Generated by CSG |
| Recognized by PDA | Recognized by LBA |
| Less powerful | More powerful |
Example: {aⁿbⁿ} | Example: {aⁿbⁿcⁿ} |
| Uses a stack | Uses bounded tape |
Remember:
\[ \boxed{CFL \subset CSL} \]
Every CFL is a CSL, but every CSL is not a CFL.
9. CSL vs Recursive Languages
A useful point in computability theory:
Every context-sensitive language is recursive.
Why?
Because an LBA has a bounded amount of tape for a fixed input, so there are only finitely many configurations that can be reached. A suitable simulation can therefore determine whether the machine accepts.
Thus:\[ \boxed{CSL \subseteq Recursive \subseteq RE} \]
So the broader hierarchy can be viewed as:
Regular
↓
Context-Free
↓
Context-Sensitive
↓
Recursive
↓
Recursively Enumerable
10. Properties of Context-Sensitive Languages
Important properties include:
1. Closed under Union
If L₁ and L₂ are CSLs:\[ L_1\cup L_2 \]
is also a CSL.
2. Closed under Intersection
\[ L_1\cap L_2 \]
is also a CSL.
3. Closed under Complement
The complement of a CSL is also a CSL.
4. Closed under Concatenation
If L₁ and L₂ are CSLs:\[ L_1L_2 \]
is also a CSL.
5. Closed under Kleene Star
\[ L^* \]
is also a CSL.
For an exam, the most important closure properties to remember are:
Union, Intersection, Complement, Concatenation, and Kleene Star.
11. Diagram of CSL
Context-Sensitive Grammar
↓
↓
Context-Sensitive Language
↓
↓
Linear Bounded Automaton
Therefore:\[ \boxed{CSG = CSL = LBA} \]
Here, the equality means equivalent in language-generating/recognizing power, not that the three things are literally the same object.
12. Important Example
Consider:\[ L=\{a^n b^n c^n\mid n\geq1\} \]
For n = 1:
abc
For n = 2:
aabbcc
For n = 3:
aaabbbccc
For n = 4:
aaaabbbbcccc
The number of all three symbols must be equal.
This demonstrates the need for more computational power than a normal PDA provides.
5–10 Marks Exam Answer
Context-Sensitive Languages
A Context-Sensitive Language (CSL) is a formal language generated by a Context-Sensitive Grammar (CSG) and recognized by a Linear Bounded Automaton (LBA). It is classified as a Type-1 language in the Chomsky hierarchy.
The productions of a context-sensitive grammar generally satisfy the non-contracting condition:\[ |\text{RHS}| \geq |\text{LHS}| \]
A general production can be represented as:\[ \alpha A\beta\rightarrow\alpha\gamma\beta \]
where the replacement of a symbol may depend on its surrounding context.
A standard example of a context-sensitive language is:\[ L=\{a^n b^n c^n\mid n\geq1\} \]
which contains abc, aabbcc, aaabbbccc, etc. The number of a, b, and c symbols must be equal.
Context-Sensitive Languages are more powerful than Context-Free Languages. A PDA recognizes CFLs, whereas an LBA recognizes CSLs.
The important relationship is:\[ \boxed{Regular\subset CFL\subset CSL\subset Recursive\subset RE} \]
Thus, Context-Sensitive Languages occupy Type-1 in the Chomsky hierarchy.
🧠 Fast Memory Trick
CSL = Type 1 = CSG + LBA
And remember:
CFL → PDA →
{aⁿbⁿ}
CSL → LBA →{aⁿbⁿcⁿ}
One-line exam conclusion:
A Context-Sensitive Language is a Type-1 language generated by a Context-Sensitive Grammar and recognized by a Linear Bounded Automaton.
