INFORMATIQUE Principes
Automates et langages formels
Langage formel
Un langage formel est, par définition, un langage ne possédant qu'une syntaxe et pas de sémantique. Un tel langage est très différent des langages naturels puisqu'il ne comporte qu'une grammaire et que le sens des mots n'intervient pas. C'est cependant en partant, non pas de la linguistique, mais de l'activité linguistique des individus, et en cherchant à résoudre un double problème, à savoir celui de l'individu parlant – capable, en apprenant un nombre fini de mots et de phrases, de former ensuite un nombre infini de phrases syntaxiquement correctes –, et celui de l'individu écoutant – capable de reconnaître la correction syntaxique d'une phrase qu'il n'a jamais entendue au préalable –, que Noam Chomsky aboutit à la théorie des grammaires génératives et des automates de reconnaissance.
Selon Chomsky, un langage formel L est formé par un quadruplet :
Choisissons par exemple un langage L1, tel que :
(le symbole → signifie « peut se remplacer par »).
Partant de P et en utilisant la règle P → aPa, on aboutit à aPa ; en appliquant à nouveau la même règle au symbole de P dans aPa, on obtient a(aPa)a, soit aaPaa, et ainsi de suite, chaque règle pouvant être utilisée à tout moment et autant de fois que l'on veut pour aboutir à une « phrase » n'ayant que des mots du vocabulaire terminal.
Les phrases QKQ, QQKQQ, ..., et de façon plus générale les phrases QpKQp, c'est-à-dire toutes celles ayant un nombre p de mots Q, suivi du mot K, suivi du même nombre p de mots Q, seront des phrases du langage L1. Ce même langage comprendra aussi les phrases QKKQ, QKKQK, QKKKQKK, etc.
Le mécanisme précédent résout le premier problème évoqué, à savoir celui de la génération d'un nombre infini de phrases d'un langage à partir d'un vocabulaire fini et d'un nombre fini de règles de grammaire. Le second problème, qui consiste à trouver un mécanisme permettant de reconnaître si une « phrase » quelconque appartient ou non à un langage déterminé, sera résolu par la définition d'un « automate de reconnaissance » qui est un dispositif ayant un nombre fini d'états et muni d'une mémoire finie ou infinie. Un tel « automate » sera capable de « lire » une phrase de gauche à droite et, arrivé à l'extrémité de la phrase, de « dire » si la phrase appartient ou non au langage qu'il est capable de reconnaître, étant entendu que l'automate fonctionne selon un nombre fini de règles fixes données à l'avance. Un des grands mérites de Chomsky a été de proposer une classification des langages formels selon leur degré de complexité syntaxique, c'est-à-dire selon le degré de complexité de l'automate de reconnaissance.
Langages réguliers et automates à nombre fini d'états
Les langages réguliers, définis initialement par Stephan Cole Kleene, sont ceux dont la grammaire ne comporte qu'un seul type de règles de réécriture, à savoir qu'un mot non terminal ne peut être réécrit que sous la forme d'un mot non terminal suivi d'un mot terminal, ou l'inverse, ou encore sous la forme d'un mot terminal.
Prenons par exemple le langage suivant :
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Jacques HEBENSTREIT : ingénieur Supélec, docteur ès sciences, lauréat de l'Académie des sciences, consultant à l'O.C.D.E.
Classification
Médias
Automate à nombre fini d'états
Encyclopædia Universalis France
Automate à pile de mémoire
Encyclopædia Universalis France
Autres références
-
PHYSIQUE - Physique et informatique
- Écrit par Claude ROIESNEL
- 6 760 mots
La révolution informatique est de nature technologique. Les physiciens sont associés à toutes les étapes de son développement. Les technologies incorporées dans les premiers ordinateurs avaient été inventées pour les besoins de la recherche en physique nucléaire. Le convertisseur analogue-digital,...
-
AFFICHE
- Écrit par Michel WLASSIKOFF
- 6 817 mots
- 12 médias
Dansles années 1990, l'affiche est de plus en plus souvent conçue sur écran, la publication assistée par ordinateur (P.A.O.) permettant l'association des textes et des images. La mise au point du langage Postscript conduit à la création de caractères haute résolution et le dessin de lettres connaît... -
AIKEN HOWARD HATHAWAY (1900-1973)
- Écrit par Bernard PIRE
- 506 mots
L’Américain Howard Aiken fut un des pionniers de l'informatique, concepteur de l'IBM Automatic Sequence Controlled Calculator (ASCC) encore appelé Harvard Mark I.
Après avoir suivi les cours d'une école technique tout en travaillant la nuit, Howard Hathaway Aiken, né le 9 mars 1900 à...
-
ALGORITHME
- Écrit par Alberto NAIBO et Thomas SEILLER
- 5 919 mots
- 4 médias
La notion d’algorithme a envahi nos discours et nos pratiques, en raison surtout de la diffusion massive d’applications informatiques dédiées à l’exécution automatisée de certaines tâches, ou à la résolution de certains problèmes. On trouve en effet les algorithmes non seulement dans de nombreux domaines...
-
APPLE
- Écrit par Pierre MOUNIER-KUHN
- 2 547 mots
- 2 médias
Archétype des start-up de la Silicon Valley, la société américaine Apple, fondée en 1976, a gagné fortune et célébrité par ses innovations de rupture, de l’ordinateur Macintosh au téléphone portable iPhone et à la tablette numérique iPad. Associée au talent visionnaire de son président historique,...
- Afficher les 148 références
