Un automate fini non déterministe (NDFA) peut-il être converti efficacement en automate fini déterministe (DFA) dans un espace / temps sous-exponentiel?

16

Il y a vingt ans, j'ai construit un package d'expressions régulières qui comprenait des conversions d'expressions régulières vers une machine à états finis (DFA) et pris en charge une multitude d'opérations d'expressions régulières fermées (Kleene star, concatenation, reverse, set operations, etc.). Je n'étais pas sûr des performances les plus défavorables de mon colis.

Un DFA a le même pouvoir expressif qu'un NDFA, car un NDFA à n états peut être converti trivialement en un DFA ayant 2 ^ n états. Cependant, existe-t-il des garanties de limite supérieure inférieures pour une telle conversion qui ne nécessitent pas une explosion exponentielle en état?

Je n'ai pas été en mesure de trouver des exemples d'expressions régulières ou NDFA se comportant mal, mais je n'ai pas passé beaucoup de temps à y penser. Je devine une expression régulière comme (((((e | A | B | C) * (e | D | E | F)) * (e | G | H | I)) * (e | J | K | L | M)) * qui mélange beaucoup d'alternances et les étoiles Kleene auraient un NDFA de taille linéaire mais un DFA expansif.

Wesner Moise
la source
Existe-t-il des restrictions sur la classe des NFA que vous souhaitez accepter comme entrée? Certaines restrictions conduisent à de meilleures limites supérieures.
András Salamon
pas un point très important, mais faut-il que ndfa soit son propre tag?
Lev Reyzin
Oui, il y a des restrictions. Les NFA sont construits directement à partir d'expressions régulières en les traitant comme des graphiques de transition généralisés. seas.upenn.edu/~cit596/notes/dave/regexp-nfa4.html
Wesner Moise

Réponses:

15

Il est connu que pour chaque paire de nombres naturels n,atels que n <= a <= 2^n, il existe un NDFA minimal avec des nétats dont le dfa minimal équivalent correspondant a des aétats (sur un alphabet à quatre lettres).

Voir l'article ici: explosions déterministes d'automates finis non déterministes minimaux sur un alphabet fixe .

Résumé de l'article:

Nous montrons que pour tous les entiers n et α tels que n ≤ α ≤ 2 ^ n, il existe un automate fini non déterministe minimal de n états avec un alphabet d'entrée à quatre lettres dont l'automate fini déterministe minimal équivalent a exactement un état. Il s'ensuit que dans le cas d'un alphabet à quatre lettres, il n'y a pas de "nombres magiques", c'est-à-dire les trous dans la hiérarchie. Cela améliore un résultat similaire obtenu par Geffert pour un alphabet croissant de taille n + 2 (Proc. 7e DCFS, Como, Italie, 23-37).

Donc, je suppose que la réponse à votre question est non.

Aryabhata
la source
la question demande un "algorithme" fonctionnant dans le temps et l'espace sous-exponentiels pour convertir le NFA.
Marcos Villagra
@Marcos: Si votre sortie est exponentielle, vous ne pouvez pas possiblement avoir un algorithme qui s'exécute en temps sous-exponentiel.
Aryabhata
1
Ceci est un résultat général. S'il existe des restrictions connues sur la classe des NFA d'entrée, il pourrait être possible de faire mieux.
András Salamon
@Andras: D'accord, mais étant donné que cela est probablement lié à la programmation (qui prendra en charge Kleen * etc.), je doute que l'ensemble d'entrée NFA soit limité à un sous-ensemble approprié.
Aryabhata
5
Ce résultat a été récemment renforcé pour utiliser un alphabet à trois lettres, et les constructions sont un peu plus simples: portal.acm.org/…
13

L'exemple classique d'un langage avec une séparation exponentielle entre la taille DFA et la taille NFA est le langage fini suivant: des chaînes binaires de longueur exactement 2n dans lesquelles la première moitié n'est pas égale à la seconde moitié. Un NFA devinerait un indice i dans lequel la première et la seconde moitié sont en désaccord. Une limite inférieure pour un DFA découle de la complexité de la communication, par exemple.

Noam
la source
8

Le DFA minimum correspondant à un NFA a 2 ^ n états dans le pire des cas, vous ne pouvez donc rien garantir. Sans avoir un exemple constructif, le raisonnement est que dans un NFA, vous pouvez être dans n'importe quel sous-ensemble arbitraire d'états après avoir lu une certaine chaîne d'entrée, et chacun de ces sous-ensembles peut se comporter différemment lors de l'observation d'un caractère. Supposons une langue avec deux caractères dans l'alphabet (a et b) et un NFA N avec n états commençant par un état acceptant à s_0. Énumérer maintenant tous les sous-ensembles d'états de N, et construire la table de transition de telle sorte que l'observation "a" du sous-ensemble S_i vous amène au sous-ensemble S_i + 1 et l'observation de b vous amène au sous-ensemble S_i-1 (c'est faisable pour certaines énumérations, je pense que ). Maintenant, ces automates ont n états et acceptent des séquences de ma et de nb telles que mn = 0 mod 2 ^ | N |, et ne peut pas être exprimé avec un DFA qui a moins de 2 ^ | N | États (car il peut être nécessaire de parcourir tous les sous-ensembles d'états du NFA N).

Alexandre Passos
la source
Cela peut-il être transformé en un argument qui dit "si (une mauvaise chose) est évitée dans le NFA, alors le DFA a un nombre sous-exponentiel d'états"?
András Salamon
1
@ András, oui. "Si le non-déterminisme est évité dans le NFA, alors le DFA a un nombre subexponentiel d'états".
P Shved
2
Pavel, oui, évidemment. Existe-t-il une propriété non triviale pouvant être reconnue efficacement qui garantit également une explosion sous-exponentielle?
András Salamon