Prova de não regularidade, com base na complexidade de Kolmogorov

Na aula, nosso professor nos mostrou três métodos para provar a não regularidade:

1. Teorema de Myhill – Nerode
2. Lemma de bombeamento para idiomas regulares
3. Prova de não regularidade, com base na complexidade de Kolmogorov

Agora, os dois primeiros, teorema de Myhill-Nerode e lema de Pumping, eu entendi bem e também pude fazer os exercícios para os dois primeiros métodos. Mas eu não entendi o terceiro. A definição do terceiro método é a seguinte:

Deixei $\ L \subseteq (\Sigma_{bool})^*$ser uma linguagem regular. Deixei$\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \}$ para cada$\ x \in (\Sigma_{bool})^*$. Então existe uma constante$\ c$, de modo que para todos $\ x,y \in (\Sigma_{bool})^*$

$\ K(y) \leq \lceil log_2(n+1)\rceil+c$

E se $\ y$ é a n-ésima palavra no idioma $\ L_x$.

Agora eu não entendo como usar esse teorema para provar que uma linguagem não é regular, eu realmente não entendo o conceito. Usamos a complexidade de kolmogorov antes para determinar o comprimento do programa de computador mais curto de um objeto. Como provar a não regularidade com esse teorema? E qual é o pensamento por trás disso?

Muito obrigado!

Que eu saiba, essa não é uma das abordagens "clássicas" usadas para caracterizar linguagens regulares.

Essa abordagem é discutida em "Uma Nova Abordagem da Teoria da Linguagem Formal pela Complexidade de Kolmogorov" , de Ming Li e Paul MB Vitanyi (consulte a seção 3.1).

Eles dão vários exemplos em que se pode usar a declaração que você mencionou em vez de usar o lema de bombeamento. Por exemplo, provar a não regularidade de$L$ Onde

$L=\left\{1^p|\text{p is prime}\right\}$.

Dado alguns $x\in\Sigma^*$, $L_x=\left\{y| \hspace{1mm} xy=1^p \land \text{p is prime}\right\}$. Vamos escolher$x=1^{p'}$ Onde $p'$ é o $k$é o primeiro. Deixei$y_1$ ser a primeira palavra em $L_x$. Obviamente,$y_1=1^{p-p'}$ Onde $p$ é o $k+1$prime. De acordo com a declaração que você mencionou,$K(y_1)\le c$ ($n=1$), por alguma constante $c$ dependendo apenas de $L$ (veja papel).

Uma vez que isso vale para todos $x$, podemos limitar a complexidade de Kolmogorov de todos os elementos em $S=\left\{y_1^x| x=1^p \text{ for prime $p$ } \land \text{$y_1^x$ is the first string in $L_x$}\right\}$ pela mesma constante $c$. No entanto, vimos que$S$ na verdade consiste em diferenças entre primos consecutivos, ou seja, $S=\left\{1^{p_{k+1}-p_k} | k\ge 1\right\}$ Onde $p_k$ é o $k$é o primeiro. Desde que sabemos$S$ não pode ter limitado a complexidade de Kolmogorov (as diferenças principais ficam arbitrariamente grandes), isso significa $L$ não pode ser regular.

Outro exemplo muito fácil é o seguinte: use a complexidade de Kolmogorov para provar que $L_{ww} = \{ww \mid w \in \{0,1\}^* \}$ não é regular.

Dou-lhe uma prova muito informal, esperando que possa ajudá-lo a entender melhor o papel da complexidade de Kolmogorov.

A ideia principal é a seguinte: um autômato finito $D$ (que reconhece um idioma normal $L_D$) possui uma quantidade finita de "memória"; então rodando em uma string de entrada$x = yz$ quando "processou" a primeira parte da entrada $y$ a associação de $x$ no $L_D$ depende apenas do seu estado atual e da segunda parte da entrada $z$.

Agora suponha que $L_{ww}$é regular; então existe um DFA$D_{ww}$ que reconhece isso.

Deixei $y$ ser uma sequência incompressível de comprimento $|y| = n \gg |D|$

Para todas as entradas $x=y z$, no final da primeira parte $y$, o DFA $D_{ww}$ estará claramente no mesmo estado $q_i$e, por hipótese, ele aceitará apenas se a parte restante $z$ é tal que $x = y z$ pode ser dividido em duas partes iguais (ou seja, $yz = ww$); por exemplo

 Let y = 10110
       y   z
 x = 10110 0  >> rejected
 x = 10110 1  >> accepted  (w=101, |y|>|z|)
 x = 10110 00 >> rejected
 x = 10110 01 >> rejected
 ....
 x = 10110 10110 >> accepted  (w=10110,  |y|=|z| !!!)
 ....
 x = 10110 1101101 >> accepted (w=101101, |z|<|y|

Mas é importante notar que existe apenas uma string $z$ de comprimento $|y|$ isso é aceito ($z = y$)

Então, dada a descrição de $D_{ww}$, o Estado $q_i$ no fim de $y$e o comprimento $|y|$ podemos simular o comportamento de $D_{ww}$ em todo o $2^{|y|}$ cordas e veja qual delas aceita ... mas aceita exatamente $z=y$.

Então, com um programa de tamanho $\ell = |D_{ww}| + \log{i} + \log y + c$

($|D_{ww}|$ é necessário espaço para armazenar a descrição de $D_{ww}$, $\log i$ espaço para guardar $q_i$, $\log y$ espaço para armazenar o comprimento de $y$, $c$ é necessário espaço para as instruções que simulam o DFA)

podemos "reconstruir" a corda $y$; mas para grande o suficiente$y$ temos $\ell < |y|$ o que é uma contradição porque $y$ é incompressível.