2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you so much! This is the first time I have heard of such a theorem, and I find it super interesting. Unfortunately, we are only allowed to use pumping lemma for this question :(. $\endgroup$ – Noobcoder Nov 27 '19 at 2:42
  • $\begingroup$ @Noobcoder Ah, homework. Where you're only allowed to use the theorems that have already been covered in the lectures. I don't know if I can help you fix your pumping lemma proof, because I can't say I've used the pumping lemma once since the class where I learned it. In the "real world", you usually just look at the language and mutter there's no way there's a DFA for that. $\endgroup$ – Aaron Rotenberg Nov 27 '19 at 2:57
  • $\begingroup$ hahaha I guess that's like a lot of the things you learn in school. $\endgroup$ – Noobcoder Nov 27 '19 at 3:08
  • $\begingroup$ @Noobcoder Heh, yep. As well as accepting the answer that solved the problem for you, remember to upvote any answers that you found helpful. $\endgroup$ – Aaron Rotenberg Nov 27 '19 at 4:44
1
$\begingroup$

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

| cite | improve this answer | |
$\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.