1
$\begingroup$

When proving a language is non regular we can use Kolmogorov complexity.

As far I know to do this we just have to use this satisfy the following conditions

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

Keeping that in mind I am trying to prove this language is not regular


Let us run through a simple example B = $\{0^n1^n | n \in \mathbb{N}\}$

Proof: Let c $\in \mathbb{N}$. Choose k $\in \mathbb{Z^+}$ such that $C(1^k) > c$, and let x = $0^k$ then we get the following$Y^A_{x,1} = 1^k$<-why? and $Y^A_{x,2} = 01^{k+1}$<- again why

therefore $C(Y^A_{x,1}) = C(1^k) > c + log(1)$ QED

$\endgroup$
  • $\begingroup$ You are asking three different questions. The usual rule is one question per post. I answered your first two questions. If you are interested in an answer to the other question, I suggest posting it separately. $\endgroup$ – Yuval Filmus Apr 12 '18 at 17:04
  • $\begingroup$ Thank you I have seperated it and will edit this to just include the first part. $\endgroup$ – ZeroDay Fracture Apr 12 '18 at 17:47
1
$\begingroup$

You are asking many questions. Let me answer your first two, regarding $Y^A_{0^k,n}$ for $A = \{0^k1^k : k \geq 0\}$. Recall that $Y^A_{0^k,1},Y^A_{0^k,2},\ldots$ is the list of all strings $y$ such that $0^ky \in A$, arranged in some order - apparently first according to length, and then lexicographically. It is easy to see that the strings $y$ such that $0^ky \in A$ are of the form $0^m1^{k+m}$. Arranged according to length, these are $1^k,01^{k+1},0^21^{k+2},\ldots$, and more generally, $Y^A_{0^k,n} = 0^{n-1}1^{k+n-1}$.

$\endgroup$

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.