In class our professor showed us 3 methods for proving non-regularity:
- Myhill–Nerode theorem
- Pumping Lemma for regular languages
- Proof of non-regularity, based on the Kolmogorov complexity
Now the first two, Myhill-Nerode theorem and Pumping lemma, I understood well and I was also able to do the exercises to the first two methods. But I did not understand the third one. The Definition of the third method is as follows:
Let $\ L \subseteq (\Sigma_{bool})^* $ be a regular language. Let $\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \} $ for every$\ x \in (\Sigma_{bool})^*$. Then there exists a constant $\ c$, such that for all $\ x,y \in (\Sigma_{bool})^* $
$\ K(y) \leq \lceil log_2(n+1)\rceil+c $
if $\ y $ is the n-th word in the language $\ L_x $.
Now I do not understand how to use this theorem to prove that a language is not regular, I don't really get the concept. We used the kolmogorov complexity before for determining the length of the shortest computer program of an object. How does one prove non-regularity with this theorem? And what is the thought behind it?
Thanks a lot!