|
|---|
Déterminiser l'automate fini suivant :
|
|
|---|
Afin de déterminiser, on construit pas à pas la fonction de transition de l'automate déterministe équivalent. Les états de l'automate déterministe sont des macro-états constitués d'un ou plusieurs états de l'automate non-déterministe. En particulier, l'état initial de l'automate déterministe est le macro-état contenant tous les états initiaux de l'automate non-déterministe. Ici c'est donc {A} :
|
|---|
Dans cette table, une case vide indique qu'il n'y a pas de transition au départ du macro-état correspondant à la ligne et pour le symbole correspondant à la colonne. Donc l'automate déterministe équivalent est :
|
|---|
On considère le jeu suivant. Les billes arrivent en A ou en B. chaque fois qu'une bille passe sur une des portes rouges, cette porte s'inverse, si bien que la fois suivante, la bille tombera de l'autre côté.
|
|---|
On décide de représenter par 0 le fait qu'une bille arrive du côté A, et par 1 le fait qu'une bille arrive du côté B. Le problème consiste à construire l'automate fini qui reconnaît le langage, sur le vocabulaire VT = {0,1}, contenant les mots correspondant à des suites de billes dont la dernière tombe du côté D. La seconde question consiste à trouver l'expression régulière de ce langage.
Par exemple, si la première bille arrive en A, elle tombe du côté C et inverse la porte x. La deuxième bille arrivant en A tombe du côté C et inverse les portes x et z. La troisième bille arrivant en A tombe du côté C et inverse la porte x. Enfin la quatrième bille arrivant en A tombe du côté D et inverse les portes x et z. En définitive, la chaîne 0000 appartient à notre langage.
On choisit de coder l'état des 3 portes par trois caractères G ou D, selon que la prochaine bille doit tomber à gauche ou à droite. L'état initial est donc GGG. Puisque chaque porte peut être dans 2 états différents et qu'il y a 3 portes, on s'attend à trouver 23 états différents, c'est-à-dire 8. En fait il y en a plus car certains états sont accepteurs et d'autres pas. Par exemple, l'état initial est GGG qui n'est pas accepteur. On a vu qu'en partant de la configuration GGG, la séquence 0000 doit être acceptée. Or cette séquence conduit à la même configuration GGG. Mais cette configuration doit être un état accepteur, ce que n'était pas l'état initial. Par conséquent, il y a deux états pour la même configuration GGG, un accepteur que nous notons GGGa et un non accepteur que nous notons GGG.
Au total, on trouve 13 états, dont 6 accepteurs :
|
|---|