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

$A=\{0^{2n}1x∣n∈\mathbb{N}, x∈\{0,1\}^∗$, and $|x|=n\}$ Prove that A is non-regular using KCR

All we have to do is to pick a $x$ and $y$ s.t the concatenation $xy \in A$.

If I let $x = 0^{2n}1$ and let $y = x$, then we build the set $Y^A_{x}$ given the $x$ and $y$ from above $Y^A_{x,1} = 001(01)$ and next element in the set $Y^A_{x,2} = 00001(0101)$.

Here is where I get stuck since I know I need to show $C(Y^A_{x,1}) > c + log(1)$ would this suffice to show that because of that this language is not regular? What is the best way to split the language for $x$ and $y $

  • $\begingroup$ You cannot "let $y=x$". In fact, $Y^A_{x,1} = 0^n$ and $Y^A_{x,2} = 0^{n-1}1$. $\endgroup$ Apr 12, 2018 at 18:16
  • $\begingroup$ what abot $y = 1x$? $\endgroup$ Apr 12, 2018 at 18:17
  • $\begingroup$ You cannot choose $y$ at all. $\endgroup$ Apr 12, 2018 at 18:17

1 Answer 1


Suppose that $A$ is regular. Then there exists a constant $c$ such that for all $x \in \Sigma^*$ and for all $n$ such that $Y^A_{x,n}$ exists, $C(Y^A_{x,n}) \leq \log n + c$.

Let us take $x = 0^{2m}1$. Then $Y^A_{x,n}$ exists as long as $n \leq 2^m$ – in fact, $Y^A_{x,n}$ is just the $n$th binary string of length $m$. Therefore $$ C(\text{$n$th binary string of length $m$}) \leq \log n + c. $$ In particular, choosing $n=1$, we get $$ C(0^m) \leq c. $$ Clearly this fails for large enough $m$. This contradiction shows that $A$ is not regular.

  • $\begingroup$ ok I think I see what is being done. Why would n $\leq 2^m$ is this because of the length of $|x| = n$ limitation? $\endgroup$ Apr 12, 2018 at 18:21
  • $\begingroup$ I believe you should be able to fill in all the details on your own. This is the only way to understand the material. $\endgroup$ Apr 12, 2018 at 18:22
  • $\begingroup$ I think I get it, the enumerated string is at most the length of the index in the enumeration since it is kolmogorov random so $C(0^m) \leq c$. Do correct me if im mistaken. $\endgroup$ Apr 13, 2018 at 0:00
  • $\begingroup$ Kolmogorov randomness doesn't appear in my answer. $\endgroup$ Apr 13, 2018 at 5:06

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.