Context Sensitive Language (CSL)

A Context Sensitive Language is one that may be described by a Context Sensitive Grammar, according to formal language theory and equivalently by a noncontracting grammar. One of the four categories of grammar in the Chomsky hierarchy is context-sensitive.

In this article, we will look more into the Context Sensitive Language according to the GATE Syllabus for (Computer Science Engineering) CSE. We will read ahead to find out more about it.

Table of Contents

• What is Context Sensitive Language (CSL)?
• Example of Context Sensitive Language
• Properties of Context Sensitive Language
• Is Natural Language a CSL?

What is Context Sensitive Language (CSL)?

G refers to Context Sensitive Grammar, in which the language of G can be defined to be a set of all the strings in Σ*, which can be derived from the start variable S in the variable V:

L(G) = { where, w belongs to Σ* : S => w}

• If there is a Context Sensitive Grammar G such that L(G) = L, then a language L is said to be a Context Sensitive Language.

Context Sensitive Language is, therefore, the collection of all strings that can be produced using Context Sensitive Grammar.

Example of Context Sensitive Language

Here is an example of Context Sensitive Language:

{ aNbNcN , N >= 1 }

Context Sensitive Grammar is required here.

Context Free Grammar does not allow us to construct CSL because it only records two properties; however, we have three in this case (a, b, and c). Similar to Context Free Grammar, Regular Grammar is ineffective since it tracks only one property and is less robust.

Here are the rules of CSG for Context Sensitive Language:

S -> pqr

S -> P

P -> pPQr

P -> pqr

rQ -> Qr

qQ -> qq

For instance, if N=3, the resultant string would be aaabbbccc, while the derivation using CSG would be:

S->P

-> pPQr

-> ppPQrQr (using Rule: P->pPQr)

-> pppbcQrQr (using Rule: P->pqr)

-> pppqQrrQr (using Rule: rQ->Qr)

-> pppqBcBrr (using Rule: rQ->Qr)

-> pppqqcBrr (using Rule: rQ->rr)

-> pppqqQrrr (using Rule: rQ->Qr)

-> pppqqqrrr (using Rule: qQ->rr)

With this, we have the resultant string aaabbbccc.

Properties of Context Sensitive Language

The positions of Context Sensitive Language and the other languages in the Theory of Computation are shown in the following table:

The table above, i.e. the Chomsky Hierarchy, was created for the first time in 1956. We can state from the table that Context Sensitive Language is more potent than:

• Regular Language
• Context-Free Language

Context Sensitive Language is additionally less robust than recursively enumerable language.

Because context free language and regular language are a subset of Context Sensitive Language, every context free and regular language can be thought of as a Context Sensitive Language. A subset of the recursively enumerable language is Context Sensitive Language.

Is Natural Language a CSL?

Humans use Natural Language to communicate, including English, Sanskrit, and other languages like Japanese. Natural Language is weaker than Context Sensitive Language. Context-free language is also less robust than Natural Language.

Natural Language lies between context-sensitive and context-free languages. Natural Languages are produced using “Linear Context Free Rewriting Systems,” a less effective variation of Context Sensitive Grammar.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.

Also Explore,

• Context Free Grammar
• Classification of Context Free Grammars
• Context Free Language Closure Properties
• Context Sensitive Grammar (CSG)
• Undecidable Problem about Turing Machine