Definition: Type-3 (Linear) Grammars and Regular Languages
A type-3 (or linear) grammar is a grammar $G=(V,T,R,S)$ in which every rule $P\to Q\in R$ allows the replacement of only one variable and the variable is at one end (left-side or right-side) of a production rule. There are two types of linear grammars:
- left-linear if and only if all grammar rules $P\to Q\in R$ consist of $P\in V$ (the premise $P$ is a variable) and $Q\in V T^+\cup \{\epsilon\}$ (the conclusion $Q$ is either the empty string $\epsilon$ or it is a concatenation starting with a variable, followed by some non-empty string of terminals).
- right-linear if and only if all grammar rules $P\to Q\in R$ consist of $P\in V$ (the premise $P$ is a variable) and $Q\in T^+V\cup \{\epsilon\}$ (the conclusion $Q$ is either the empty string or it is a concatenation of some non-empty string of terminals ending with a variable).
Formal languages generated by type-3 grammars are called regular.
Notes
- The characteristics of type-3 grammars is that they always replace a single variable by the empty word or a concatenation of terminals ending or starting with a single variable.
- The notation $T^+$ denotes the Kleene plus of all terminal symbols.
Mentioned in:
Explanations: 1
Proofs: 2
Theorems: 3
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
