Une toute première version de ce support de cours a été rédigée pendant l'année 2004/2005 par les élèves Gaëtan Bisson, François Garillot, Thierry Martinez et Sam Zoghaib. Ensuite, il a été complètement repris et très largement étoffé par mes soins. Même si la version actuelle est relativement éloignée de la première version, elle lui doit l'impulsion initiale sans laquelle elle n'existerait peut-être pas. Certains passages ont aussi bénéficié de quelques travaux de rédaction des élèves. Malgré tous ces efforts, ce support de cours contient encore de trop nombreuses erreurs et omissions. Une certaine indulgence est demandée au lecteur. Les corrections et suggestions sont bien sûr les bienvenues.
Ce support de cours reflète les deux objectifs de ce cours. Le premier est d'acqué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.
Les deux parties reprennent la division du cours en deux grandes parties: les langages formels d'une part, calculabilité et complexité d'autre part. Chacune de ces deux parties est scindée en deux chapitres. Les deux premiers chapitres sont consacrés aux langages rationnels et aux langages algébriques et les deux suivants à la calculabilité et à la complexité.