Théorie des langages

Abstract

En linguistique et en informatique, on parle de théorie des langages pour décrire les langages formels. Plus généralement, la théorie des langages concerne tout langage ni ou in ni qui peut etre spécié par une méthode ou un mécanisme ni, et explicite, qui permet de le produire ou de l'analyser. La théorie des langages ne se préoccupe pas du coté sémantique (le sens), mais plutot syntaxique (la forme) d'un langage. On dé nit un langage notamment gr^ace aux gram- maires et on analyse les mots d'un langage gr^ace aux automates ou reconnaisseurs. Ce cours va s'articuler autour de ces trois concepts que sont les langages, les grammaires et les automates. La théorie des langages est une base pour un certain nombre de disciplines informatique dont principalement la compilation mais aussi, la logique, la complexité, la calculabi- lité... Nous allons étudier dans cette matière tous les types de langages décrits dans la clas- si cation de Chomsky que nous allons voir plus tard ainsi que les grammaires qui permettent de les g enérer et les automates qui permettent de les reconnaitre. Dans le chapitre suivant, nous allons étudier les concepts de base des trois axes de notre cours, a savoir les langages, les grammaires et les automates. Nous verrons aussi la classi cation de Chomsky qui dé nit quatre grands types. Un chapitre sera par la suite réservé a chaque type de langage. 6