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.


Explanations: 1

Thank you to the contributors under CC BY-SA 4.0!




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