Definition 4.4.1: A context-free grammar is: • right-linear if all its productions are either right- linear or terminating, • left-linear if all its productions are either left- linear or terminating, • regular if it is either right-linear or left-linear.
Theorem 4.4.1: If L ___* is regular, then there is a right-linear grammar G with L= L(G).
Corollary 4.4.2: no regular language is inherently ambiguous.
| Previous slide | Next slide | Back to first slide | View graphic version |