Une condition suffisante et nécessaire sur la régularité d'une langue

laquelle des déclarations suivantes est correcte?

1. des conditions suffisantes et nécessaires de régularité d'une langue existent mais ne sont pas encore découvertes.

2. Il n'y a pas de condition suffisante et nécessaire sur la régularité d'une langue.

3. Le pompage du lemme est une condition nécessaire à la non-régularité d'une langue.

4. Le pompage du lemme est une condition suffisante pour la non-régularité d'une langue.

Je sais que # (4) est correct et # (3) est faux parce que "l'inverse de cette affirmation n'est pas vrai: un langage qui remplit ces conditions peut encore être non régulier", mais que peut-on dire à propos de (1) et (2)?

Voici quelques conditions nécessaires et suffisantes pour qu'une langue soit régulière.

Théorème. Soit . Les conditions suivantes sont les mêmes:$L\subseteq\Sigma^*$

• $L$ est généré par une expression régulière (c'est-à-dire la définition du langage régulier).
• $L$ est reconnu par un automate fini non déterministe ( Kleene ).
• $L$ est reconnu par un automate fini non déterministe sans transitions .$\varepsilon$
• $L$ est reconnu par un automate fini déterministe ( Scott et Rabin ).
• $L$ est généré par une grammaire , où est un sous-ensemble fini de ( Frazier et Page ).$(N,\Sigma,P,S)$$N$$\Sigma^*$
• $L$ est généré par une grammaire sans contexte régulière gauche (resp. Droite).
• L'indice de la relation est fini (Anil Nerode, Linear automon transformations , 1958). Ceci est largement (et à tort) connu sous le nom de théorème de Myhill-Nerode. est la relation utilisée pour construire le DFA minimal d'un langage régulier.$\equiv_L$$\equiv_L$
• L'indice de la relation Myhill est fini (John Myhill, Finite Automata and the Representation of Events , 1957). est la relation utilisée pour construire le monoïde syntaxique d'un langage arbitraire.∼ $\sim_L$$\sim_L$
• Le monoïde syntaxique de est fini (conséquence du résultat de Myhill). Nous notons ici que le monoïde syntaxique, en plus d'être défini en utilisant la relation ∼ L , peut être défini comme un monoïde minimal (en taille) qui reconnaît L comme une image préalable d'un homomorphisme.$L$$\sim_L$$L$
• peut être reconnu par une machine de Turing en lecture seule (trivial).$L$
• peut être défini par une formule en logique monadique de second ordre sur des chaînes (Büchi).$L$

Si une langue ne satisfait pas aux conditions du lemme de pompage pour les langues régulières , elle n'est pas régulière. Cela signifie que le pompage du lemme est une condition suffisante pour la non-régularité d'une langue.

En résumé, les déclarations 1, 2 et 3 sont fausses, tandis que la déclaration 4 est vraie, comme vous l'avez mentionné.

Il suffit (et nécessaire) de démontrer l'existence d'un DFA, d'un NFA ou d'une expression régulière pour prouver qu'un langage est régulier, ce qui réfute (1) et (2). Pour montrer qu'une langue n'est pas régulière, il est nécessaire de montrer qu'il n'existe pas de DFA, NFA ou d'expression régulière.

Le lemme de pompage est un outil utile pour montrer (éventuellement par contradiction) qu'une langue n'est pas régulière, en montrant qu'il n'existe pas de DFA.

La condition «il existe une expression régulière qui génère exactement » est une condition nécessaire et suffisante pour la régularité d'un langage L , par grâce d'être sa définition.$L$$L$

Cette condition ne permet cependant pas de prouver facilement la non-régularité d'une langue. Je ne connais aucune condition facile à vérifier qui prouve toujours la non-régularité d'une langue non régulière.

Il existe deux autres `` tests '' qui peuvent prouver la non-régularité d'une langue (bien qu'ils ne fonctionnent pas): vous pouvez essayer de donner une langue régulière de telle sorte que leur union / intersection / différence / concaténation / quotient soit non régulière ( il y a plus d'opérations comme celle-ci), et vous pouvez essayer de compter le nombre de mots qu'il génère et vérifier s'il contredit l'expression du nombre de mots dans une langue régulière (comme on peut le trouver sur la page Wikipedia que vous avez liée).

Il y a cette merveilleuse connexion entre la théorie formelle du langage et les séries de pouvoirs formels prouvées par Chomsky et Schützenberger [CS63] . Sous la forme trouvée dans [SS78] Chap. II, Théorème 5.1

$L$$\mathbb{K}$$\mathrm{char}(L)$$\mathbb{K}$

$\mathrm{char}(L)$

[SS78] Arto Salomaa et Matti Soittola. Aspects théoriques des automates de la série Power formelle. Springer-Verlag, New York, 1978.

[CS63] Noam Chomsky et Marcel P. Schützenberger. La théorie algébrique des langages sans contexte. Dans P. Braffort et D. Hirschberg, éditeurs, Programmation informatique et langages formels, pages 118-161. Hollande du Nord, 1963.

$I_{L}$$x$$y$$x I_{L} y$

1. $z_{x}$$xz_{x} \in L$$yz_{x} \in L$
2. $z_{y}$$yz_{y} \in L$$xz_{y} \in L$

$I_{L}$$L$

$I_{L}$