Editing Regular grammar (section)

== Strictly regular grammars ==

A '''right-regular grammar''' (also called [[Linear Grammar#Right-Linear Grammars|right-linear grammar]]) is a formal grammar (''N'', Σ, ''P'', ''S'') in which all production rules in ''P'' are of one of the following forms:
# ''A'' → ''a''
# ''A'' → ''aB''
# ''A'' → ε
where ''A'', ''B'', ''S'' ∈ ''N'' are non-terminal symbols, ''a'' ∈ Σ is a terminal symbol, and ε denotes the [[empty string]], i.e. the string of length 0. ''S'' is called the start symbol.

In a  '''left-regular grammar''', (also called [[Linear Grammar#Left-Linear Grammars|left-linear grammar]]), all rules obey the forms
# ''A'' → ''a''
# ''A'' → ''Ba''
# ''A'' → ε

The language described by a given grammar is the set of all strings that contain only terminal symbols and can be derived from the start symbol by repeated application of production rules. Two grammars are called [[weak equivalence (formal languages)|weakly equivalent]] if they describe the same language.

Rules of both kinds must not be mixed; for example, the grammar with rule set { ''S''→''aT'', ''T''→''Sb'', S→ε } is not regular, and describes the language <math>\{ a^i b^i : i \in \mathbb{N} \}</math>, which is not regular, either.

Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.