Exercice Vrai-Faux / Oui-Non (corrigé de Michaël Périn)
Table of Contents
- 1. Est-il toujours possible de transformer un automate en automate non-déterministe avec epsilon transition pour avoir un seul état accepteur ?
- 2. Est-il toujours possible de transformer un automate en automate déterministe sans epsilon-transition et avoir un seul état accepteur ?
- 3. Est-il toujours possible de transformer un automate en automate non-déterministe sans epsilon-transition et avoir un seul état accepteur ?
1 Est-il toujours possible de transformer un automate en automate non-déterministe avec epsilon transition pour avoir un seul état accepteur ?
Oui. Preuve : il suffit de
- créer un nouvel état (q) qui sera accepteur
- ajouter des espilon-transitions des états accepteurs vers le nouvel état (q)
- rendre non-accepteurs les anciens états accepteurs
L'automate obtenu est équivalent à l'automate de départ au sens où il reconnaît le même langage.
2 Est-il toujours possible de transformer un automate en automate déterministe sans epsilon-transition et avoir un seul état accepteur ?
Non. Contre-exemple : si on applique la technique de la question 1 à l'automate suivant
->((1)) -a->((2))
on obtient un automate déterministe à seul état accepteur mais comportant des epsilons transitions. Lorsqu'ensuite on élimine les epsilons transitions on retombe … sur l'automate de départ.
Conclusion : on ne peut pas en général se ramener à un automate déterministe sans espilon transition à un seul état accepteur.
3 Est-il toujours possible de transformer un automate en automate non-déterministe sans epsilon-transition et avoir un seul état accepteur ?
Non. Même contre-exemple. Le fait d'autoriser le non-déterminisme ne permet pas d'éliminer les espilons-transitions et de garder un seul état accepteur.
Ce problème apparaît dans le cas des automates qui reconnaissent epsilon.