# 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.

Explanations: 1
Proofs: 2
Theorems: 3

Github: ### References

#### Bibliography

1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015