- it can be accepted by a deterministic finite state automaton.
- it can be accepted by a non-deterministic finite state automaton
- it can be described by a regular expression.
- it can be generated by a regular grammar
- it can be accepted by a read-only Turing machine

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. The shuffle operation, when applied to two regular languages, yields another regular language. The right quotient and the left quotient of a regular language by an arbitrary language is also regular.

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 Myhill-Nerode Theorem or 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

*uw*in*L*if and only if*vw*in*L*for all*w*in Σ*

- Department of Computer Science at the University of Western Ontario:
*Grail+*, http://www.csd.uwo.ca/research/grail/. A software package to manipulate regular expressions, finite-state machines and finite languages. Free for non-commercial use.\n