0
$\begingroup$

Caveat. You have to show this specifically by showing there exists an infinite set that is pairwise distinguishable with respect to L.

This question was on a quiz which we had 12 minutes to complete (this wasn't the only question!) I can see that this isn't a regular language but I cannot come up with any set that is pairwise distinguishable with respect to L. (No you can't use the pumping lemma). This will probably be on an exam I'm taking tomorrow so your help is greatly appreciated.

$\endgroup$
2
  • $\begingroup$ Going out on a limb here and guessing that you mean pairwise distinguishable? I am not sure how this would prove that the language is non-regular, otherwise. $\endgroup$
    – big-Oaf
    Commented Oct 13, 2022 at 3:57
  • $\begingroup$ Yes! Thanks. My bedtime was a few hours ago. $\endgroup$
    – Zachary
    Commented Oct 13, 2022 at 4:12

1 Answer 1

0
$\begingroup$

Let $$\mathcal{D}_L := \{ 0^j 1 0^j 1 \mid j \ge 1\}$$ be the desired set. Clearly it is infinite. We show that a subset of the set is pairwise distinguishable with respect to the given language $L$.

For any two strings $0^i 1 0^i 1$ and $0^{i+1} 1 0^{i+1} 1, \text{ }(\text{for }i \ge 2)$ in $\mathcal{D}_L$, we have — by appending the string $0^{i+1}$ — that $0^i 1 0^i 1 0^{i+1} \in L$ whereas $0^{i+1} 1 0^{i+1} 1 0^{i+1} \notin L$. Thus, the two strings are distinguishable. More generally, for every pair of strings $x, y \in \mathcal{D}_L$, there is a string $z$ (appropriately chosen) such that $xz \in L \Leftrightarrow yz \notin L$.

Since we know that for a set, $\mathcal{D}_L$, of pairwise distinguishable strings with respect to $L$, any DFA for $L$ must have at least $\vert \mathcal{D}_L \vert$ states; and since in our case $\vert \mathcal{D}_L \vert$ is infinite, we conclude that no DFA can decide $L$. So, it is not regular.

$\endgroup$
4
  • $\begingroup$ You might find it useful to review these notes as well. $\endgroup$
    – big-Oaf
    Commented Oct 13, 2022 at 4:26
  • $\begingroup$ I actually came up with something very similar to this on the quiz and he gave me 1/10. But I think the set $D_L$ is not pairwise distinguishable because $0^i101$ and $0^{i+2}101$ are indistinguishable? $\endgroup$
    – Zachary
    Commented Oct 13, 2022 at 11:18
  • $\begingroup$ Yes, I made an error. I'll update my answer. $\endgroup$
    – big-Oaf
    Commented Oct 13, 2022 at 13:27
  • $\begingroup$ Hey this is great. Thanks $\endgroup$
    – Zachary
    Commented Oct 14, 2022 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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