A sufficient and necessary condition about regularity of a language

Which of the following statements is correct?

• sufficient and necessary conditions about regularity of a language exist but not discovered yet.

-
There's no sufficient and necessary condition about regularity of a
language.

-
Pumping lemma is a necessary condition for non-regularity of a
language.

• Pumping lemma is a sufficient condition for non-regularity of a

language.


I know #(4) is correct and #(3) is false because "the converse of this statement is not true: a language that satisfies these conditions may still be non-regular", but what can be said about (1) and (2)?

Here are some necessary and sufficient conditions for a language to be regular.

Theorem. Let $L\subseteq\Sigma^*$. 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 $\varepsilon$-transitions.

• $L$ is recognized by a deterministic finite automaton (Scott and Rabin).

• $L$ is generated by a grammar $(N,\Sigma,P,S)$, where $N$ is a finite subset of $\Sigma^*$ (Frazier and Page).

• $L$ is generated by a left (resp. right) regular context-free grammar.

• The index of the Nerode relation $\equiv_L$ is finite (Anil Nerode, Linear automaton transformations, 1958). This is widely (and incorrectly) known as the Myhill-Nerode theorem. $\equiv_L$ is the relation used to build the minimal DFA of a regular language.

• The index of the Myhill relation $\sim_L$ is finite (John Myhill, Finite Automata and the Representation of Events, 1957). $\sim_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 $\sim_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).

If a language does not satisfy the conditions of the pumping lemma for regular languages, then it is not regular. This means pumping lemma is a sufficient condition for the non-regularity of a language.

In summary, statements 1, 2 and 3 are false, while statement 4 is true, as you mentioned.

StackExchange Computer Science Q#156, answer score: 20