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? Commented Feb 22, 2023 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. Commented Feb 22, 2023 at 18:27
• @Steven I would assume the grammar of that language. Commented Feb 26, 2023 at 13:17
• @AlanWhitteaker that assumption should be added to the actual question.
– Kai
Commented May 14 at 0:21

Of course one would first have to specify the language to apply the regularity algorithm. Even for a rather restricted class of language specifications such an algorithm would be impossible.

It is undecidable, for a given context-free grammar, to decide whether it accepts a regular language.

Theorem 6.3 (c) in: Bar-Hillel, Perles, Shamir, On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung 14 (1961) 143–172. doi 10.1524/stuf.1961.14.14.143

• The quoted reference has been OCR'ed at the publisher as "On formai properties oî simple phreise structure grammars". Moreover, it claims: Published Online: 1961-04. Commented Feb 22, 2023 at 18:36

A subset $$L ⊆ Σ^*$$ is regular if and only if $$q_L = \{ w \backslash L: w ∈ Σ^* \}$$ is finite. The left-quotient is defined by $$w ∈ Σ^*, L ⊆ Σ^* ↦ w \backslash L = \{ w' ∈ Σ^*: w w' ∈ L \},$$ and satisfies the properties $$ε \backslash L = L,\quad (w w') \backslash L = w' \backslash (w \backslash L),$$ where $$ε ∈ Σ^*$$ denotes the empty word.

Whether $$L$$ is regular or not, the state diagram given by the transitions $$A \overset{x}→ x \backslash A$$, for $$x ∈ Σ$$ and $$A ⊆ Σ^*$$, whose final states are all $$A ∋ ε$$, contains the state diagrams of the minimal deterministic automaton of every $$L ⊆ Σ^*$$: it is The Universal State Diagram.

The set of "states" in the diagram accessible from a given $$L ⊆ Σ^*$$ is just $$q_L$$, itself, the state set is finite precisely when $$L$$ is regular and the portion of the state diagram containing $$q_L$$ with $$L$$ designated as the start state is the minimal deterministic finite state automaton for $$L$$. Otherwise if $$L$$ is not finite, then the automaton is an infinite state automaton - but still deterministic - and may or may not be recursively specifiable.