Proof of non-regularity, based on the Kolmogorov complexity

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!

To my knowledge, this is not one of the "classical" approaches used to characterize regular languages.

This approach is discussed in "A New Approach to Formal Language Theory by
Kolmogorov Complexity", by Ming Li and Paul M.B. Vitanyi (see section 3.1).

They give several examples where one can use the statement you mentioned instead of using the pumping lemma. For example, proving non-regularity of $L$ where

$L=\left\{1^p|\text{p is prime}\right\}$.

Given some $x\in\Sigma^*$, $L_x=\left\{y| \hspace{1mm} xy=1^p \land \text{p is prime}\right\}$. Let us choose $x=1^{p'}$ where $p'$ is the $k$'th prime. Let $y_1$ be the first word in $L_x$. Obviously, $y_1=1^{p-p'}$ where $p$ is the $k+1$ prime. According to the statement you mentioned, $K(y_1)\le c$ ($n=1$), for some constant $c$ depending only on $L$ (see paper).

Since this holds for all $x$, we can bound the Kolmogorov complexity of all elements in $S=\left\{y_1^x| x=1^p \text{ for prime $p$ } \land \text{$y_1^x$ is the first string in $L_x$}\right\}$ by the same constant $c$. However, we saw that $S$ actually consists of differences between consecutive primes, i.e.
$S=\left\{1^{p_{k+1}-p_k} | k\ge 1\right\}$ where $p_k$ is the $k$'th prime. Since we know $S$ cannot have bounded Kolmogorov complexity (prime differences get arbitrarily large), this means $L$ cannot be regular.

StackExchange Computer Science Q#64784, answer score: 9