Definition: Type-1 (cs) Grammars and Context-sensitive Languages
A type-1 (or cs) grammar is a grammar $G=(V,T,R,S)$ in which every rule $P\to Q\in R$ has the following properties:
- Either $|P|\le|Q|$ (the length of the conclusion $Q$ has at least the length of the premise $P$, or
- $P\to Q$ is the rule $S\to\epsilon$ (the empty word replacing the starting symbol).
- If the rule $S\to\epsilon$ is included, then the starting symbol $S$ is not allowed to be part of the conclusion of any other rule of the grammar.
We can state this definition more formally as follows:
* Every rule $P\to Q\in R$ has the form $$P\to Q=\begin{cases}S\to\epsilon&\text{or}\\\exists u,v,\alpha\in (V\cup T)^*,\exists A\in V:P=uAv\wedge Q=u\alpha v,|\alpha|\ge 1\end{cases}$$
* $S\not\in Q$ for all $P\to Q\in R.$
Formal languages generated by type-1 grammars are called context-sensitive.
Notes
- The characteristics of type-1 grammars is that they replace a variable $A$ by a word $\alpha$ of the length of at least $|\alpha|\ge 1$.
- However, the variable $A$ can be only replaced if it occurs in the context between the words $u$ (left-side) and $w$ (right-side).
- The notation $(T\cup V)^*$ denotes the Kleene star of any combination of terminal symbols or variables.
Mentioned in:
Explanations: 1
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
- Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015
