Théorie des Langages
S. Mazouz & B. Laichi
FEI-USTHB
Département Informatique
2019-2020
campusvirtuel.usthb.dz
LANGAGE (DÉFINITIONS)
Un langage est un ensemble de phrases ou mots
satisfaisant certaines règles.
Exemple simple : Le langage composé des phrases
respectant la forme suivante :
Phrase = Sujet Verbe
Sujet = Pronom
Pronom = il ou elle
Verbe = écoute ou regarde
L’ensemble des phrases formées est :
il écoute, elle écoute, il regarde, elle regarde.
LANGAGE (EXEMPLES)
De très nombreux langages existent, par exemple :
Les langages naturels (arabe, anglais, …).
Les langages utilisés en mathématiques et en
logique mathématique (langage de la logique
propositionnelle, langage de la logique des prédicats).
Les langages informatiques qui sont la principale
motivation de ce cours (C, C++, JAVA, ...)
LANGAGE (INTÉRÊTS)
Les langages permettent de :
Communiquer soit :
Entre nous (Langages naturels)
Avec la machine (Langages de programmation)
Entre machines (Protocoles réseaux : TCP/IP,
ATM, …)
Décrire des systèmes, des documents, …
(Description des pages web avec HTML, …)
Formaliser des problèmes afin de les résoudre
(Détection des ressemblances d’ADN ou
Protéines en Bioinformatique)
THEORIE DES LANGAGES
La théorie des langages trouve son
origine dans la tentative de
formalisation du langage naturel par le
linguistique Noam Chomsky 1956.
Par la suite, il y a eu le besoin des informaticiens de
l’époque pour :
Décrire de manière finie certains langages infinis
Mettre en place les premiers langages de
programmation (Fortan, Algol, …).
THÉORIE DES LANGAGES
En théorie des langages, nous avons besoin de :
Décrire formellement un langage Grammaire
Reconnaître formellement un langage Automate
Grammaire formelle : permet d’engendrer (générer) les
mots du langage, généralement infini, en utilisant un
ensemble fini de règles.
THÉORIE DES LANGAGES
Automate : est une machine abstraite qui permet de
reconnaître les mots d’un langage.
Etant donné un mot fourni en entrée, l'automate procédera à
sa lecture et décidera s’il est accepté (appartient au
langage) ou rejeté (n’appartient pas au langage)
Mot Accepté
Automate de L
Rejeté
THÉORIE DES LANGAGES
La théorie des langages établit des correspondances
entre :
descriptions génératives (grammaires)
et
descriptions analytiques (automates)
APPLICATIONS DE LA THÉORIE DES LANGAGES
o Convertir un « problème » en un langage :
La résolution du problème revient à l'analyse d'un élément de ce
langage. Un automate qui résout le problème prend en entrée un
mot et décide s'il est accepté ou non.
Exemple : Déterminer si un entier N est pair (test de parité).
Ce problème peut se traduire comme suit :
On représente tous les entiers naturels par des chaînes binaires
(écriture en base 2).
Dans ce langage, les mots représentant des nombres pairs
forment un sous-ensemble.
Le test de parité consiste alors à vérifier si la chaîne binaire
représentant un nombre N appartient à ce sous-ensemble ou non
Un automate approprié prend en entrée une chaîne binaire et
l'accepte précisément lorsqu'elle représente un nombre pair.
APPLICATIONS DE LA THÉORIE DES LANGAGES
En compilation : reconnaître qu’un programme
d’un langage donné est syntaxiquement correcte.
Recherche des motifs :
Recherche d’une chaine dans un fichier
(Recherche sous word)
Recherche dans un répertoire (Recherche sous
Dos/Linux)
Recherche dans le web (Moteur de recherche)
Réaliser des contrôles : Vérifier qu’une donnée
entrée par un utilisateur a bien le format spécifié
par exemple: une adresse IP, une adresse e-mail,...
Industries de la langue :
• Traitement automatique des langages naturels
• Correction orthographique automatique
• Génération automatique de textes
• Réalisation de dictionnaire électronique (gain de mémoire)
Vérification des circuits électroniques : en utilisant par
exemple VHDL qui est un langage de descriptions de matériel
destiné à représenter le comportement ainsi que l’architecture
d’un système électronique numérique.
Biologie (génomique) : Recherche de gènes particuliers
dans une chaine. En génomique, on dispose d’un alphabet de
4 lettres correspondant aux bases de l'ADN) ou protéomes
(textes sur un alphabet de 20 lettres correspondant aux acides
aminés qui constituent les protéines).
