# Non Regularity proof using Kolmogorov Complexity (Li - Vitanyi Theorem)

When proving a language is non regular we can use Kolmogorov complexity.

As far I know to do this we just have to use this satisfy the following conditions

Given $$Y^A_{x,n}$$= the nth string $$y∈Σ^∗$$ (in lex order) such that $$xy∈A$$ (if n such y exits). So what completes $$x$$ if adding $$n$$ such y's brings us to an element in the set A

Given $$A \subseteq \Sigma^*$$ has the following property, then it is not regular

For every $$c \in \mathbb{Z^+}$$ there exits $$x \in \Sigma^*$$, and $$n \in \mathbb{Z^+}$$ s.t. $$Y^A_{x,n}$$ exits and K-Comp $$C(Y^A_{x,n}) > c + log(n)$$

We are trying to show weather given a DFA will it end in a final state after certain number of steps and this process will tell us if that is not a possibility since we cannot prove regularity just non-regularity

Keeping that in mind I am trying to prove this language is not regular

Let us run through a simple example B = $$\{0^n1^n | n \in \mathbb{N}\}$$

Proof: Let c $$\in \mathbb{N}$$. Choose k $$\in \mathbb{Z^+}$$ such that $$C(1^k) > c$$, and let x = $$0^k$$ then we get the following$$Y^A_{x,1} = 1^k$$<-why? and $$Y^A_{x,2} = 01^{k+1}$$<- again why

therefore $$C(Y^A_{x,1}) = C(1^k) > c + log(1)$$ QED

• You are asking three different questions. The usual rule is one question per post. I answered your first two questions. If you are interested in an answer to the other question, I suggest posting it separately. – Yuval Filmus Apr 12 '18 at 17:04
• Thank you I have seperated it and will edit this to just include the first part. – ZeroDay Fracture Apr 12 '18 at 17:47

You are asking many questions. Let me answer your first two, regarding $Y^A_{0^k,n}$ for $A = \{0^k1^k : k \geq 0\}$. Recall that $Y^A_{0^k,1},Y^A_{0^k,2},\ldots$ is the list of all strings $y$ such that $0^ky \in A$, arranged in some order - apparently first according to length, and then lexicographically. It is easy to see that the strings $y$ such that $0^ky \in A$ are of the form $0^m1^{k+m}$. Arranged according to length, these are $1^k,01^{k+1},0^21^{k+2},\ldots$, and more generally, $Y^A_{0^k,n} = 0^{n-1}1^{k+n-1}$.