What is wrong with my application of the Myhill-Nerode theorem on this language?

289 Views Asked by At

Let $L=\left\{ w\in\Sigma^{*}\mid w\text{ has an equal number of 01 and 10}\right\}$ (e.g. $010\in L$) over $\Sigma=\left\{ 0,1\right\} $

I initially tried to prove that $L$ is not regular

Proof: Consider the strings $s_{n}=\left(01\right)^{n}=\overbrace{0101\ldots01}^{n\text{ times}}$ and $t_{m}=\left(11\right){}^{m}$ for any $m,n\in\mathbb{N}$ and the suffix $z=0$.

Note that for any choice of $m$ and $n$ $0101\ldots0\in L$ but $11\ldots10\notin L$ and therefore $z$ is a separating suffix.

Since $m$ and $n$ were not specified we have $\infty$ equivalence classes and therefore, by Myhill-Nerode, $L\notin REG $

Later, I came up with a DFA that definitely accepts $L$, meaning the above proof is wrong. Where is the fault in the argument?

2

There are 2 best solutions below

0
On

$L$ is the language of words such that the first letter is equal to the last letter (and the empty word). So there are only 5 equivalence classes :

  1. empty word
  2. 0 and 0w0 for any word w
  3. 1 and 1w1 for any word w
  4. 0w1 for any word w
  5. 1w0 for any word w
0
On

Answering my own question (With the help of Alex Vong and Xoff)

The problem with the proof is chiefly that $s_{n}$ and $t_{m}$ are of different forms and therefore proving that there exists a separating suffix between them only proves that there are at least two equivalence classes. Namely, $[s_{n}]$ and $[t_{m}]$.

A proper proof of non regularity with Myhill-Nerode requires both strings to be of the same form, say for any $n\neq m$ there exists a seperating suffix between $s_{n}$ and $s_{m}$ , then one can make the claim that since the set $\{s_{n}\mid n\in \mathbb{N} \}$ is infinite and no two words in it are equivalent, then the set $\{[s_{n}]\mid n\in \mathbb{N} \}$ is infinite as well.