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

10

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é.

zic10
la source

Réponses:

17

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:Lp

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 .wpw=Xyz|Xy|p|y|1XyjezLje0

Vous pouvez utiliser cette caractérisation pour prouver que le langage nécessite p + 1 états.{0p}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 + 1X,yLzXzLyzLpLpL={0p}p+1 mots inéquivalents par paire, à savoir .ϵ,0,,0p

Yuval Filmus
la source
oui zpeut être ^vide, mais je pense que vous avez une faute de frappe dans votre citation. xy^i ∈ L devrait êtrexy^i z ∈ L
Grijesh Chauhan
12

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 ).pp+10

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)

Alexis Beingessner
la source
Bonne réponse: cela explique beaucoup de choses sans donner la solution à ce qui ressemble à un exercice de devoirs. Bienvenue en informatique !
David Richerby
1

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.une3uneune3

vonbrand
la source
-2

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 .

vzn
la source
n
nn+1
@Yuval à droite. pense que cette idée peut fonctionner mais peut-être que les détails ne sont pas exactement exacts, les détails sont difficiles, je suppose que cela pourrait être quelque part dans la littérature, mais je ne l'ai pas vue
vzn