L’objet de ce cours est une initiation à la théorie des langages formels. De manière générale, les langages sont les supports naturels de communication. Ils permettent aux hommes d’échanger des informations et des idées, ils leur permettent également de communiquer avec les machines.
La théorie des langages permet de résoudre ce type de problème. En théorie des langages, l’ensemble des entités élémentaires est appelé l’alphabet. Une combinaison d’entités élémentaires est appelé un mot. Un ensemble de mots est appelé un langage et est décrit par une grammaire.
Le langage défini, ou généré, par une grammaire est l’ensemble des mots qui peuvent être obtenus à partir du symbole de départ par application des règles de la grammaire. Plus formellement, on introduit les notions de dérivation entre formes, d’abord en une étape, ensuite en plusieurs étapes.
Dans le cas d’un langage de programmation, on se sert d’une grammaire pour décrire les entités du langage. La forme de Backus-Naur (BNF), souvent utilisée pour décrire la syntaxe des langages de programmation, est en fait une grammaire au sens où nous allons le définir.