Automates

Ce cours présente les différents langages formels de la classification de Chomsky avec les machines abstraites qui acceptent ces langages.

Son objectif est à la fois théorique et pratique :

sur le plan théorique, l’objectif est de faire voir aux étudiants qu’on aboutit finalement à une formalisation mathématique du concept d’algorithme (la notion de calculabilité est évoquée à la fin du cours) ;
sur le plan pratique, ce cours permet aux étudiants de se familiariser avec des formalismes utilisés dans d’autres cours : grammaire (compilation) ; automates finis déterministes (conception de systèmes matériels).

Introduction - généralités

Grammaires formelles

Expressions régulières

Automates finis déterministes (AFD)

Automates finis non déterministes (AFND)

Notion d’automate minimal

Conclusion sur les langages réguliers

Automates à pile non déterministes (APND)

Machines de Turing

A remplir

Il n'y a pas de prérequis à ce cours