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

Question

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

Answer 1

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}$.