publicMasters/1-ComputationAndData/6ComputationAndData.md

# Quelques constructions autour des automates.

Nous avons vu le modèle des automates finis.
Nous explorons ici trois techniques.


## Complétez l'automate.

Un automate est incomplet si il peut arriver qu'au cours d'un calcul on ne sache pas quoi faire.
Ceci correspond dans la table de transition à une case sans prochain état pour une lettre donnée.

Pour le compléter, on ajoute un état poubelle à notre automate.
Cet état est un puits dans lequel on reste coincé (toutes transitions sortante reste dans cet été poubelle); et, toute transition manquante devient une transition vers cet état poubelle.


## Déterminisation

* Exemple d-un automate non déterministe à 3 état qui calcule les mots qui commencent et terminent par a et ont au moins deux lettres.
* Calcul sous forme d'un arbre pour aaa, et aaab
* Table de transition
* digression parralèlisme (multi coeurs)
* digression préemption plusieurs processus (commande top)
* digression problème mémoire partagée etc
* retour exemple automate. Super-état. Déterminisation.

### Méthode.
* On part de l'état initial, on note les états accessibles depuis cet état.
* Si un état n'existe pas, on ajoute le super état correspondant.
* Un super-état est acceptant ssi il contient un état acceptant.
* On arrête la construction quand on ne recontre pas de nouvel état.

### Exercice.
On déterminise l'automate non déterministe à 5 états qui acceptent les mots (y compris d'une lettre) qui commencent et terminent par la même lettre.

Donnée du problème : Dessin au tableau
1. Donnez table de transition
2. Pourquoi l'automate n'est pas déterministe
3. Déterminisez l'automate avec la méthode vue en cours.

Correction.

1. la table de transition
|                | a    | b    | c    |
|:---------------|:-----|:-----|:-----|
| 0 (initial)    | 1,OK | 2,OK | 3,OK |
| 1              | 1,OK | 1    | 1    |
| 2              | 2    | 2,OK | 2    |
| 3              | 3    | 3    | 3,OK |
| OK (acceptant) |      |      |      |

2. Non déterminisme visible quand une cas contient au moins 2 états successeurs.
   Par exemple depuis 0 en lisant a je peux aller vers l'état 1 et l'état OK.
   
3. Déterminisation
   
   |                   | a    | b    | c    |
   |:------------------|:-----|:-----|:-----|
   | 0 (initial)       | 1,OK | 2,OK | 3,OK |
   | 1, OK (acceptant) | 1,OK | 1    | 1    |
   | 2, OK (acceptant) | 2    | 2,OK | 2    |
   | 3, OK (acceptant) | 3    | 3    | 3,OK |
   | 1                 | 1,OK | 1    | 1    |
   | 2                 | 2    | 2,OK | 2    |
   | 3                 | 3    | 3    | 3,OK |


## Équivalence.

Méthode pour tester si deux automates sont équivalents (acceptent et rejettent exactement les mêmes mots).


Provisio : il faut que la machine soit déterministe (hypothèse nécessaire pour la preuve) et complète (hypothèse simplificatrice pour la preuve).

* On regarde tous les mots jusqu'à une taille qui est le produit du nombre d'état des automates.
* Il faut que les deux automates disent la même chose (accepter ou rejeter) sinon on a trouvé un contre-exemple et on répond non, ils ne sont pas équivalents.
* Si c'est le cas on répond oui, ils sont équivalents.

La méthode de la machine bi-coeur (similarité avec la construction précédente de déterminisation) permet de démontrer que cette méthode fonctionne et donner soit un contre-exemple, soit une preuve que les deux machines sont équivalentes.

L'idée consiste à simuler de manière synchrone les deux automates en parallèle.
La machine bi-coeur a une paire d'état au début correspondant à la paire des états initiaux.
Il faut que à chaque étape de construction de son programme, les deux coeurs disent la même chose.

Détails dans transparents.