A sufficient and necessary condition about regularity of a language

Problem Detail: 

Which of the following statements is correct?

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

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

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

4. 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)?

Asked By : Gigili

Answered By : Janoma

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/156