Automates et Etat(s) Initiau(x)

Questions/Réponses par disciplines Informatique
1

Bonjour

Je n’ai pas l’impression que le programme soit explicite sur la definition des automates finis: se restreint on à un unique etat initiale considere t on I l’ensemble des etats initiaux.
Bien sur, un etat unique ne restreint pas la generalité (puisqu’il suffit de determiniser) mais avec plusieur etats initiaux possible ont a une construction de l’union parresseuse (et de ce point de vue rejouissante).

Par ailleurs la definition qui m’est familliere
Sur un alphabet A, on definie un automate finie comme (S, T, I, F)

  • S est un ensemble fini (non vide) d’états,
  • T ⊆ S × A × S est une relation de transition,
  • I ⊆ S est l’ensemble (non vide) des états initiaux, (ou alternativement i un etat inital)
  • F ⊆ S est l’ensemble des états finaux

semblent connaitre des « formats » different, par exemple avec une fonction pour la transition (qui ne peut donc pas avoir le meme ensemble d’arrivée dans les cas deterministes et non deterministes) ou par des renomages de symboles (par exemple avec une fonction de transition nommé delta, ce qui est super memotechnique mais bon ou un alphabet nommé \Sigma ce qui parait pas super memotechnique non plus)

Y a t il une « verité du concours » ou cela depend du choix de l’enseignant et les diverses variantes seront admises (y compris "l’union paresseuses) ?

w.

w

2

Dans le cas déterministe, je pense qu’une fonction delta de transition est le plus courant (et un seul état initial, bien sûr).
Dans le cas non déterministe on trouve un peu tout, tant dans les cours que dans les sujets de concours : des fonctions delta à valeurs dans P(S) ou des ensembles de triplets, un seul ou plusieurs états initiaux.
De toute façon en info je ne connais pas une seule définition qui soit parfaitement fixée, il faut toujours s’adapter à l’auteur du sujet ou de l’ouvrage.

3

merci bien. Si je comprends bien il faut bien lire le sujet et s’adapter.
w.

PS
J’ai l’impression que la didactique « computer science » en premier cycle n’est pas vraiment stable. Peut etre que la creation recente d’une agreg d’info et donc d’un programme y contribura mais pas sur (personnellement je suis dubitatif sur le dit programme et l’interet de cette agregation mais je m’egare)