Automates finis déterministes
L'automate fini déterministe : états, transitions, état initial et états acceptants, table de transitions, lecture d'un mot, langage reconnu, automate complet avec état puits et automate du complémentaire.
- 24 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Automate fini déterministe : de quoi s'agit-il ?
Voir la réponse
Machine à nombre fini d'états qui lit un mot lettre par lettre, avec au plus une transition par état et par lettre, et un unique état de départ.
C'est un quintuplet (Q, Σ, δ, q₀, F). Le calcul est unique : un mot suit au plus un chemin, donc il est accepté ou refusé sans ambiguïté. Avec exactement une transition par état et par lettre, l'automate est de plus complet.
Cet automate lit les nombres écrits en binaire ; l'état est le reste modulo 3 de ce qui a été lu, 0 est initial et acceptant. Il lit 1001. Où s'arrête-t-il, et le mot est-il accepté ?
```text
0 1
→*0 0 1
1 2 0
2 1 2`- À l'état 0, accepté
- À l'état 1, refusé
- À l'état 2, refusé
- À l'état 1, accepté, car il est passé par 0
Voir la réponse
À l'état 0, accepté
Chemin : 0 -1→ 1 -0→ 2 -0→ 1 -1→ 0. L'arrêt en 0 signifie reste 0, et 1001 en binaire vaut 9 = 3 × 3. Il est accepté parce que 0 est acceptant, pas parce qu'on y est repassé.
Un automate est un quintuplet (Q, Σ, δ, q₀, F) : Q est l'ensemble des …, δ la fonction de … et F l'ensemble des états ….
Voir la réponse
Un automate est un quintuplet (Q, Σ, δ, q₀, F) : Q est l'ensemble des états, δ la fonction de transition et F l'ensemble des états acceptants.
q₀ est l'état initial, un seul pour un automate déterministe. Σ est l'alphabet lu.
Fonction de transition : de quoi s'agit-il ?
Voir la réponse
La fonction δ qui, à un état et à une lettre, associe l'état atteint en lisant cette lettre depuis cet état.
δ(q, a) = p se dessine par une flèche de q vers p étiquetée a. Elle se range dans une table : une ligne par état, une colonne par lettre.