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

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

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.

StackExchange Computer Science Q#71311, answer score: 3