Context-Sensitive Grammar (CSG) & Language (CSL) Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : Context-Sensitive Grammar (CSG) & Language (CSL) Notes | EduRev

The document Context-Sensitive Grammar (CSG) & Language (CSL) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

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

Context-Sensitive Grammar –
A Context-sensitive grammar is an Unrestricted grammar in which all the productions are of form –

α → β
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 (CSG) & Language (CSL) Notes | EduRev

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 α1 A α2 –> α1 β α2
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 {anbncn | n≥1}.

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Objective type Questions

,

ppt

,

mock tests for examination

,

video lectures

,

Viva Questions

,

practice quizzes

,

Context-Sensitive Grammar (CSG) & Language (CSL) Notes | EduRev

,

Previous Year Questions with Solutions

,

Context-Sensitive Grammar (CSG) & Language (CSL) Notes | EduRev

,

Important questions

,

Free

,

Context-Sensitive Grammar (CSG) & Language (CSL) Notes | EduRev

,

Extra Questions

,

Summary

,

MCQs

,

Exam

,

shortcuts and tricks

,

past year papers

,

Semester Notes

,

study material

,

Sample Paper

,

pdf

;