# 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