# Algorithm to determine the regularity of a language

According to the answer provided by Janoma, there are several methods to determine the regularity of a language.

## Theorem

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.

• What would be the input of the algorithm? Feb 22 at 17:23
• It is not "trivial" that a read-only Turing machine accepts only regular languages. Note a TM may move in two directions. Also excursions into the empty part of the tape have to be accounted for. Feb 22 at 18:27
• @Steven I would assume the grammar of that language. Feb 26 at 13:17