According to the answer provided by Janoma, there are several methods to determine the regularity of a language.
Let L ⊆ Σ∗. The following conditions are equivalent:
- L is generated by a regular expression (i.e., the definition of regular language).
- L is recognized by a nondeterministic finite automaton (Kleene).
- L is recognized by a nondeterministic finite automaton without ε-transitions.
- L is recognized by a deterministic finite automaton (Scott and Rabin).
- L is generated by a grammar (N, Σ, P, S), where N is a finite subset of Σ∗ (Frazier and Page).
- L is generated by a left (resp. right) regular context-free grammar.
- The index of the Nerode relation ≡L is finite (Anil Nerode, Linear automaton transformations, 1958). This is widely (and incorrectly) known as the Myhill-Nerode theorem. ≡L is the relation used to build the minimal DFA of a regular language.
- The index of the Myhill relation ∼L is finite (John Myhill, Finite Automata and the Representation of Events, 1957). ∼L is the relation used to build the syntactic monoid of an arbitrary language.
- The syntactic monoid of L is finite (consequence of Myhill's result). We note here that the syntactic monoid, apart from being defined by using relation ∼L, can be defined as a minimal monoid (in size) that recognizes L as a preimage of a homomorphism.
- L can be recognized by a read-only Turing Machine (trivial).
- L can be defined by a formula in Monadic second-order logic over strings (Büchi).
However, in none of these methods is there a clear, step by step process that can be followed to conclusively prove that a language is regular.
Does such an algorithm exist? Please provide the necessary references as well.