How to prove that this language is not regular?

Question

Given a language $L$ over the alphabet { 0, 1, [, ,, ] } where if $x \in L$ then $x$ is of the form $[x_0, \dots, x_n]$, in which each of the $x_i$ represents unique binary strings (so $x_i = x_j$ only when $i=j$). Prove that this is not a regular language.

Here is what I have. I have used the pumping lemma.

Suppose $L$ is a regular language. Let $M$ be the DFA that accepts $L$. Let $p$ be the pumping length of $L$. Given $x = [x_0,\dots,x_p] \in L$ we see that $|x| > p$ so pumping lemma applies, so $x = UVW$ where $|UV| < p$, $|v| > 0$, and $UV^iW \in L$.

Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.

Is this a correct proof? If not, what can I do to improve it?

Answer 1

Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.

This is not necessarily true. Suppose $x=[0^p, 0^{p-1}, \dots, 00, 0]$. If $V$ is of length $k<p$ and entirely in $0^p$, we get $UVVW = [0^{p+k}, 0^{p-1}, \dots, 00, 0]$ which is still in $L$.

Normally when doing a proof using pumping lemma, we try to use a more specific $x$ such that the pumping lemma fails. Like this:

Suppose $L$ is regular and let $p$ be its pumping length. We choose $x=[0^p, 0^{p-1}, \dots, 00, 0]\in L$. By the pumping lemma, we can split it into 3 parts $UVW$. Noticed that $V$ cannot include the symbol [ otherwise $UVVW$ contains two [ which is not in $L$. Then, the choices for $V$ is either $0, 00, \dots, 0^{p-1}$. Note that it cannot be $0^p$ because it is subject to the constraint $|UV|\leq p$. No matter what we choose for $V=0^k$, the string $UW=[0^{p-k}, 0^{p-1}, \dots, 0]$ is not in $L$ because $0^{p-k}$ must be one of $0, 00, \dots, 0^{p-1}$. Hence $L$ is not regular.

Answer 2

Your proof doesn't quite work because of the last step: "Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$."

The problem with this is that the substring being pumped is not necessarily an entire $x_i$. It could be the middle of an $x_i$, which would not necessarily invalidate the string's membership in $L$.

Using the pumping lemma makes this problem more complicated than it needs to be, in my opinion. Using the Myhill-Nerode theorem instead gives a proof that the language is not regular in about two sentences, and does a better job of intuitively explaining why the language can't be regular (namely, that DFAs have finite memory, so it can't remember all the $x_i$ to ensure that they are unique).

Here's the tweet-length proof if you want it. Don't write this on your homework, though, or you'll get points off for not showing your work. 🙂

Suppose that $L$ is regular; by Myhill-Nerode, there exist two distinct prefixes "$[x_1,$" and "$[x_2,$" in the same equivalence class. But "$[x_1, x_2]$" is in $L$ and "$[x_2, x_2]$" is not in $L$, contradicting them being in the same equivalence class.

Answer 3

Your proof is incorrect because it is possible in some cases for $UVVW$ to belong to $L$. For example, take $x = [000,001,010]$ and $V =,00$. Then $UVVW = [000,00,001,010]$ whose binary strings are unique.

Here is proof that $L$ is not regular. By way of contradiction, suppose there exists a DFA $M$ with $p$ states that recognizes $L$. Consider the $p+1$ inputs $s_1 = [0^1, s_2 = [0^2, \ldots, s_{p+1} = [0^{p+1}$, where $s_i$ consists of the open bracket followed by $i$ $0$'s.

Observe that the DFA $M$ reaches different states for these different inputs. For if the DFA $M$ reached the same state for input $s_i$ and also input $s_j$ for some $i \ne j$, then it must make the same decision (of accepting versus nonaccepting) after concatenation of the same suffix $,0^i]$, i.e. both $[0^i, 0^i]$ and $[0^j, 0^i]$ must be accepted or both must be rejected by the machine. However, the first string is rejected by the machine and the second string is accepted by the machine.

This implies the DFA must have at least $p+1$ states, a contradiction. Since $p$ was arbitrary, we have proved that there is no DFA (with a finite number of states) recognizing $L$.

The proof above is self-contained and from scratch, but if you want to learn about this proof method look up the Myhill-Nerode theorem and how one can show a language to be nonregular by giving an infinite set of pairwise distinguishable prefixes (the $s_i$'s above).