Prove that A is non-regular using K-Complexity Non regularity theorem
-
05-11-2019 - |
Question
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 $
No correct solution