Voilà un sujet passionnant sur le quel portais le dernier document que j'ai lu. Une petite cinquantaine de page dont je vais vous faire un résumer rapide pour vous mette l'eau a la bouche.
Dans une première partie, l'auteur nous introduis au près de la terminologie qu'il compte employer.
Sigma un alphabet, Sigma* un langage, indénombrabilitée des langages. Très rapidement, il aborde des règles d'écriture rationnel (Cf: Expression régulière) qui permettent de définir un langage (ex: (a+b)a*(aba)*b).
Alors que l'on se retrouve satisfait de cette lecture, c'est alors que commence le cœur de ces notes. Les automates : Ils sont un mécanisme permettant de vérifier si un mot u de Sigma* appartient a un langage L. Plus que des outils, ils se révèlent une véritable définition d'un langage. Y sont aborder les automates déterministe, non déterministe, et non déterministe à transition spontané.
On remarqueras la similitude entre une machine de Turing et la définition d'un automate déterministe.
On trouveras enfin des mécanisme permettant de construire des automates pour un langage.
Entre définition et démonstration, on trouveras même quelques exercices pour les plus motiver (Personnellement, je me contenterai de cette lecture, aillant déjà asse a faire avec mes études).
Pour faire simple, vous l'auriez compris, une lecture très instructive que je recommande a tous ceux qui démontre un intérêt envers la structure des langage.
Merci a François Yvon et Akim Demaille pour ce document.
Lien vers la dernière révision sur le site de l'auteur
Edit : Il semblerais que ce terme soit aborder à lyon1 au 5ième semestre de Licence d'informatique (Module LIF11)