11
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ I would rather say that (4) is correct: the pumping lemma is designed to show that some language is not regular (it states if L is regular then ..). Also, (3) is false: en.wikipedia.org/wiki/… $\endgroup$ – jmad Mar 9 '12 at 13:28
  • $\begingroup$ Agree with @jmad: the pumping lemma is sufficient, not necessary. $\endgroup$ – Patrick87 Mar 9 '12 at 13:34
  • $\begingroup$ @jmad: The WP article I linked to in my question stands that "both the original and the general version of the pumping lemma give a necessary but not sufficient condition for a language to be regular." $\endgroup$ – Gigili Mar 9 '12 at 13:35
  • $\begingroup$ @Gigli: yes. Regular. Not "non-regular". $\endgroup$ – jmad Mar 9 '12 at 13:37
  • $\begingroup$ @jmad: Oops, you're right. I'll edit the question, thank you. $\endgroup$ – Gigili Mar 9 '12 at 13:38
18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that for the last statement, we have to restrict ourselves to WMSO or, equivalently, finite words. MSO in general can also express $\omega$-regular languages. $\endgroup$ – Raphael Mar 9 '12 at 16:27
  • 1
    $\begingroup$ You might want to add '$L$ is recognized by a left/right regular context-free grammar', for completion's sake. $\endgroup$ – Alex ten Brink Mar 9 '12 at 18:36
  • $\begingroup$ @AlextenBrink Forgot that one! Thanks for mentioning it. Do you have a reference to include? $\endgroup$ – Janoma Mar 9 '12 at 18:49
  • $\begingroup$ @Janoma: sorry, I can't find any. The proof is extremely simple though (going to an NFA and back). $\endgroup$ – Alex ten Brink Mar 9 '12 at 18:59
9
$\begingroup$

It is sufficient (and necessary) to show the existence of a DFA, NFA or regular expression to prove that a language is regular, which refutes (1) and (2). To show that a language is not regular it is needed to show that a DFA, NFA or regular expression does not exists.

The pumping lemma is a useful tool to show (possibly by contradiction) that a language is not regular, by showing that no DFA exists.

$\endgroup$
  • 1
    $\begingroup$ The pumping lemma, technically speaking, shows that a DFA does not exist for the language. $\endgroup$ – Patrick87 Mar 9 '12 at 13:22
  • $\begingroup$ @Patrick87: Thanks. I edited the answer to add this detail. $\endgroup$ – Victor Stafusa Mar 9 '12 at 13:30
  • 1
    $\begingroup$ Just for the sake of being pedantic: proofs using the pumping lemma are not proof by contradiction. Since you prove a negative statement (P -> False), it is perfectly fine from an intuitionist's point of view to assume that P holds. $\endgroup$ – gallais Mar 9 '12 at 14:11
  • 2
    $\begingroup$ You can write it as a proof by contradiction: "Assume L is regular. Then there is pumping constant $p$. Choose $w$ ... The pumped word is not in $L$. Contradiction.$ $\endgroup$ – Raphael Mar 9 '12 at 16:25
  • 1
    $\begingroup$ You can write it, but you don't need the contradiction. That is the point. $\endgroup$ – Janoma Mar 9 '12 at 16:29
6
$\begingroup$

The condition 'there exists a regular expression that generates exactly $L$' is a necessary and sufficient condition for the regularity of a language $L$, by grace of being its definition.

This condition doesn't exactly make it easy to prove non-regularity of a language though. I'm not aware of any conditions that are easy to check that always prove non-regularity of a non-regular language.

There are two more 'tests' that can prove the non-regularity of a language (though they may not work): you can try to give some regular language such that their union/intersection/difference/concatenation/quotient is non-regular (there are more operations like this), and you can try to count how many words it generates and check if it contradicts the expression for the number of words in a regular language (as can be found on the Wikipedia page you linked).

$\endgroup$
6
$\begingroup$

There is this wonderful connection between formal language theory and formal power series proofed by Chomsky and Schützenberger [CS63]. In the form found in [SS78] Chap. II, Theorem 5.1

Let $L$ be a regular language and $\mathbb{K}$ a semiring. Then $\mathrm{char}(L)$ is $\mathbb{K}$-rational.

So if you look at the characteristic series $\mathrm{char}(L)$ of a language and it turns out not to be rational, it can’t be a regular language. So you don’t have to use the pumping lemma all the time. With the help of computer algebra systems such a check is not too hard to do.

[SS78] Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag, New York, 1978.

[CS63] Noam Chomsky and Marcel P. Schützenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Languages, pages 118–161. North Holland, 1963.

$\endgroup$
4
$\begingroup$

By the Myhill-Nerode theorem, a language is regular iff there are finitely many equivalence classes of the indistinguishability relation $I_{L}$. Two strings $x$ and $y$ are said to be indistinguishable, written $x I_{L} y$, iff:

  1. For all strings $z_{x}$ such that $xz_{x} \in L$, also $yz_{x} \in L$.
  2. For all strings $z_{y}$ such that $yz_{y} \in L$, also $xz_{y} \in L$.

Intuitively, this corresponds to the idea that there are finitely many states in the state machine. In fact, the number of distinct equivalence classes under the $I_{L}$ relation is precisely the number of states in a minimal DFA for $L$.

Myhill-Nerode is especially useful because you can construct positive proofs (the language is regular) and negative proofs (the language isn't regular) using the same framework: the relation $I_{L}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.