Conversion de RE en NFA

Question

Laquelle est la bonne façon d'afficher une union RE 0 + 1? J'ai vu cela de deux façons mais je pense que les deux sont corrects. Si les deux sont corrects pourquoi compliquer les choses?

Answer 1

Ils sont tous les deux corrects, comme vous l'avez dit. Le premier semble avoir été généré en utilisant un ensemble de règles standard - dans ce cas, c'est exagéré (et semble juste idiot), mais dans les cas plus compliqués, il est plus facile de suivre des règles simples que de tenir le tout dans votre tête et écrire un NFA équivalent à partir de zéro.

En général, un NFA peut être réécrit de sorte qu'il ait un seul état final (il n'y a évidemment qu'un seul état de départ).

Ensuite, deux NFA sous cette forme peuvent être combinés de telle sorte que le langage qu'ils acceptent lorsqu'ils sont combinés soit l'union des langages qu'ils acceptent individuellement - cela correspond au ou (+) dans une expression régulière. Pour combiner les NFA de cette manière, créez simplement un nouveau nœud qui agira comme état de départ et connectez-le avec des transitions ε aux états de départ des deux NFA. Ensuite, afin de terminer proprement le NFA dans un seul état final (afin que nous puissions utiliser ce NFA récursivement pour d'autres unions si nous le voulons), nous créons un nœud supplémentaire pour servir d'état final unifié et ε- connecter les anciens états finaux (qui perdent leur statut final). En utilisant les règles générales ci-dessus, il est facile d'arriver au premier diagramme (deux NFA unis ensemble, le premier correspondant 0, l'autre 1) - le second est facile à atteindre par le bon sens, car il est si simple regex ;-)

Answer 2

La première construction appartient à la classe de NFA avec e-moves, qui est une extension pour la classe NFA générale. e-moves vous donne la possibilité de faire des transitions sans avoir besoin d'une entrée. Pour la fonction de transition, il est important de calculer l'ensemble des états accessibles à partir d'un état donné en utilisant uniquement des transitions électroniques. De toute évidence, l'ajout de e-moves ne permet pas à NFA d'accepter des langages non-réguliers, donc il est équivalent aux NFA, puis aux DFA à la fin. NFA avec e-moves est utilisé par l'algorithme de construction de Thompson pour construire un automate à partir de n'importe quelle expression régulière. Il fournit une manière standard de construire un automate à partir d'expressions rationnelles quand c'est utile pour automatiser la construction.