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

  • $\begingroup$ 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. $\endgroup$ Apr 12, 2018 at 17:04
  • $\begingroup$ Thank you I have seperated it and will edit this to just include the first part. $\endgroup$ Apr 12, 2018 at 17:47

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.