Context Sensitive Language (CSL)
Context Sensitive Language is a Language generated from Context Sensitive Grammar. We have explored the concept along with example and properties of Context Sensitive Language.
Prerequisite: Context Sensitive Grammar
Table of contents:
- Definition of Context Sensitive Language
- Example of Context Sensitive Language
- Properties of Context Sensitive Language
Let us get started with Context Sensitive Language.
Definition of Context Sensitive Language
G is a Context Sensitive Grammer. The language of G is defined to be the set of all strings in Σ* that can be derived for start variable S in V:
L(G) = { w belongs to Σ* : S => w}
- A language L is called Context Sensitive Language if there is a Context Sensitive Grammer G such that L(G) = L.
Therefore, in simple terms, the set of all strings that can be generated from Context Sensitive Grammar is known as Context Sensitive Language.
Example of Context Sensitive Language
Example of Context Sensitive Language is:
{ aNbNcN , N >= 1 }
For this, we need Context Sensitive Grammar.
We cannot generate this language with Context Free Grammar because it keeps track of only two properties while in this case, we have 3 properties that is count of a, b and c. Similarly, Regular Grammar cannot be used as it is weaker than Context Free Grammar and tracks only 1 property.
The rules of Context Sensitive Grammar for this language will be:
S -> abc
S -> A
A -> aABc
A -> abc
cB -> Bc
bB -> bb
For example, if N=3, then the resultant string will be aaabbbccc and the derivation using our Context Sensitive Grammar will be:
S->A
-> aABc
-> aaABcBc (using Rule: A->aABc)
-> aaabcBcBc (using Rule: A->abc)
-> aaabBccBc (using Rule: cB->Bc)
-> aaabBcBcc (using Rule: cB->Bc)
-> aaabbcBcc (using Rule: bB->bb)
-> aaabbBccc (using Rule: cB->Bc)
-> aaabbbccc (using Rule: bB->bb)
With this, we have our resultant string aaabbbccc.
Properties of Context Sensitive Language
This table gives you the idea of the different Languages in Theory of Computation and the position of Context Sensitive Language:
| Type | Language | Automata Machine | Power |
|---|---|---|---|
| Type 0 | Recursively Enumerable | Turing Machine | Strongest |
| Type 1 | Context Sensitive | Linear Bounded Automaton | Stronger |
| Type 2 | Context Free | Pushdown Automaton | Strong |
| Type 3 | Regular | Finite State Automaton | Weak |
The above table is known as Chomsky Hierarchy and was first formed in 1956.
From the table, we know that Context Sensitive Language is stronger than:
- Context Free Language
- Regular Language
Additionally, Context Sensitive Language is weaker than Recursively Enumerable Language.
Therefore, every Context Free Language and Regular Language can be viewed as a Context Sensitive Language as Context Free Language and Regular Language is a subset of Context Sensitive Language.
Context Sensitive Language is a subset of Recursively Enumerable Language.
Are Natural Language a CSL?
Natural Language is a language that humans use to communicate such as English, Japanese, Sanskrit and others.
Context Sensitive Language is stronger than Natural Language. Additionally, Context Free Language is weaker than Natural Language.
So, Natural Language is in between Context Sensitive Language and Context Free Language.
A lesser powerful version of Context Sensitive Grammar known as "Linear Context Free Rewriting Systems" is used to generate Natural Languages.
With this article at OpenGenus, you must have the complete knowledge of Context Sensitive Language.