The passing of a rational expression to a nondeterministic finite automaton (Q1280234): Difference between revisions

Let but de cet article est de présenter un nouvel algorithme séquentiel en temps \(\Omega(n^2)\) pour la conversion d'une expression rationnelle simple, ayant \(n\) occurrences de symboles, en son automate de Glushkov (automate d'états finis, non nécessairement déterministe, sans \(\varepsilon\)-transitions, ayant \(n+1\) états, représenté par sa table de transitions). Les algorithmes produits par A. Brüggemann-Klein et par C. H. Chang et R. Paige évaluent les opérations de fermeture (étoile de Kleene) en unions (d'ensembles de transitions) disjointes, selon les deux variantes suivantes: \[ \delta\uplus A= (\delta\setminus(\delta\cap A))\cup A= \delta\cup(A\setminus(\delta\cap A)). \] A. Brüggemann-Klein introduit la notion de ``Star Normal form'' (forme normale de fermeture) et calcule ``au plus tard'' les transitions induites par un opérateur de fermeture. Chang et Paige évaluent de façon paresseuse la fonction de transitions avec une structure de données appelée CNNFA (Compressed Normal NFA) à base de forêts d'états. À complexité temporelle égale, notre algorithme est inťeressant pour les raisons suivantes. Tout d'abord il repose sur une représentation originale de l'automate de Glushkov, basée sur des forêts d'étas différentes de celles de Chang et Paige. Le passage de l'expression à cette représentation de l'automate est en temps linéaire par rapport au nombre d'occurrences de lettres \(n\); la traduction en table de transitions est en \(\Omega(n^2)\). Lévaluation des opérations de fermeture sur cette représentation est réalisée en unions disjointes par un algorithme récursif original en temps linéaire par rapport à \(n\). Par ailleurs, cet algorithme séquentiel se prête bien à la parallélisation dans le modèle PRAM.