Trouver le plus petit DFA qui sépare deux mots sans utiliser la recherche par force brute?

23

Étant donné deux chaînes x et y, je veux créer une taille minimale DFA qui accepte x et rejette y. Une façon de le faire est la recherche par force brute. Vous énumérez les DFA en commençant par le plus petit. Vous essayez chaque DFA jusqu'à ce que vous en trouviez un qui accepte x et rejette y.

Je veux savoir s'il existe un autre moyen connu de trouver ou de créer un DFA de taille minimale qui accepte x et rejette y. En d'autres termes, pouvons-nous battre la recherche par force brute?

Plus de détails:

(1) Je veux vraiment qu'un algorithme trouve une taille minimale DFA, pas une taille DFA proche de la taille minimale.

(2) Je ne veux pas seulement savoir quelle est la taille du DFA minimum.

(3) Ici, je ne me concentre que sur le cas où vous avez deux chaînes x et y.


Modifier :

Informations supplémentaires pour le lecteur intéressé:

Supposons que x et y sont des chaînes binaires de longueur au plus n . C'est un résultat connu qu'il existe un DFA qui accepte x et rejette y avec au plus n états. Notez qu'il y a environnn DFA avec un alphabet binaire et au plusn états. Par conséquent, l'approche par force brute ne nous obligerait pas à énumérer plus denn DFA. Il s'ensuit que l'approche par force brute ne pouvait pas prendre beaucoup plus quenn temps.

Diapositives que j'ai trouvées utiles: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf

Michael Wehar
la source
2
@ AndrásSalamon Est-il toujours NP-complet si les ensembles à distinguer se composent chacun d'une seule chaîne? Il me semble que cela devrait être raisonnablement réalisable.
mhum
6
@mhum le problème qu'il existe de nombreuses langues régulières différentes qui séparent les deux chaînes - la minimisation DFA trouvera le meilleur automate pour l'une de ces langues mais ne fera rien pour le comparer aux automates pour les autres langues de séparation.
David Eppstein
4
Si et y sont de longueurs différentes, avec la plus grande de longueur n , il est facile de trouver rapidement un DFA avec des états O ( log n ) qui les sépare: utilisez simplement un cycle de longueur p , où p ne se divise pas | x | - | y | . Trouvez p en essayant 2 , 3 , 5 , dans l'ordre jusqu'à ce que vous trouviez le p appropriéxynO(logn)pp|x||y|p2,3,5,p . Si et y ont la même longueur, alors le Oxyconstruction de Robson, dans un article de 1996, donne une machine simple que l'on peut trouver par une recherche de tailleO(n). Aucune construction n'est garantie comme étant la plus petite DFA. O(n)O(n)
Jeffrey Shallit
3
Les notes de Shallit, liées ci-dessus, incluent l'observation utile que le pire cas pour le problème de séparation est lorsque l'alphabet est binaire: il est toujours possible de partitionner des alphabets plus grands en deux sous-ensembles qui distinguent toujours les deux mots d'entrée et de rechercher un automate binaire qui traite lettres dans un sous-ensemble comme 0 et lettres dans l'autre sous-ensemble comme 1. Mais pour rechercher l'automate de séparation minimum, cela ne semble pas aider, car vous pourriez être en mesure d'utiliser les informations supplémentaires de l'alphabet d'origine pour faire mieux que vous ne le pourriez avec un mappage vers un alphabet binaire.
David Eppstein
3
un cas particulier de cette autre question récente où les tailles d'entrée et de sortie sont égales à 1. des automates finis minimaux donnés en mots et en mots . cette réponse énumère de la littérature d'apprentissage, y compris des heuristiques.
vzn

Réponses:

9

Si je devais le faire dans la pratique, j'utiliserais un solveur SAT.

La question de savoir s'il existe un DFA avec états qui accepte x et rejette y peut être facilement exprimée comme une instance SAT. Par exemple, une façon consiste à avoir 2 k 2 variables booléennes: z s , b , t est vrai si le DFA passe de l'état s à l'état t sur le bit d'entrée b . Ajoutez ensuite quelques clauses pour faire en sorte qu'il s'agisse d'un DFA, et quelques variables et clauses pour faire en sorte qu'il accepte x et rejette y .kxy2k2zs,b,tstbxy

Utilisez maintenant la recherche binaire sur pour trouver le plus petit k tel qu'il existe un DFA de ce type. Sur la base de ce que j'ai lu dans des articles sur un problème connexe, je m'attendrais à ce que cela soit raisonnablement efficace dans la pratique.kk


D'autres codages de cela comme SAT sont possibles. Par exemple, nous pouvons utiliser un encodage de trace:

  • Si est de longueur m , vous pouvez ajouter m lg k variables booléennes: soit s 0 , s 1 , , s m soit la séquence d'états traversés sur l'entrée x , et représenter chaque s i à l' aide de lg k variables booléennes.xmmlgks0,s1,,smxsilgk

  • Maintenant, pour chaque tel que x i = x j , vous avez la contrainte que s i - 1 = s j - 1i,jxi=xj .si1=sj1si=sj

  • Ensuite, étendez ceci pour gérer : soit t 0 , , t n la séquence d'états traversés sur l'entrée y , et représentez chaque t j à l' aide de lg k variables booléennes. Pour chaque i , j tel que y i = y j , ajoutez la contrainte que t i - 1 = t j - 1yt0,,tnytjlgki,jyi=yj .ti1=tj1ti=tj

  • De même, pour chaque tel que x i = y j , ajoutez la contrainte que s i - 1 = t j - 1i,jxi=yj .si1=tj1si=tj

  • Les deux traces doivent commencer à partir du même point de départ, donc ajoutez l'exigence que (WLOG vous pouvez exiger s 0 = t 0 = 0 ).s0=t0s0=t0=0

  • Pour garantir que le DFA n'utilise que états, exigez que 0 s i < k et 0 t j < k pour tout i , j .k0si<k0tj<ki,j

  • Enfin, pour coder l'exigence selon laquelle est accepté et y est rejeté, il faut que s mt n .xysmtn

Toutes ces exigences peuvent être codées en tant que clauses SAT.

Comme précédemment, vous utiliseriez la recherche binaire sur pour trouver le plus petit k pour lequel un tel DFA existe.kk

DW
la source
3
notez que cela sera en fait supérieur à la recherche par force brute s'il y a certaines symétries dans le problème et qu'elles sont reconnues par le solveur, mais il peut actuellement être difficile d'identifier / d'isoler celles-ci (que ce soit pour l'homme ou la machine). il existe également des "technologies" plus récentes / apparentées de théories de module de satisfiabilité et de programmation d'ensembles de réponses dont certaines ont des prédicats de graphes "intégrés" ou peuvent prendre en charge leurs définitions.
vzn