Comment convertir un NFA avec des cycles qui se chevauchent en une expression régulière?

11

Si je comprends bien, les NFA ont le même pouvoir expressif que les expressions régulières. Souvent, la lecture d'expressions régulières équivalentes dans NFA est facile: vous traduisez des cycles en étoiles, des jonctions comme alternatives, etc. Mais que faire dans ce cas:

entrez la description de l'image ici
[ source ]

Les cycles qui se chevauchent rendent difficile de voir ce que cet automate accepte (en termes d'expressions régulières). Y a-t-il une astuce?

zell
la source
2
Ce serait bien si vous pouviez indiquer dans le diagramme quels sont les états initial et final: une petite flèche vers l'état initial et un double cercle comme état final. De plus, il est difficile de savoir où vous vous trompez si vous ne donnez aucune indication de ce que vous avez essayé.
Dave Clarke
Peut-être que ce document peut vous aider: il explique clairement comment convertir un NFA à un RE.
Vor
1
Pourquoi est-ce difficile? Avez-vous essayé l'un des algorithmes canoniques? Quel est le meilleur ansatz que vous puissiez faire?
Raphael
3
J'ai édité pour rendre la question (à mon humble avis) intéressante et bonne pour ce site. Voir l' historique des révisions pour se faire une opinion.
Raphael
1
J'ai une réponse prête qui transforme votre NFA en une expression régulière, mais je l'ai supprimée: la réponse de Raphaël vous donne la méthode dont vous avez besoin pour le faire vous-même (elle donne également un lien vers un exemple), afin que vous puissiez vous entraîner si vous vouloir. Si vous voulez toujours ma solution, je vais effacer ma réponse.
Alex ten Brink

Réponses:

5

Plutôt que de "lire", vous devriez utiliser l'une des méthodes canonciales pour le faire. De loin le plus beau que j'ai vu est celui qui exprime l'automate comme un système d'équations de langages (réguliers) qui peut être résolu. C'est particulièrement agréable car il semble donner des expressions plus concises que les autres méthodes.

J'ai écrit ce document expliquant la méthode aux étudiants l'été dernier. Il se rapporte directement à une conférence spécifique; la référence mentionnée est la définition typique des expressions régulières. Une preuve du lemme d'Arden (un résultat nécessaire) est contenue; un pour l'exactitude de la méthode est manquant. Comme je l'ai appris lors d'une conférence, je n'ai malheureusement pas de référence.

qi

Qi=qiaqjaQj{{ε}, qiF, else

Fqiaqjqiqja+

QiqiQ0q0

L'application à l'automate donné est laissée comme exercice; un exemple complet est inclus dans le document lié ci-dessus .

Voir aussi ici où j'ai posté une réponse similaire.

Raphael
la source
1
Voir cette question de référence pour d'autres méthodes générales.
Raphael
3

S'il n'y avait qu'une chaîne d'états sans boucle, sauriez-vous quoi faire?

S'il y avait une boucle simple sans cette ramification qui se chevauchait, sauriez-vous quoi faire?

(Si la réponse est «non», pensez d'abord à ces cas.)

Maintenant, l'idée est de transformer progressivement l'automate pour le mettre sous une forme où vous pouvez repérer ces motifs: chaînes, boucles et chemins divergents qui se reconvertissent à la fin (conduisant à l'alternance). À chaque étape de la transformation, veillez à ce que l'automate transformé reconnaisse toujours le même langage.

Gardez à l'esprit qu'il s'agit d'un automate non déterministe. Celui que vous avez publié se révèle être déterministe, mais il ne doit pas rester de cette façon lorsque vous le transformez.

q2q1fq2gq3q4q2q5q4jq5gq3

q3,q4,q5q3q3(hjg)

Prenez soin de vérifier quels états sont finaux. Cela peut aider à ne pas s'inquiéter de cela au début et à faire une grande boucle, puis à dupliquer les parties qui se terminent à mi-chemin de la boucle.

Ce n'est pas nécessairement la technique la plus efficace ou celle qui génère l'expression régulière la plus simple, mais c'est simple.

Gilles 'SO- arrête d'être méchant'
la source
3

Split q_1

Jukka Suomela
la source
Et cela répond à la question comment?
Raphael
1
Si vous réécrivez la machine à états de cette manière, il est désormais trivial de lire l'expression régulière équivalente.
Jukka Suomela
1
Vous devriez peut-être l'inclure dans le texte de la réponse. Cela fonctionne-t-il toujours?
Raphael
@Raphael: Cela fonctionne dans ce cas. :) L'idée générale derrière cette astuce est la suivante: nous avons fait les cycles "correctement imbriqués". Autrement dit, nous n'avons pas la structure du cycle [(])mais [()].
Jukka Suomela