Quels algorithmes existent pour construire un DFA qui reconnaît le langage décrit par une expression régulière donnée?

11

Tous mes manuels utilisent le même algorithme pour produire un DFA avec une expression régulière: créez d'abord un NFA qui reconnaît le langage de l'expression régulière, puis, en utilisant la construction du sous-ensemble (aka "powerset"), convertissez le NFA en un DFA équivalent ( en minimisant éventuellement le DFA). J'ai également entendu une fois un professeur faire allusion à l'existence d'autres algorithmes. Quelqu'un en connaît-il? Peut-être celui qui passe directement de l'expression régulière à un DFA sans le NFA intermédiaire?

BlueBomber
la source
Bienvenue sur cstheory, un site de questions / réponses pour les questions de recherche en informatique théorique (TCS). Votre question ne semble pas être une question de niveau recherche dans TCS. Veuillez consulter la FAQ pour plus d'informations sur ce que cela signifie. Votre question pourrait convenir à l' informatique qui a une portée plus large.
Kaveh
1
pourquoi utilisez-vous toujours ce modèle de commentaire? Apparemment, il y en a au moins 5 qui ne sont pas d'accord avec vous. Je vous suggère de donner une chance à ces questions.
AJed
@AJed, je n'utilise pas toujours ce commentaire. Je l'utilise lorsqu'une question me semble hors sujet mais peut convenir à l' informatique . Les votes positifs ne signifient pas qu'une question est sur le sujet, et celle-ci ne me semble pas être une question de recherche, donc je pense que le commentaire est approprié. (Le fait que quelqu'un puisse écrire une réponse de niveau recherche à une question ne rend pas la question de niveau recherche.) Ps: Je pense que cette discussion convient mieux à Meta Computer Science théorique .
Kaveh

Réponses:

13

Il existe différents algorithmes pour convertir des expressions régulières en automates finis. Vous pouvez passer directement d'expressions régulières aux DFA sans construire d'autre automate en effectuant implicitement la construction du sous-ensemble lors de la génération de l'automate. Une autre option pour obtenir directement des automates déterministes est d'utiliser la méthode des dérivés.

Vérifier si une expression régulière représente la langue contenant toutes les chaînes est un problème complet de PSPACE (voir cette réponse pour une référence). Vérifier si un DFA accepte que le langage puisse être fait en temps polynomial, donc si vous passez directement d'une expression régulière à un DFA, il y aura une explosion quelque part.

Ma compréhension de la littérature est que nous pouvons choisir des traductions qui nous permettent de localiser l'explosion. Cela signifie qu'il existe différentes façons de passer d'une expression régulière à un automate fini, et les méthodes linéaires ou polynomiales sont préférées. Habituellement, les coûts exponentiels sont poussés dans la détermination des automates.

Il y a eu beaucoup de travail pour identifier les sous-familles d'expressions régulières à partir desquelles nous pouvons générer efficacement des DFA. Cette ligne de travail dépend de la traduction que vous utilisez. En d'autres termes, vous corrigez un mappage des expressions régulières vers les NFA et essayez de caractériser les expressions régulières mappées vers les DFA.

La construction standard d'automates à partir d'expressions régulières n'est pas la construction préférée dans un tel travail. Les constructions de choix produisent des automates qui ressemblent étroitement à la structure de l'expression régulière. Ces constructions utilisent la notion de dérivée d'une expression régulière.

Dérivés d'expressions régulières , JA Brzozowski. 1964.

srara

Dérivés partiels d'expressions régulières et de constructions d'automates finis , V. Antimirov. 1995.

Si vous pensez à un état d'un automate comme une représentation de toutes les chaînes acceptées à partir de cet état, les dérivées (partielles) vous permettent de traiter les expressions régulières comme des états . Contraste avec la construction de manuel standard qui traite intuitivement les expressions régulières comme des automates, pas des états.

Des expressions régulières aux automates déterministes , G. Berry et R. Sethi, 1986.

La correspondance entre les expressions régulières et les états d'un automate et du déterminisme est explicitement discutée par Berry et Sethi, qui combinent la notion de dérivés de Brzozowski avec l'idée de distinguer les occurrences du même symbole pour donner une traduction syntaxique des expressions régulières en finies. automates.

One-Unambiguous Regular Languages , A. Brüggemann-Klein et Derick Wood, 1998.

Cet article s'appuie sur des travaux antérieurs de Brüggemann-Klein et étudie des cas dans lesquels vous pouvez utiliser des dérivés pour générer des DFA en temps polynomial. Il y a une grande quantité de travail suite à ce document. Il était important du point de vue des technologies Web, car les expressions régulières pouvant être manipulées efficacement (c'est-à-dire correspondant aux DFA) étaient importantes pour le traitement de SGML et XML.

De nombreux travaux ont été consacrés à l'étude d'autres cas particuliers d'expressions régulières déterministes. Un article très récent étudiant quand certains de ces problèmes peuvent être résolus en temps linéaire date de 2012.

Expressions régulières déterministes en temps linéaire , Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012.

Vijay D
la source
5
Vous avez déjà mentionné les dérivés dans votre réponse, vous devez donc également ajouter JA Brzozowski: Derivatives of regular expressions, Journal of the ACM 11 (4): 481–494 (1964), car il donne un algorithme direct pour convertir les regexps en DFA. .
Neel Krishnaswami
3
J'en ai débattu. Mais les trois articles ci-dessus s'appuient directement sur ce résultat, j'ai donc pensé qu'il n'y avait aucune raison de le mentionner. Le papier Brueggeman-Klein et Wood est également plein d'exemples. Si je mentionne Brzozowski, je pense qu'Antimirov devrait également être mentionné. Je voulais éviter une enquête, mais je devrais peut-être simplement y aller. Que dis-tu?
Vijay D
5
Si vous avez le temps et l'énergie, je pense que des réponses de type enquête assez longues sont très appropriées ici.
David Eppstein
1
@VijayD: oui, je suis d'accord avec David. Les réponses courtes sont bonnes, mais si vous avez l'énergie, il est agréable de donner une réponse complète.
Neel Krishnaswami