Context Sensitive and Unrestricted Grammars

 

🌿 Context-Sensitive Grammar (CSG)

Definition

A context-sensitive grammar (CSG) is a formal grammar
$G=(V,\mathrm{\Sigma },R,S)$ where every production (rule) in $R$ is of the form:

$$\alpha A \beta \rightarrow \alpha \gamma \beta$$

such that $A \in V - \Sigma$, $\alpha, \beta \in (V \cup \Sigma)^*$, and
$\gamma \in (V\cup \mathrm{\Sigma }{)}^{+.}$

That means:

• The nonterminal A can be replaced by γ,

• But only in the context of α (on the left) and β (on the right).

• Also, the length of the right-hand side is at least the length of the left-hand side:

  $$|\alpha A \beta| \leq |\alpha \gamma \beta|$$
  

  — so no production makes the string shorter.

This non-decreasing length property makes them context-sensitive.

---

Intuitive Meaning

• The replacement (rewriting) of a symbol depends on its context in the string.

• Hence the name “context-sensitive.”

• The grammar cannot “shrink” a string (unlike context-free grammars).

---

Language Type

The language generated by a context-sensitive grammar is called a Context-Sensitive Language (CSL).

---

Equivalent Machine Model

Context-sensitive languages are exactly those accepted by a
Linear Bounded Automaton (LBA) —
that is, a nondeterministic Turing machine whose tape head never goes beyond the space occupied by the input.

This was shown by Kuroda (1964).

---

Example

Language:

$$L = \{ a^n b^n c^n \mid n \ge 1 \}$$

This language is not context-free, but context-sensitive.

Grammar $G$:

$$S \Rightarrow aSBC \mid aBC$$
$$CB \Rightarrow BC$$
$$aB \Rightarrow ab$$
$$bC \Rightarrow bc$$

How it works:

• Start by generating strings like $a^n B^n C^n$
  

• Then use $CB \Rightarrow BC$ to reorder the middle symbols.

• Finally, use $aB \Rightarrow ab$ and $bC \Rightarrow bc$ to turn B’s and C’s into the corresponding terminals.

So this grammar enforces equal numbers of a’s, b’s, and c’s — a classic context-sensitive pattern.

---

Key Properties of CSG

1. Every context-free grammar is also a CSG (so, CSG ⊇ CFG).

2. No CSG can derive the empty string (unless the start symbol is specially handled).

3. Every context-sensitive language is recursive — that is, decidable by some Turing machine.

4. Recognized by Linear Bounded Automata (LBA).

---

🌾 Unrestricted Grammar (Type-0 Grammar)

Definition

An unrestricted grammar (also called a Type-0 grammar) is the most general kind of grammar.

A grammar
$G = (V, \Sigma, R, S)$
is unrestricted if the productions are of the form:

$$\alpha \rightarrow \beta$$

where:

• $\alpha, \beta \in (V \cup \Sigma)^*$
  

• and α contains at least one nonterminal.

Unlike CSG:

• There is no restriction on context or on string length —
  so $|\beta|$ can be less than, equal to, or greater than $|\alpha|$
  

---

Language Type

The languages generated by unrestricted grammars are called recursively enumerable languages (RE languages).

---

Equivalent Machine Model

An unrestricted grammar is equivalent to a Turing machine.

That is:

• For every unrestricted grammar, there exists a Turing machine that accepts the same language.

• And for every Turing machine, there is an unrestricted grammar generating the same language.

So Type-0 grammars = Turing machine languages.

---

Example

Language:

$$L = \{ a^n b^n c^n \mid n \ge 1 \}$$

We can also define it by an unrestricted grammar, for example:

$$S \rightarrow aSBC \mid abc$$
$$CB \rightarrow BC$$
$$aB \rightarrow ab$$
$$bC \rightarrow bc$$

Notice — this looks similar to our context-sensitive example, but if we also allowed rules that shorten strings or rearrange them arbitrarily, it becomes unrestricted.

---

Properties of Unrestricted Grammars

1. Most powerful of all grammars.

2. Generate recursively enumerable languages (those accepted by a Turing machine that may not halt).

3. No restriction on rule length or form.

4. Used to describe any computation that can be done mechanically (by Turing’s thesis).

---

🧭 3. Relationship — Chomsky Hierarchy

Type	Grammar Name	Machine Equivalent	Language Class	Restrictions
0	Unrestricted Grammar	Turing Machine	Recursively Enumerable	None
1	Context-Sensitive Grammar	Linear Bounded Automaton	Context-Sensitive	Non-contracting rules
2	Context-Free Grammar	Pushdown Automaton	Context-Free	A → α
3	Regular Grammar	Finite Automaton	Regular	A → aB or A → a

And:

$$\text{Regular} \subset \text{Context-Free} \subset \text{Context-Sensitive} \subset \text{Recursively Enumerable}$$