Preuve de non-régularité, basée sur la complexité de Kolmogorov

En classe, notre professeur nous a montré 3 méthodes pour prouver la non-régularité:

1. Théorème de Myhill – Nerode
2. Pompage du lemme pour les langues régulières
3. Preuve de non-régularité, basée sur la complexité de Kolmogorov

Maintenant les deux premiers, le théorème de Myhill-Nerode et le lemme de pompage, j'ai bien compris et j'ai également pu faire les exercices des deux premières méthodes. Mais je n'ai pas compris le troisième. La définition de la troisième méthode est la suivante:

Laisser $\ L \subseteq (\Sigma_{bool})^*$être une langue régulière. Laisser$\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \}$ pour chaque$\ x \in (\Sigma_{bool})^*$. Il existe alors une constante$\ c$, de telle sorte que pour tous $\ x,y \in (\Sigma_{bool})^*$

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

si $\ y$ est le nième mot de la langue $\ L_x$.

Maintenant, je ne comprends pas comment utiliser ce théorème pour prouver qu'un langage n'est pas régulier, je ne comprends pas vraiment le concept. Nous avons utilisé la complexité de kolmogorov avant pour déterminer la longueur du programme informatique le plus court d'un objet. Comment prouver la non-régularité avec ce théorème? Et quelle est la pensée derrière cela?

Merci beaucoup!

À ma connaissance, ce n'est pas une des approches "classiques" utilisées pour caractériser les langues régulières.

Cette approche est discutée dans «Une nouvelle approche de la théorie du langage formel par la complexité de Kolmogorov» , par Ming Li et Paul MB Vitanyi (voir la section 3.1).

Ils donnent plusieurs exemples où l'on peut utiliser l'énoncé que vous avez mentionné au lieu d'utiliser le lemme de pompage. Par exemple, prouver la non-régularité de$L$ où

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

Étant donné certains $x\in\Sigma^*$, $L_x=\left\{y| \hspace{1mm} xy=1^p \land \text{p is prime}\right\}$. Choisissons$x=1^{p'}$ où $p'$ est le $k$'e premier. Laisser$y_1$ être le premier mot $L_x$. Évidemment,$y_1=1^{p-p'}$ où $p$ est le $k+1$premier. Selon la déclaration que vous avez mentionnée,$K(y_1)\le c$ ($n=1$), pour une constante $c$ en fonction uniquement de $L$ (voir papier).

Puisque cela vaut pour tous $x$, nous pouvons limiter la complexité de Kolmogorov de tous les éléments $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\}$ par la même constante $c$. Cependant, nous avons vu que$S$ se compose en fait de différences entre des nombres premiers consécutifs, à savoir $S=\left\{1^{p_{k+1}-p_k} | k\ge 1\right\}$ où $p_k$ est le $k$'e premier. Puisque nous savons$S$ ne peut pas avoir limité la complexité de Kolmogorov (les différences principales deviennent arbitrairement grandes), cela signifie $L$ ne peut pas être régulier.

Un autre exemple très simple est le suivant: utilisez la complexité de Kolmogorov pour prouver que $L_{ww} = \{ww \mid w \in \{0,1\}^* \}$ n'est pas régulier.

Je vous donne une preuve très informelle en espérant que cela peut vous aider à mieux comprendre le rôle de la complexité de Kolmogorov.

L'idée clé est la suivante: des automates finis $D$ (qui reconnaît une langue régulière $L_D$) a une quantité finie de «mémoire»; donc en cours d'exécution sur une chaîne d'entrée$x = yz$ quand il a "traité" la première partie de l'entrée $y$ l'appartenance à $x$ dans $L_D$ dépend uniquement de son état actuel et de la deuxième partie de l'entrée $z$.

Supposons maintenant que $L_{ww}$est régulier; puis il y a un DFA$D_{ww}$ qui le reconnaît.

Laisser $y$ être une chaîne de longueur incompressible $|y| = n \gg |D|$

Pour toutes les entrées $x=y z$, à la fin de la première partie $y$, le DFA $D_{ww}$ sera clairement sur le même état $q_i$, et par hypothèse, il n'acceptera que si la partie restante $z$ est telle que $x = y z$ peut être divisé en deux moitiés égales (c.-à-d. $yz = ww$); par exemple

 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|

Mais il est important de noter qu'il n'y a qu'une seule chaîne $z$ de longueur $|y|$ qui est accepté ($z = y$).

Donc, étant donné la description de $D_{ww}$, l'état $q_i$ au bout du $y$et la longueur $|y|$ nous pouvons simuler le comportement de $D_{ww}$ sur tous les $2^{|y|}$ cordes et voir lequel d'entre eux il accepte ... mais il accepte exactement $z=y$.

Donc avec un programme de taille $\ell = |D_{ww}| + \log{i} + \log y + c$

($|D_{ww}|$ un espace est nécessaire pour stocker la description de $D_{ww}$, $\log i$ espace pour stocker $q_i$, $\log y$ espace pour stocker la longueur de $y$, $c$ de l'espace est nécessaire pour les instructions simulant le DFA)

on peut "reconstruire" la chaîne $y$; mais pour assez grand$y$ on a $\ell < |y|$ ce qui est une contradiction parce que $y$ est incompressible.