Langue régulière non acceptée par DFA ayant au plus trois états

Décrivez une langue régulière qui ne peut être acceptée par aucun DFA qui ne comporte que trois états.

Je ne sais pas trop par où commencer et je me demandais si quelqu'un pourrait me donner quelques conseils ou astuces. Je comprends que le lemme de pompage peut être utilisé pour prouver qu'une langue n'est pas régulière, mais dans ce cas, il doit s'agir d'une langue régulière. Si quelqu'un a des idées, ce serait apprécié.

Le lemme de pompage peut être déclaré en tenant compte du nombre d'états dans le DFA. Chaque langue acceptée par un DFA avec p états satisfait le lemme de pompage suivant:$L$$p$

Chaque mot d'une longueur d'au moins p peut être décomposé en w = x y z , où | x y | ≤ p et | y | ≥ 1 , tel que x y i z ∈ L pour tout i ≥ 0 .$w$$p$$w=xyz$$|xy| \leq p$$|y| \geq 1$$xy^iz \in L$$i \geq 0$

Vous pouvez utiliser cette caractérisation pour prouver que le langage nécessite p + 1 états.$\{0^p\}$$p+1$

Une autre méthode consiste à utiliser le théorème de Myhill - Nerode. Deux mots sont inéquivalents (par rapport à une langue L ) si pour un mot z , soit x z ∈ L et y z ∉ L ou inversement . Le théorème de Myhill - Nerode déclare que s'il y a p mots inéquivalents par paire, alors chaque DFA pour L a au moins p états. Pour l'exemple L = { 0 p } , vous pouvez trouver p + $x,y$$L$$z$$xz \in L$$yz \notin L$$p$$L$$p$$L = \{0^p\}$$p+1$ mots inéquivalents par paire, à savoir .$\epsilon,0,\ldots,0^p$

La réponse de Yuval est excellente. Une formulation plus simple de ce qu'il a décrit est que les automates finis ne peuvent pas compter arbitrairement élevés, et la quantité à laquelle ils peuvent compter est limitée par les états numériques dans les automates. Plus précisément, pour qu'un automate compte pour , il a besoin de p + 1 états (un état serait 0 ).$p$$p+1$$0$

C'est, en substance, l'idée derrière le lemme de pompage: si une chaîne est vraiment longue, les automates finis doivent "oublier" la hauteur de son comptage et recommencer à zéro, ce qui vous permet de répéter une section encore et encore sans s'en soucier .

Par conséquent, tout langage régulier qui nécessite de compter jusqu'à 3 pour valider un mot qu'il contient ne peut pas être décrit par un automate fini de taille 3.

Pouvez-vous penser à une telle langue? (Votre professeur peut également s'attendre à ce que vous prouviez cet argument de comptage, bien que dans mon programme, cette compréhension du lemme de pompage soit tenue pour acquise)

Il existe un algorithme pour minimiser les DFA. Choisissez simplement une langue qui a un DFA minimal de 4 (ou plus) états. Tout ce qui a une longueur minimale de 3 symboles fera l'affaire, c'est-à-dire la langue de l'expression régulière , ou (encore plus simple) a 3 . Pour voir pourquoi, jetez un œil à la preuve du lemme de pompage pour les langues régulières.$a^3 a^*$$a^3$

une autre idée, la diagonalisation ! énumérer tous les DFA à 3 états ou moins, prendre l'union de tous, puis prendre le complément. il s'agit d'un DFA par fermeture régulière des opérations linguistiques. cela pourrait être construit via un algorithme, mais la question ne demande qu'une description .