1
$\begingroup$

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 $

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

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.

$\endgroup$
  • $\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$ – ZeroDay Fracture Apr 12 '18 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$ – Yuval Filmus Apr 12 '18 at 18:22
  • $\begingroup$ got it, that was a stupid question I understand now $\endgroup$ – ZeroDay Fracture Apr 12 '18 at 19:51
  • $\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$ – ZeroDay Fracture Apr 13 '18 at 0:00
  • $\begingroup$ Kolmogorov randomness doesn't appear in my answer. $\endgroup$ – Yuval Filmus Apr 13 '18 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.