Présentation

Le cours présente les notions relatives aux langages réguliers et aux automates à états finis. On présente également des outils dans le cadre de l’analyse lexicale. 

• Introduction aux langages formels : alphabets, mots, facteurs, ordre sur les mots, opérations ensemblistes et algébriques sur les langages, fermetures des langages, langages réguliers, expressions régulières. 
• Introduction aux automates : automates déterministes et non déterministes, calculs dans un automate, langages reconnaissables, automates complets, produits d'automates, déterminisation des automates, automates asynchrones, théorème des éliminations des epsilon-transitions, exemples de langages reconnus, théorème de Kleene, l’algorithme de Brzozowski et Mac Cluskey, minimisation des automates. Exemples d'applications d'automates.