where are non-terminal symbols, are terminal words, and the empty word. In BNF, they are:
A regular language (also known as a regular set or a regular event) is the set of strings generated by a regular grammar. Regular grammars are also known as Type-3 grammars in the Chomsky hierarchy.
A regular grammar can be represented by a deterministic or non-deterministic finite automaton. Such automata can serve to either generate or accept sentences in a particular regular language. Note that since the set of regular languages is a subset of context-free languages, any deterministic or non-deterministic finite automaton can be simulated by a pushdown automaton.
There is also a close relationship between regular languages and regular expressions. With every regular expression we can associate a regular language. Conversely, every regular language can be obtained from a regular expression. For example, over the alphabet , the regular language associated with the regular expression is the set
Yet another way of describing a regular language is as follows: take any alphabet . Let be the smallest subset of (the power set of the set of words over , in other words, the set of languages over ), among all subsets of with the following properties:
is closed under set-theoretic union, concatenation, and Kleene star operations.
Then is a regular language over iff .
Normal form. Every regular language can be generated by a grammar whose productions are either of the form or of the form , where are non-terminal symbols, and is a terminal symbol. Furthermore, for every pair , there is exactly one production of the form .
- 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
|Date of creation||2013-03-22 12:26:31|
|Last modified on||2013-03-22 12:26:31|
|Last modified by||mps (409)|