Myhill-Nerode Theorem with constraint

179 Views Asked by At

I am trying to to understand the Myhill-Nerode Theorem with the example. $L = \{{0^i1^j}|\ j > i\}$ I have read some article but still cannot fully understand,what I know about is that I have to choose the subset$\sum^*$ and find two string x and y and z so that if the language can distinguishable, then it is nonregular.

But I don't know how to do this with the constraint j > i, can you demonstrate the example.

1

There are 1 best solutions below

0
On BEST ANSWER

Just consider sequence $x_n = 0^n, n \ge 0$ and prove that $ x_i \not\equiv_L x_j$ for every $i \ne j $. You can do this by finding a word $z$ such $ x_iz \not \in L $ and $ x_jz \in L $ or vise versa. For example, if $i < j$ just take $z = 1^j$ and notice that $ x_iz \in L $ and $ x_iz \not \in L $. So you can conclude that all elements of the sequence are pairwise $L$ - nonequivalent and hence our language is not regular since the number of equivalence classes would not be finite. For more info check this question.