Combien de DFA acceptent deux chaînes données?

28

Fixe un entier n et un alphabet Σ={0,1} . Définissez DFA(n) comme la collection de tous les automates à états finis sur n états avec l'état de départ 1. Nous considérons tous les DFA (pas seulement ceux connectés, minimaux ou non dégénérés); ainsi |DFA(n)|=n2n2n .

Considérons maintenant deux chaînes x,yΣ et définissons K(x,y) comme le nombre d'éléments de DFA(n) qui acceptent à la fois x et y .

Question: Quelle est la complexité du calcul de K(x,y) ?

Cette question a des implications pour l'apprentissage automatique .

Edit: Maintenant qu'il y a une récompense sur cette question, je suppose qu'un peu plus de précision dans la formulation est de mise. Pour n1 , soit DFA(n) la collection de n2n2n automates, comme défini ci-dessus. Pour x,y{0,1} , définissez Kn(x,y) comme le nombre d'automates dans DFA(n) qui acceptent les deux x ety . Question:Kn(x,y) peut-il être calculé en tempspoly(n,|x|,|y|) ?

Aryeh
la source
2
Si vous corrigez un DFA sans fixer les états finaux, alors il mappe x et y au même état, auquel cas la seule contrainte est que l'état doit être final, ou il les mappe à deux états différents, auquel cas la seule contrainte est qu'ils doivent tous deux être définitifs. Ainsi, je reformulerais votre problème comme "combien de DFA mappent x et y à différents états?".
a3nm
3
Aryeh, pouvez-vous expliquer le nombre n2n2n ? Je ne peux pas obtenir le facteur 2n . Ajouté: Oups, j'ai oublié de spécifier les états finaux. Quoi qu'il en soit, pour le bien des autres, voici comment se déroule le décompte. Pour chaque état, spécifiez où aller sur les entrées 0 et 1 ; cela représente n2n . Spécifiez l'ensemble des états finaux; c'est 2n .
Srivatsan Narayanan
2
En effet, je me fiche de ce qui arrive aux chaînes autres que et y . Je suppose que l'on a besoin d'un certain nombre de points pour commencer une prime? xy
Aryeh
4
Le plus petit automate qui accepte et y a un seul état, donc je ne pense pas que ce soit terriblement informatif ...xy
Aryeh
3
Voici une idée: il suffit de connaître le nombre de DFA à états qui se retrouvent dans le même état sur x et y . Soit ce nombre m et M le nombre total de DFA, c'est-à-dire M = n 2 n 2 n . Alors la réponse est 1nxymMM=n2n2n12m+14(Mm)mxyx=0ab=1bl0 a 1 b mmax{a,b}0a1bm

Réponses:

1

La question est donc assez brève mais très intéressante. Je suppose que l'entrée est en unaire et x et y en binaire (ou nous avons des problèmes, comme l'a souligné la réponse de Kai).nxy

Tout d'abord, si vous souhaitez connaître approximativement , vous pouvez simplement générer quelques DFA aléatoires et cela vous donnera (whp) une bonne approximation. (Je me demande si cette classe de complexité a un nom.)K(x,y)

Alors connaître semble précisément être un problème difficile. Comme indiqué dans les commentaires de a3_nm et Kaveh, la question revient à déterminer le nombre d'automates pour lesquels x et y passent au même état. Je dénoterai la probabilité qu'ils passent au même état par p .K(x,y)xyp

Mise à jour: Certaines des choses que j'ai écrites ici n'étaient pas vraies, maintenant je les ai corrigées.

Il est facile de voir que . Nous avons l'égalité, si x est tout 0 et y est tout zéro sauf pour son dernier bit, qui est un 1. Y a-t-il d'autres cas? Je ne sais pas. Si par exemple x est la chaîne vide et , alors .p1/nxyxp = n + 1y=00p=n+1(n1)n

Pour simplifier le problème, j'ai même commencé à penser à ce qui se passe si et sont unaires. Si les deux sont au moins et que leur différence est divisible par, alors . Existe-t-il une formule simple pour la version unaire?y n n ! p = 1xynn!p=1

domotorp
la source
J'ai clarifié le problème - un algorithme est souhaité (ou une réduction par rapport à un problème difficile connu). L'approximation d'échantillonnage est utilisée dans l'article où ce noyau est introduit: portal.acm.org/citation.cfm?id=1577108poly(n,|x|,|y|)
Aryeh
2
Quant à la version unaire: il n'y a que de nombreux automates unaires à états, je parierais donc qu'il existe un algorithme poly-temps pour calculer K n ( x , y ) dans ce cas. nKn(x,y)
Aryeh
En effet, vous avez absolument raison de dire que la version unaire est calculable. Je me demande encore à quel point la formule est simple pour un x et un y donnés.
domotorp
La réduction que vous avez utilisée est boguée: x et y peuvent être acceptés par les mêmes automates et se terminer dans des états complètement différents, en fait, ils ne peuvent partager que l'état de départ dans leurs chemins, ce qui est vrai pour toutes les chaînes.
amnn
@amnn: Cela fait trois ans que j'ai écrit ceci, mais le troisième paragraphe de ma réponse n'explique-t-il pas pourquoi je ne traite que de finir dans le même état?
domotorp
0

Je peux très bien manquer le point, mais vous avez déclaré que est fixe, donc tous les DFA de cette taille pourraient être considérés comme précalculés et stockés dans un format facilement simulable. Calculez K comme suit:nK

En entrée , yx , y Σ xyx,yΣ

  1. stocker et yxy
  2. initialiser le compteur à 0c0
  3. pour chacun de vos DFAn2n2n
  4. une. simulez-le sur les deux mots (cette étape est )O(|xy|)

    b. incrémenter si les deux cycles de simulation acceptentc

  5. sortie c

Au total, le calcul a une complexité linéaire. La réponse est assez différente pour .K(n,x,y)

Kai
la source
3
Il est clair que toutes les machines fonctionneront. Aryeh veut savoir s'il existe, peut-être, un algorithme de temps polynomial ou sinon un résultat de dureté.
Lev Reyzin
Strictement parlant, c'est le temps polynomial dans l'entrée, si n ne fait pas partie de l'entrée, c'est ce que Kai disait. Mais la question est clairement différente.
domotorp
4
Oh je vois. Je ne pense pas que c'est ce qu'il entend par «fixer ». Je pense que l'interprétation naturelle du problème est celle qui ne le banalise pas. n
Lev Reyzin
1
D'accord, merci d'avoir signalé l'échappatoire, Kai. Il a été corrigé :)
Aryeh