Regular Language - Deciding Whether A Language Is Regular

Deciding Whether A Language Is 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 regular, one often uses the Myhill–Nerode theorem or the pumping lemma among other methods.

There are two purely algebraic approaches to define regular languages. If:

• Σ is a finite alphabet,
• Σ* denotes the free monoid over Σ consisting of all strings over Σ,
• f : Σ* → M is a monoid homomorphism where M is a finite monoid,
• S is a subset of M

then the set is regular. Every regular language arises in this fashion.

If L is any subset of Σ*, one defines an equivalence relation ~ (called the syntactic relation) on Σ* as follows: u ~ v is defined to mean

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

The language L is regular if and only if the number of equivalence classes of ~ is finite (A proof of this is provided in the article on the syntactic monoid). When a language is regular, then the number of equivalence classes is equal to the number of states of the minimal deterministic finite automaton accepting L.

A similar set of statements can be formulated for a monoid . In this case, equivalence over M leads to the concept of a recognizable language.