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 $LsubseteqSigma^*$. 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