Automate

[BigL]

Bonjour,

Je me demandais comment il était possible de démontrer que tout automate fini non déterministe peut être converti en automate fini non déterministe qui contient un seul état accepteur.

Merci à l'avance

[Doraki]

Tu ajoutes un état accepteur qui ne mène nulle part, et pour chaque flèche qui va vers un état qui était accepteur dans l'automate de départ, tu rajoutes la même flèche mais vers le nouvel état accepteur.

[BigL]

je suis pas sur de bien comprendre ta réponse

[Monsieur23]

Aloha,

Alternative à Doraki, puisque tu te fiches du déterminisme :
— tu ajoutes un état F, qui sera l'unique état accepteur (tu transformes les anciens accepteurs en états normaux)
— de chaque état anciennement accepteur, tu ajoutes une epsilon-transition vers F.