Editing Chomsky hierarchy (section)

===Regular (Type-3) grammars===
{{main|Regular grammar}}

Type-3 grammars generate the [[regular language]]s. Such a grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed by a single nonterminal, in which case the grammar is ''right regular''. Alternatively, all the rules can have their right-hand sides consist of a single terminal, possibly ''preceded'' by a single nonterminal (''left regular''). These generate the same languages. However, if left-regular rules and right-regular rules are combined, the language need no longer be regular. The rule <math>S \rightarrow \varepsilon</math> is also allowed here if <math>S</math> does not appear on the right side of any rule. These languages are exactly all languages that can be decided by a [[finite-state automaton]]. Additionally, this family of formal languages can be obtained by [[regular expression]]s. Regular languages are commonly used to define search patterns and the lexical structure of programming languages.

For example, the regular language <math>L = \{a^n \mid n > 0\}</math> is generated by the Type-3 grammar <math>G = (\{S\}, \{a, b\}, P, S)</math> with the productions <math>P</math> being the following.

:{{math|''S'' → ''aS''}}
:{{math|''S'' → ''a''}}