5
$\begingroup$

Without using pumping lemma, can we prove $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular?

Is $L= \{w \mid w \in \{0,1\}^* \}$ non regular? I'm thinking of using concatenation to prove the former isn't regular. If L is non regular then so is LL

$\endgroup$
  • $\begingroup$ The $L$ you defined is regular, it is the whole set of strings... $\endgroup$ – Aryabhata May 3 '13 at 14:27
12
$\begingroup$

Your idea (while interesting) is unlikely to work for two reasons:

  1. How would you express $A$ as a concatenation of a language with itself?
  2. If $L$ is non-regular, it may still be the case that $LL$ is regular. See this post: Is $A$ regular if $A^{2}$ is regular?

You could prove it using the Myhill-Nerode theorem - show that there are infinitely many equivalence classes. Or you could simply use a pumping argument without the lemma. That is, follow the proof of the lemma for this particular language.

$\endgroup$
  • $\begingroup$ Thanks, out of curiosity, does Myhill-Nerode theorem also imply that $L$ is not regular? doesn't it also have infintely many equivalent classes? $\endgroup$ – Iancovici May 3 '13 at 14:35
  • $\begingroup$ The Myhill-Nerode criterion is necessary and sufficient: a language is regular if and only if it has finitely many M.N equivalence classes. In your case, the language has infinitely many, of course. $\endgroup$ – Shaull May 3 '13 at 14:40
  • 3
    $\begingroup$ $L$ is most definitely regular. it's accepted by the all-accepting-automaton (which has a single accept state and stays in it all the time) $\endgroup$ – Sasho Nikolov May 4 '13 at 0:10
  • $\begingroup$ @SashoNikolov: In the original post the language $A$ was called $L$ (or perhaps I misread), anyway, the nonregular language is of course $A$, not $L$. $\endgroup$ – Shaull May 4 '13 at 5:43
7
$\begingroup$

If you can't or don't want to use the pumping lemma, you can always fall back on the pigeonhole principle.

We will prove that $A = \{ww \mid w \in \{0,1\}^* \}$ cannot be the language accepted by any DFA, which means that it isn't regular.

In particular, let $\rm M$ be a DFA with $k < 2^n$ states, and consider the set $P = \{w \mid w \in \{0,1\}^n \}$. Since $P$ has $2^n > k$ members, it follows from the pigeonhole principle that there exists a pair of distinct words $w_1, w_2 \in P$ such that $\rm M$ is in the same state after reading either $w_1$ or $w_2$.

But this implies that, if $\rm M$ accepts the string $w_1 w_1 \in A$, it must also accept the string $w_2 w_1 \notin A$. Thus, $A$ cannot be the language accepted by $\rm M$. Since this holds for any DFA $\rm M$, it follows that $A$ is not a regular language.

$\endgroup$
  • 1
    $\begingroup$ The pumping lemma is exactly the pigeonhole principle as you apply it here ;-) $\endgroup$ – vonbrand May 3 '13 at 20:33
  • 2
    $\begingroup$ @vonbrand Personally I would say the argument is more Myhill-Nerode like, in the sense that two different strings must end up in the same state (after reading the first half of the string). For pumping we consider two positions in the same string. But agreed, finite state => pigeon hole => same state is the common argument in it all. $\endgroup$ – Hendrik Jan May 3 '13 at 21:42
4
$\begingroup$

You can use the incompressibility method to bypass the pumping lemma. I can't find a reference, but the sketch of the proof is something like this:

Let $w$ be a large and incompressible bitstring (Kolmogorov complexity tells us that $w$ exists). Assume for a contradiction that A is regular. Simulate the DFA that accepts $ww$. At the moment that the DFA has read the last symbol of the first copy, 'pause' it and store the whole DFA, plus its current state and the length of the string $|w|$. This can be done in a fixed number of bits for the DFA and a logarithmic term $O(\log|w|)$. Since $w$ is the only string of length $|w|$ that the DFA accepts from this state, it is a description of $w$ in fewer bits than $|w|$ (because we can choose $w$ any length). This is impossible, so it proves that $ww$ cannot be accepted by a DFA.

[Edited after Yuval's comments]

$\endgroup$
  • 3
    $\begingroup$ You also need to store the length of $w$ for an extra $O(\log |w|)$ bits. $\endgroup$ – Yuval Filmus May 3 '13 at 17:29
  • $\begingroup$ @Yuval I expect you're right, but I don't see why. Surely if any other string w' with a different length leads to an accepting state from the stored state, then the DFA accepts ww'... $\endgroup$ – Peter May 3 '13 at 17:38
  • 1
    $\begingroup$ That can well be the case. For example, say $w=00$ and $w'=0000$, then $ww' = (000)^2$. $\endgroup$ – Yuval Filmus May 3 '13 at 17:46
  • $\begingroup$ You're right. Once you've read 0000, there are (at least) two paths to an accepting state: 00 and 0000. $\endgroup$ – Peter May 4 '13 at 0:18
2
$\begingroup$

Let $X = \{0^n1 \mid n \in \mathbb{N}\}$, and observe that each member is uniquely determined from its length.

Consider two strings $x_1, x_2 \in X$ where $x_1 \ne x_2$. Then clearly $x_1 x_1 \in A$ and $x_2 x_1 \not \in A$ (since $x_1$ and $x_2$ have different lengths, either $x_2 x_1$ has odd length or the first half ends with a $0$ but the second half ends with a $1$). In other words, $x_1$ is a witness that $x_1$ and $x_2$ belong to different classes of the Myhill-Nerode equivalence relation.

Since any two unequal strings in $X$ belong to different equivalence classes and there's an infinite number of strings in $X$, the language $A$ has an infinite number of equivalence classes. By the Myhill-Nerode theorem, $A$ cannot be regular.


This feed nicely into a proof based on the pumping lemma: assume that $A$ is regular, and let $p$ be given such that $\forall s \in A: |s| \ge p \Rightarrow (\exists x, y, z: s = xyz \land |xy| \le p \land |y| \ge 1 \land \forall i \in \mathbb{N}: xy^iz \in A)$. In particular, let $s = w^2$ where $w = 0^p1$. Then, by the pumping lemma you could remove a zero from the first copy of $w$, or insert any number of zeros, and still have a member of $A$. This is not true, so $A$ is not regular.


The intuition in both proofs is the same: to recognize that the second half of $s$ equals the first half, you have to remember the entire first half. But there are at least as many distinct first halves as there are members of $\mathbb{N}$, so no finite memory automaton can do that.

$\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.