1
$\begingroup$

I'm trying to prove that the following language is not regular:

$$\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$$

I'm trying to prove this with the pumping lemma, but I'm kind of confused because $w$ is a language, not an expression like $a^n b^n$, and I don't know how can I partition that into three parts.

$\endgroup$
1
  • $\begingroup$ $w$ is a word, your language simply consists of all binary strings that can be written as some number of repetitions of the same block $\endgroup$
    – Ariel
    Apr 13 at 9:49
2
$\begingroup$

Suppose towards a contradiction that your language $L$ was regular and let $p$ be its pumping length.

Consider the word $w = 0^p 10^p1 \in L$. By the pumping lemma, $w$ can be written as $w=xyz$ with $x=0^{h}$, $y=0^k$, and $z=0^{p-h-k}10^p 1$ (here $h+k \le p$ and $k \ge 1$) such that, for every non-negative integer $i$, $xy^iz \in L$.

Substituting and simplifying, the above means that, for every $i \ge 0$, we have $0^{p-k} 0^{ki} 1 0^p 1 \in L$. In particular, the above must hold for $i=0$, implying that $0^{p-k}1 0^p 1 \in L$. Since $0^{p-k}1 0^p 1 \not\in L$ (recall that $k \ge 1$), this is provides the sought contradiction and concludes the proof.

$\endgroup$
2
$\begingroup$

First to clear up: $w$ is not a language, it is an arbitrary string composed of the symbols $0$, $1$. The "plain English" definition of this language would be "all binary strings that can be expressed as two or more repetitions of any binary string (including the empty string)".

Examples of strings that are members of this language would be $010010$ ($w=010$), $1111$ ($w=1$ or $w=11$) and the empty string $\epsilon$ ($w=\epsilon$).

To prove this language non-regular by pumping lemma, assume there exists a pumping length $p$ for the language. Then let's construct a string belonging in the language with a length of at least $p$ that we can use to demonstrate the impossibility of a legal partition: I suggest $0^p 1^p 0^p 1^p$ which is a member of the language as $w = 0^p 1^p$.

Now it is fairly easy to see any $xyz$ partition using the rules of the pumping lemma is impossible. As $|xy| \leq p$ it must hold that $y$ = $0^n$ for some $n \leq p$. Therefore $xy^2z = 0^{p+n}1^p0^p1^p$. From $|y| \geq 1$ it follows that $n \geq 1$, therefore $xy^2z$ is not a member of the specified language, and there are no legal $xyz$ partitions.

This demonstrates the language doesn't have a finite pumping property, therefore it is not regular.

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