Theory of Computation (3 credits)

Ce support de cours reflète les deux objectifs de ce cours. Le premier est d’ac-
quérir les principales notions élémentaires en langages formels, calculabilité et
complexité. Le second est de ne pas rester uniquement au niveau des définitions
et trivialités et de montrer quelques jolis résultats de ces différents domaines. Ce
choix fait que des résultats de difficultés très différentes se côtoient. Le premier
chapitre sur les langages rationnels contient par exemple le lemme de l’étoile
mais aussi la caractérisation de Schützenberger des langages sans étoile.