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}) &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

$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}) &gt; 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 $
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.