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

8

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(Σbool)être une langue régulière. Laisser Lx={y(Σbool)|xyL} pour chaque x(Σbool). Il existe alors une constante c, de telle sorte que pour tous  x,y(Σbool)

 K(y)log2(n+1)+c

si  y est le nième mot de la langue  Lx.

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!

gammaALpha
la source

Réponses:

8

À 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é deL

L={1p|p is prime}.

Étant donné certains xΣ, Lx={y|xy=1pp is prime}. Choisissonsx=1pp est le k'e premier. Laissery1 être le premier mot Lx. Évidemment,y1=1ppp est le k+1premier. Selon la déclaration que vous avez mentionnée,K(y1)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={y1x|x=1p for prime p y1x is the first string in Lx} par la même constante c. Cependant, nous avons vu queS se compose en fait de différences entre des nombres premiers consécutifs, à savoir S={1pk+1pk|k1}pk est le k'e premier. Puisque nous savonsS 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.

Ariel
la source
2
Je ne connaissais pas cette technique. Vous sentez-vous prêt à ajouter une réponse à notre question de référence ?
Raphael
1
Oui, je peux en ajouter un plus tard. Je dois admettre que je n'étais pas non plus au courant de cette technique, je suis juste tombé sur ce document après avoir consulté la question d'op. Je ne sais pas à quel point cette technique s'est avérée populaire (par rapport à d'autres méthodes). L'article d'Arxiv a en fait été publié dans SIAM en 1995, il n'est donc pas aussi nouveau que je le pensais au départ (approche intéressante et originale).
Ariel
Merci beaucoup pour l'effort et l'exemple. Pourriez-vous m'expliquer pourquoi 1pp est le premier mot  Lx? p est le k-ème premier et p 'est le k + 1 premier, alors ne devrions-nous pas dire que y1=1pp? Et si j'ai bien compris, pp 'n'a pas besoin d'être nécessairement premier, c'est pourquoi nous choisissons cela?
gammaALpha
1
Le préfixe est x=1p, le premier mot de L avec préfixe x est alors y1x=1pp tel que p est le prochain premier, donc xy1x=1p+(pp)=1p. Nous choisissonsx de cette façon parce que cela nous permet de limiter la complexité de Kolmogorov de tous ces y1xpar une constante. Étant donné que les différences principales peuvent devenir arbitrairement grandes, l'ensemble de toutes ces différencesy1xest infini (il ne peut donc pas avoir de complexité limitée). J'ai ajouté une réponse à la question de référence, elle contient plus d'informations que vous pourriez trouver utiles et un autre exemple.
Ariel
3

Un autre exemple très simple est le suivant: utilisez la complexité de Kolmogorov pour prouver que Lww={www{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 LD) a une quantité finie de «mémoire»; donc en cours d'exécution sur une chaîne d'entréex=yz quand il a "traité" la première partie de l'entrée y l'appartenance à x dans LD dépend uniquement de son état actuel et de la deuxième partie de l'entrée z.

Supposons maintenant que Lwwest régulier; puis il y a un DFADww qui le reconnaît.

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

Pour toutes les entrées x=yz, à la fin de la première partie y, le DFA Dww sera clairement sur le même état qi, et par hypothèse, il n'acceptera que si la partie restante z est telle que x=yz 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 Dww, l'état qi au bout du yet la longueur |y| nous pouvons simuler le comportement de Dww 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 =|Dww|+logi+logy+c

(|Dww| un espace est nécessaire pour stocker la description de Dww, logi espace pour stocker qi, logy 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 grandy on a <|y| ce qui est une contradiction parce que y est incompressible.

Vor
la source
Je ne connaissais pas cette technique. Vous sentez-vous prêt à ajouter une réponse à notre question de référence ?
Raphael