I need to prove that L = { 0^(3n)1^(2n) | n>0 } is irregular using The Myhill-Nerode theorem
I understand I need to demonstrate that it is not a finite union of equivalence classes, by using the the concept of distinguishability between strings:
strings x and y are distinguishable if there exists some string z such that xz is in L but yz is not in L, or vice versa.
However, if we add any z to a word in the language L, it will no longer be a member of L. For example, adding 0's is not allowed because 0 can only come before 1 in L. Adding 1's is also not allowed because it would result in a word of the form 0(3n)1^(2n+i), which breaks the 3:2 ratio of 0's and 1's that is required for a word to be in L.
what am I missing?
Best Answer
Myhill-Nerode theorem speaks about splitting all words to classes, not only words in $L$.
Words in $L$ are indeed all equivalent: if we add an empty word to word from $L$, we (of course) get word from $L$, and if we add any non-empty word, we get word not from $L$.
But words $x_n = 0^{3n}$ for different $n$ are not equivalent: if we have words $x_n$ and $x_m$ with $n \neq m$, then adding $1^{2n}$ to both we get $0^{3n}1^{2n} \in L$ and $0^{3m}1^{2n} \notin L$. Thus we have infinite number of pairwise non-equivalent words, and so infinite number of equivalence classes.