À l’image du langage naturel, qui nous sert à échanger et à communiquer, un langage formel permet de communiquer avec une machine. Si une machine ne comprend au départ que son propre langage, il faut qu’elle puisse comprendre des langages plus évolués. C’est tout l’objet de la théorie des langages.

D’UN LANGAGE À L’AUTRE

Lorsque deux personnes souhaitent communiquer ou échanger des informations, ils utilisent un langage. Ce type de langage, dit langage naturel, est informel et le plus souvent ambigu, si bien que seul le cerveau humain est en capacité de le comprendre. La situation est tout autre lorsque l’on souhaite communiquer avec une machine. Dans ce cas-là, le langage doit être particulièrement structuré et non ambigu, c’est-à-dire formalisé, afin que la machine puisse le comprendre. On parlera alors d’un langage formel. Ces langages formels sont totalement artificiels, dans la mesure où ils sont construits par des humains afin que les machines puissent facilement l’interpréter. Au départ, une machine ne comprend qu’un seul langage, qui a été conçu exprès, le langage machine. L’interprétation et la compilation par la machine d’autres langages plus évolués nécessitent plusieurs analyses (lexicales, syntaxiques et sémantiques). La théorie des langages vise à étudier et faciliter ces analyses.

LES ÉLÉMENTS D’UN LANGAGE

Tout langage, y compris le langage naturel, s’appuie sur des éléments de base appelés l’alphabet du langage. Une combinaison d’éléments de cet alphabet s’appelle un mot. Formellement, un alphabet est un ensemble fini non vide de symboles et un mot est une suite finie d’éléments de l’alphabet. Par exemple, lors de l’analyse lexicale d’un texte, l’alphabet est naturellement les symboles figurant sur le clavier tandis que les mots sont les mots-clés, les identificateurs, les nombres ou encore les opérateurs. On peut définir également la longueur d’un mot comme le nombre d’éléments qui le composent ou la concaténation de deux mots en formant le mot avec les symboles de l’un suivis de ceux de l’autre. Enfin, un langage, défini sur un alphabet, est un ensemble de mots définis sur cet alphabet. Il est ensuite possible de définir un certain nombre d’opérations sur les langages, comme l’union, l’intersection, la différence, le produit de deux langages ou la fermeture itérative d’un langage.

LES GRAMMAIRES

Une fois la notion de langage définie, il est nécessaire de se doter d’un outil qui permette de savoir si les phrases construites avec les mots de l’alphabet sont correctes. C’est le rôle de la grammaire. Le langage naturel possède une grammaire qui permet à la fois de construire des phrases correctes mais aussi de reconnaître si une phrase donnée appartient ou non au langage. Formellement, une grammaire est un quadruplet G = (T, N, S, R) où T est le vocabulaire terminal (c’est-à-dire l’alphabet sur lequel est défini le langage), N est le vocabulaire non terminal (les symboles qui n’apparaissent pas dans les mots générés mais qui sont utilisés lors de la génération), R est un ensemble de règles et S est le symbole de départ ou axiome (point de départ de la génération de mots avec les règles de la grammaire). Ainsi, 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.

LES DIFFÉRENTES CLASSES DE GRAMMAIRES

L’utilisation de critères plus ou moins restrictifs sur la forme des règles de grammaire aboutit à des classes de grammaires hiérarchisées, ordonnées par inclusion. C’est le linguiste Noam Chomsky qui, en 1957, fournit la première classification des grammaires en distinguant quatre grandes classes. La première est celle des grammaires pour lesquelles on n’impose aucune restriction sur les règles. C’est naturellement la plus grande classe possible de grammaires. Ensuite, on trouve la classe des grammaires sensibles au contexte ou contextuelles, puis celle des grammaires hors-contexte et enfin celle des grammaires régulières. Naturellement, un certain langage est associé à chaque type de grammaire. Ainsi, les grammaires sans restriction de règles génèrent les langages dits « décidables », c’est-à-dire tous les langages qui peuvent être reconnus en temps fini par une machine. A contrario, les langages qui ne peuvent pas être générés par une telle grammaire sont dits « indécidables ».

LES AUTOMATES

Chaque classe de grammaire génère différents types de langages. Il est alors nécessaire de se doter d’un outil qui permette à la machine de reconnaître les langages d’un type de grammaire donné, c’est-à-dire de déterminer si un mot appartient au langage. C’est le rôle des automates. À chaque type de grammaire est alors associé un type d’automate. Les langages réguliers sont reconnus par les automates finis, les langages hors-contexte par des automates à pile et les autres langages par des machines de Turing. On comprend alors pourquoi la machine de Turing est considérée comme le modèle de machine le plus puissant. En effet, tout langage qui ne peut être traité par une machine de Turing ne pourra l’être par aucune autre machine. Un automate est une procédure effective, c’est-à-dire un algorithme, qui permet de déterminer si un mot donné appartient à un langage. L’automate permet ainsi la compilation d’un programme, c’est-à-dire la transformation d’un langage source en langage machine.

À RETENIR

Lorsque nous communiquons ou échangeons des idées, nous utilisons un langage, le langage naturel. Mais lorsque nous souhaitons communiquer avec une machine, il faut créer des langages artificiels et des outils permettant à la machine de comprendre ces langages. C’est l’objet de la théorie des langages. On se donne un alphabet permettant de construire des mots. Ensuite, une grammaire (des règles) permettra de générer différents types de langages. Enfin, des automates associés aux grammaires permettront à la machine de reconnaître les langages.