Show that the the language $L = \{0^kww0^m | k,m \ge 1, w \in \{0, 1\}^*\}$ is nonregular

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.

• 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. Commented Oct 13, 2022 at 3:57
• Yes! Thanks. My bedtime was a few hours ago. Commented Oct 13, 2022 at 4:12

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.
• 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? Commented Oct 13, 2022 at 11:18