Context-Sensitive Grammar (CSG) & Language (CSL) | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Clear all your Computer Science Engineering (CSE) doubts with EduRev Join for Free

Join for Free

Context-sensitive Grammar (CSG) and Language (CSL)

Context-Sensitive Grammar –

α → β
where α, β ∈ (V u T)⁺ and |α| ≤ |β|
Where α and β are strings of non-terminals and terminals.
Context-sensitive grammars are more powerful than context-free grammars because there are some languages that can be described by CSG but not by context-free grammars and CSL are less powerful than Unrestricted grammar. That’s why context-sensitive grammars are positioned between context-free and unrestricted grammars in the Chomsky hierarchy.

Context-sensitive grammar has 4-tuples. G = {N, Σ, P, S}, Where

N = Set of non-terminal symbols

Σ = Set of terminal symbols

S = Start symbol of the production

P = Finite set of productions

All rules in P are of the form α₁ A α₂ –> α₁ β α₂
Context-sensitive Language: The language that can be defined by context-sensitive grammar is called CSL. Properties of CSL are :

• Union, intersection and concatenation of two context-sensitive languages is context-sensitive.
• Complement of a context-sensitive language is context-sensitive.

Example – Consider the following CSG.

S → abc/aAbc

Ab → bA
Ac → Bbcc
bB → Bb
aB → aa/aaA
What is the language generated by this grammar?
Solution:
S → aAbc
→ abAc
→ abBbcc
→ aBbbcc
→ aaAbbcc
→ aabAbcc
→ aabbAcc
→ aabbBbccc
→ aabBbbccc
→ aaBbbbccc
→ aaabbbccc
The language generated by this grammar is {aⁿbⁿcⁿ | n≥1}.