Problem Detail: 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})^* | xyin 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!
Answered By : Ariel
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 $xinSigma^*$, $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} | kge 1right}$ 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/64784
Related
