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}) &gt; 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) &gt; c$, and let x = $0^k$ then we get the following$Y^A_{x,1} = 1^k$&lt;-why? and $Y^A_{x,2} = 01^{k+1}$&lt;- again why
therefore $C(Y^A_{x,1}) = C(1^k) &gt; c + log(1)$ QED
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}$.