Definition: Type-2 (cf) Grammars and Context-free Languages
A type-2 (or cf) 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 its production rules can contain any number of variables and/or terminals.
We can state this definition more formally as follows: All grammar rules $P\to Q\in R$ consist of $P\in V$ (the premise $P$ is a variable) and $Q\in (V\cup T)^*$ (the conclusion $Q$ is either the empty string $\epsilon$ or it is a concatenation of variables and/or terminals).
Formal languages generated by type-2 grammars are called context-free.
Notes
- The characteristics of type-2 grammars is that they always replace a single variable by the empty word or a concatenation of any number of terminal and/or variables.
- 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
