Using Myhill-Nerode to prove a language is non-regular

Question

I'm trying to prove

L={w∈{0,1}∗:w contains more 00 substrings than 11 substrings}

is a non regular language using Myhill-Nerode theorem.

I'm a bit lost and not sure what to do. Thanks

Answer 1

The basic idea here is that you are trying to show that there are infinitely many indistinguishable sets in $L$.

Distinguishable Strings: Let $L$ be a language over an alphabet $\sum$. We say that two strings $x$ and $y$ are distinguishable with respect to $L$ if there is a string $z$ such that $xz \in L$ and $yz \notin L$, or vice versa. That is, if we append $z$ to $x$ and $y$, the machine that processes $xz$ will be in a different state than if it were to process $yz$.

An indistinguishable set is then a collection of strings that are indistinguishable from one another but distinguishable from every other indistinguishable set.

Consider a FA $M$ that accepts $L$ = { even 0s } with alphabet $\sum = \{0,1\}$. The minimal FA for this machine has two states. There exists an indistinguishable set for every state, one set containing odd number of 0s and one set containing even number of 0s.

For your language, consider that you have { 1 00 substrings, 0 11 substrings } $\ne$ { 2 00 substrings, 1 11 substrings } $\ne$ { 2 00 substrings, 0 11 substrings } $\ne$ { 3 00 substrings, 2 11 substrings } $\ne$ { 3 00 substrings, 1 11 substrings } $\ne$ ... $\ne$ { $k$ 00 substrings, $l$ 11 substrings | $k > l$ }. Each of these sets is distinguishable from other. In other words, your minimal FA would require infinitely many states due to its need for counting. Since an FA cannot have infinitely many states, the language cannot be regular.

Answer 2

Myhill-Nerode theorem defines an equivalence relation $xRy$ when $\forall w, xw \in L$ iff $yw \in L$

Then it says that this relation $R$ partitions $L$ in a finite number of partitions iff $L$ is regular.

So what you have to do is to show that if $L$ is not regular then this relation partitions $L$ into infinite number of partitions. For this you need to specify infinitely many strings which are not equivalent according to $R$.

Here are more details, How to prove that a language is not regular.

Answer 3

Consider any relation R which on $\{0,1\}^*$ such that :

1. for any pair of strings $x, y$ related by $R$ we have, $xz, yz$ also related by $R$ (right congruence property)

2. any pair of strings $x, y$ are related by $R$ if either both $x, y$ are in $L$ or both are out of $L$ (refinement property)

Now if we have the property of finite index as well then by Myhill-Nerode theorem this will be a regular language, so to prove that this is not the case we should try to show that this doesn't have the finite index property:

consider 2 strings $a=(000)^n(11)^n$ and $b=(0000)^n(11)^n$ assume $a\ R\ b$ then by right congruence $(a1^n)\ R\ (b1^n)$ but $a1^n$ is not in $L$ but $b1^n$ is in $L$, therefore $R$ can not be of finite index, hence $L$ is non regular.