# Prove that A is non-regular using K-Complexity Non regularity theorem

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$

• You cannot "let $y=x$". In fact, $Y^A_{x,1} = 0^n$ and $Y^A_{x,2} = 0^{n-1}1$. – Yuval Filmus Apr 12 '18 at 18:16
• what abot $y = 1x$? – ZeroDay Fracture Apr 12 '18 at 18:17
• You cannot choose $y$ at all. – Yuval Filmus Apr 12 '18 at 18:17

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{nth 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.
• 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? – ZeroDay Fracture Apr 12 '18 at 18:21
• 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. – ZeroDay Fracture Apr 13 '18 at 0:00