In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expressions engines, which are augmented with features that allow recognition of non-regular languages). Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars. Formal definition The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language. If A is a regular language, A* (Kleene star) is a regular language. Due to this, the empty string language {ε} is also regular. If A and B are regular languages, then A ∪ B (union) and A • B (concatenation) are regular languages. No other languages over Σ are regular. See regular expression for syntax and semantics of regular expressions. Examples All finite languages are regular; in particular the empty string language {ε} = Ø* is regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of a 's, or the language consisting of all strings of the form: several a 's followed by several b 's. A simple example of a language that is not regular is the set of strings { anbn | n ≥ 0 }. Intuitively, it cannot be recognized with a finite automaton, since a finite automaton has finite memory and it cannot remember the exact number of a's. Techniques to prove this fact rigorously are given below. Equivalent formalisms A regular language satisfies the following equivalent properties: it is the language of a regular expression (by the above definition) it is the language accepted by a nondeterministic finite automaton (NFA) it is the language accepted by a deterministic finite automaton (DFA) it can be generated by a regular grammar it is the language accepted by an alternating finite automaton it is the language accepted by a two-way finite automaton it can be generated by a prefix grammar it can