Grammars and context-sensitivity

Grammars $G=(V,\Sigma,S,P)$ are defined as context-free grammars before with the only difference that there may be several symbols on the left-hand side of a production, i.e. $P\subseteq (V\cup T)^+\times(V\cup T)^*$. Here $(V\cup T)^+$ means that at least one symbol has to present. The relation derives $\Rightarrow _G$ (and $\Rightarrow _G^*$) is defined as before

$$\Rightarrow _G \subseteq (V\cup T)^*\times (V\cup T)^*$$

$$\ \alpha \beta\gamma \Rightarrow _G \alpha\beta'\gamma :\iff \beta \to \beta' \in P$$

and as before the language of $G$ is defined as

$$L(G) = \{ w\in\Sigma^* \mid S \Rightarrow ^*_G w \}$$

We say that a grammar is context-sensitive (or type 1) if the left hand side of a production is at least as long as the right hand side. That is for each $\alpha\to\beta\in P$ we have $\vert\alpha\vert \leq \vert\beta\vert$

Here is an example of a context sensitive grammar: $G=(V,\Sigma,S,P)$ with $L(G) = \{ \{a^nb^nc^n \mid n\in\mathbb{N}\wedge n\geq 1\}$. where

• $V=\{S,B,C\}$

• $\Sigma = \{ \texttt{a},\texttt{b},\textrm{c} \}$

• $$P = \{ S \to aSBC$$

  $$ S \to aBC$$

  $$ aB \to ab$$

  $$ CB \to BC$$

  $$ bB \to bB$$

  $$ bC \to bc$$

  $$cC \to cc \}$$

  
  

We present without proof:

Theorem 8.1   For a language $L\subseteq \Sigma^*$ the following is equivalent:

1. $L$ is accepted by a Turing machine $M$, i.e. $L=L(M)$

2. $L$ is given by a grammar $G$, i.e. $L=L(G)$

Theorem 8.2   For a language $L\subseteq \Sigma^*$ the following is equivalent:

1. $L$ is accepted by a Turing machine $M$, i.e. $L=L(M)$ such that the length of the tape is bounded by a linear function in the length of the input, i.e. $\vert\gamma_l\vert+\vert\gamma_r\vert\leq f(x)$ where $f(x) = ax + b$ with $a,b\in\mathbb{N}$.

2. $L$ is given by a context sensitive grammar $G$, i.e. $L=L(G)$