Equivalent ways of describing regular languages are deterministic and non-deterministic finite automata, regular grammars, read-only Turing machines and regular expressions.
All finite languages are 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.
The the result of the union, intersection and set-difference operations when applied to regular languages is itself a regular language; the complement of every regular language is a regular language as well. Reversing every string in a regular language yields another regular language. Concatenating two regular languages (in the sense of concatenating every string from the first language with every string from the second one) also yields a regular language.
To locate the regular languages in the Chomsky hierarchy, one notices that every regular language is context-free. The converse is not true: for example the language consisting of all strings having the same number of a's as b's is context-free but not regular. To prove that a language such as this is not regular, one uses the pumping lemma.
There are two purely algebraic approaches to defining regular languages. If Σ is a finite alphabet and Σ* denotes the free monoid over Σ consisting of all strings over Σ, f : Σ* -> M is a [monoid homomorphism]? where M is a finite monoid, and S is a subset of M, then the set f -1(S) is regular. Every regular language arises in this fashion.
If L is any subset of Σ*, one defines an equivalence relation ~ on Σ* as follows: u ~ v is defined to mean
![[Home]](wikipedia.png)