Skip to content
Home » Context-Sensitive Languages (CSL)

Context-Sensitive Languages (CSL)

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:

  • as
  • bs
  • cs

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 LanguageContext-Sensitive Language
Type-2Type-1
Generated by CFGGenerated by CSG
Recognized by PDARecognized by LBA
Less powerfulMore powerful
Example: {aⁿbⁿ}Example: {aⁿbⁿcⁿ}
Uses a stackUses 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.