Sciences.ch (automates)

Le propos de ce chapitre est d'étudier le fonctionnement théorique du concept ordinateur, ou machine. Nous nous situons ici au niveau des mathématiques et de la logique mathématique, indépendamment de toute référence à une machine (ou un logiciel) concrète existante. Nous nous pencherons sur la façon dont cette machine théorique va prendre connaissance de données numériques, de quelque nature qu'elles soient, pour en effectuer un traitement, en vue de résoudre un problème d'ordre général. Nous serons alors amenés à constater que, de ce point de vue, toute machine théorique est réductible, dans son principe de fonctionnement, à une machine idéale. Ainsi, nous pouvons dire que tous les ordinateurs, ou tous les programmes, sont équivalents entre eux, puisque le propre d'un ordinateur, dans sa définition théorique, est l'universalité, c'est-à-dire la capacité à traiter tous les problèmes traitables effectivement.

Remarque: Ce chapitre aurait normalement sa place en tout premier de la section d'informatique théorique mais il nous a semblé plus judicieux de se faire au préalable la main sur des exemples concrets de l'informatique théorique avant de passer au formalisme abstrait de leurs exécutions. C'est une des raisons pour lesquelles nous reviendrons ici brièvement sur les concepts d'algorithmes, de complexité, de systèmes logiques formels, de théorie de la démonstration et de l'information (voir les chapitres du même nom). Par ailleurs, pour ce chapitre, une expérience dans le développement de logiciels informatiques est un grand plus pour comprendre certaines notions (ou pour s'imaginer les applications pratiques).

Avant de commencer, il convient de faire un tour d'horizon très sommaire des questions mises en jeu par ces premiers mots. Mais d'abord citons quelques domaines où la théorie du langage et les automates sont utilisés: spécification des langages de programmation, compilation, recherche de motifs (dans un texte, dans une base de données, sur le web, dans les gènes, ...), compression de textes, preuves de programmes, électronique des ordinateurs, codage pour la transmission, cryptographie, décodage du génome, linguistique, sciences cognitives, etc.

MISE EN PERSPECTIVE

L'informatique moderne est née de la recherche entreprise au début du 20ème siècle par Bertrand Russel et Alfred North Whitehead pour constituer la mathématique en un système formel où toute proposition pourrait être démontrée par un calcul logique (cf. chapitre de Théorie De La Démonstration). David Hilbert et Kurt Gödel accomplirent des pas décisifs dans l'exploration de ce programme. En 1931, Gödel démontre que (rappel):

1. Il se peut que dans certains cas, nous puissions démontrer une chose et son contraire (inconsistance)

2. Dans tout système mathématique formel, il existe des vérités mathématiques qu'il est impossible de démontrer (incomplétude)

Le théorème de Gödel ruine ainsi le rêve de réunir la mathématique en un système déductif parfaitement cohérent, mais de l'effervescence intellectuelle autour du projet des Principia de Russel et Whitehead vont sortir les idées fondatrices de l'informatique. Cela amène en 1936 Alan Turing, à la suite de Gödel, à s'attaquer au problème de la décidabilité.

Définition: Un système est appelé "système décidable" s'il existe une procédure effective pour distinguer les propositions démontrables des autres. Pour définir plus rigoureusement la notion de procédure effective, Turing élabore le concept "d'automate", appelé par la suite "machine de Turing" (voir exemple plus bas), qui lui permet de préciser la notion d'exécution d'un "algorithme" (cf. chapitre de Méthodes Numériques).

Inventer des procédures effectives (des algorithmes) consiste à déterminer un enchaînement d'opérations élémentaires qui exécuteront les calculs nécessaires à la solution de problèmes pour lesquels existent des solutions calculables (il y a des problèmes sans solution et des solutions incalculables comme nous l'avons vu lors de notre étude de la complexité dans le chapitre de méthodes numériques). Turing démontre en outre que son modèle de calcul est universel, c'est-à-dire que toutes les machines de Turing sont équivalentes (nous le démontrerons plus loin). Il formule l'hypothèse selon laquelle tout algorithme est calculable par une machine de Turing. Ces idées fondent la théorie de la programmation des ordinateurs.

MACHINE DE VON NEUMANN

Il revient à von Neumann de concevoir en 1945 l'architecture générale des appareils concrets qui vont réaliser les calculs selon le modèle de Turing, architecture si efficiente et élégante que les ordinateurs d'aujourd'hui sont encore construits, pour l'essentiel, selon ces principes.

Remarque: Nous pouvons d'une certaine façon dire que cette décennie entre 1936 et 1945 a vu la naissance de l'informatique, qui est passée du stade de construction intellectuelle mathématique et logique à celui de l'application de ces idées à la réalisation de systèmes physiques concrets.

Les unités de contrôle (Control Unit), arithmétique (ALU) et de mémoire primaire (Primary Memory) constituent à elles trois l'unité centrale, ou le "processeur" de l'ordinateur. Le processeur est constitué de circuits électroniques qui peuvent exécuter des actions. L'ensemble des actions câblées dans le processeur constitue le jeu d'instructions du processeur et détermine le langage élémentaire de son utilisation, appelé "langage machine".

Le rôle de l'unité de contrôle consiste à permettre le déclenchement de l'action (l'instruction) voulue au moment voulu. Cette instruction peut appartenir à l'unité arithmétique, à l'unité de mémoire ou à l'unité de contrôle elle-même. Une instruction peut en outre consulter le contenu de la mémoire (la "lire") ou modifier le contenu de la mémoire (y "écrire"). De façon générale, une action consiste soit à consulter ou à modifier l'état de la mémoire ou d'un des registres (qui sont des éléments de mémoire spéciaux incorporés à l'unité centrale), soit à déclencher une opération d'entrée-sortie (communication avec le monde extérieur et notamment l'utilisateur humain).

Comment indiquons-nous à l'unité de contrôle le moment voulu pour déclencher telle ou telle action?: C'est écrit dans le texte d'un programme. Où est le programme ?: Dans la mémoire.

La mémoire est constituée d'éléments susceptibles de prendre des états. Un élément de base de la mémoire peut prendre deux états distincts et peut servir à représenter une donnée élémentaire, ou bit (cf. chapitre sur les Systèmes Logiques). Cette représentation d'une donnée par un élément de mémoire s'appelle un "code". Une mémoire avec beaucoup de bits permet le codage de données complexes, dans la limite de la taille de la mémoire.

Le chemin par lequel unité centrale, mémoire et organes d'entrée-sortie (Devices) communiquent s'appelle de façon générique un "bus" (c'est en quelque sorte l'autoroute où circulent des données d'un point à un autre à l'aide d'adresses). De façon un peu formelle, un bus est un graphe connexe complet (cf. chapitre de Théorie Des Graphes), ce qui veut dire en langage courant que tous les éléments connectés au bus peuvent communiquer entre eux.

Remarque: Le codage fait correspondre des groupes de bits à des symboles. Les symboles les plus simples sont les chiffres et les lettres. Pour représenter des données complexes on peut définir des méthodes, des règles pour regrouper des symboles puis associer un élément de données à un groupe de symboles construit selon les règles.

Définition: Nous appellerons "langage" un ensemble de symboles ou de groupes de symboles, construits selon certaines règles, et qui sont les mots du langage. La "syntaxe du langage" est l'ensemble des règles de construction des mots du langage.

La mémoire de l'ordinateur (c'est l'idée fondamentale de von Neumann) contient des informations de deux types: des programmes et des données. Les programmes et les données sont représentés avec les mêmes symboles, seule la sémantique permet d'interpréter leurs textes respectifs. D'ailleurs, le texte d'un programme peut parfois être envisagé comme des données pour un autre programme, par exemple un programme de traduction d'un langage dans un autre.

MACHINE DE TURING

Il importe de se convaincre (ce ne sera pas en un jour) que tous les programmes que nous pourrons écrire dans différents langages sont équivalents. La machine de Turing est un modèle d'automate dont on trouvera ci-dessous une description très terre à terre (avant de passer à une définition beaucoup plus formelle). L'architecture de von Neumann, conçue pour réaliser efficacement les traitements décrits par une machine de Turing, engendre les langages impératifs (voir définition en R1 ci-dessous). Tout programme, fonctionnel ou impératif, destiné à être exécuté, sera traduit dans un langage impératif, le langage machine de l'ordinateur utilisé. La cohérence de l'informatique, et l'équivalence sémantique des programmes écrits en divers langages, qui assurent la validité de cette opération, sont le fruit non pas du hasard, mais d'une conception théorique originelle commune. Gödel, Church, von Neumann et Turing étaient tous à Princeton en 1936.

Remarques:

R1. Les premiers langages évolués qui apparurent sont des langages dits "langages impératifs", fondés sur la notion d'état de la mémoire (c'est l'assembleur au fait!). Ces langages, inspirés du modèle de John von Neumann, comportent comme le langage machine des instructions qui produisent des modifications de la mémoire (instruction d'affectation). La rédaction d'un programme en langage impératif consiste à écrire la suite des instructions qui vont causer les états successifs par lesquels devra passer la mémoire pour que, en partant d'un état initial permettant l'initialisation du programme, elle arrive dans un état final fournissant les résultats recherchés.

R2. Outres les langages impératifs, en informatique, nous distinguons les langages séquentiels, interprétés et compilés.

Un modèle formel pour une procédure effective (pour décrire un algorithme) doit posséder certaines propriétés. Premièrement, chaque procédure doit recevoir une définition finie. Deuxièmement, la procédure doit être composée d'étapes distinctes, dont chacune doit pouvoir être accomplie mécaniquement. Dans sa simplicité, la machine de Turing composée des éléments suivants répond à ce programme:

1. Une mémoire infinie représentée par un ruban divisé en cases. Chaque case du ruban peut recevoir un symbole de l'alphabet défini pour la machine ;

3. Un ensemble fini d'états parmi lesquels on distingue un état initial et les autres états, dits "états accepteurs"

4. Une fonction de transition qui, pour chaque état de la machine et chaque symbole figurant sous la tête de lecture, précise: l'état suivant, le caractère qui sera écrit sur le ruban à la place de celui qui se trouvait sous la tête de lecture, le sens du prochain déplacement de la tête de lecture.

On peut doter sa Machine de Turing de l'alphabet fini de son choix. Son ruban peut être infini dans les deux sens ou dans un seul. Elle peut même avoir plusieurs rubans. On montre que ces diverses machines sont équivalentes.

Un automate fini est un modèle mathématique des systèmes ayant un nombre fini d'états et que des actions (externes ou internes) peuvent faire passer d'un état à un autre. Les actions externes sont représentées par les symboles d'un alphabet A ; les actions internes (invisibles, silencieuses, ou spontanées) sont représentées par un symbole n'appartenant pas à l'alphabet précité.

Les automates finis permettent de modéliser et de contrôler des systèmes à nombre d'états finis et de résoudre des problèmes courants: analyse lexicale, recherche de motifs dans un texte, analyse du génome, etc.

E1. Automate fini et déterministe qui reconnaît tous les entiers dont l'écriture est normalisée (langage régulier), c'est-à-dire ne commençant pas par 0 (les chiffres dans les cercles sont juste là pour décrire l'ordre dans lequel l'automate exécute l'opération):

Explication: L'automate reçoit dans l'entrée (1) un nombre entier, il regarde si ce nombre commence par un 0 ou est un nombre compris entre 1 et 9. Si le nombre commence par zéro, l'automate sort et s'arrête en (3). Sinon, l'automate va en (2) et analyse les chiffres du nombre les uns après les autres jusqu'à ce qu'il arrive à la fin après quoi il s'arrête et sort en (3).

E2. Automate fini et déterministe qui reconnaît une entrée numérique dans un tableur type langage régulier (par exemple: +12,3 ou 08 ou -15 ou 5E12 ou 14E-3):

qui est bien régulier où

est le mot vide, A est l'alphabet {0,1,...,9} et

l'ensemble des mots (in extenso des nombres) qu'on peut écrire avec A.

E3. Automate fini et déterministe reconnaissant tous les multiples de 3, type langage régulier (en d'autres termes si un tel multiple est trouvé, l'automate effectue une sortie, sinon rien):

HIÉRARCHIE DE CHOMSKY

La hiérarchie de Chomsky est une classification des langages décrits par les grammaires formelles proposée en 1956, par le linguiste Noam Chomsky. Elle est aujourd'hui largement utilisée en informatique, en particulier pour la conception d'interpréteurs ou de compilateurs, ou encore pour l'analyse des langages naturels.

LANGAGE FORMEL

Définition (simpliste): Dans de nombreux contextes (scientifique, légal, etc.) l'on désigne par "langage formel" un mode d'expression plus formalisé et plus précis (les deux n'allant pas nécessairement de pair) que le langage de tous les jours (voir langage naturel).

1. D'un ensemble de mots obéissant à des règles logiques (grammaire formelle ou syntaxe) strictes.

2. Éventuellement d'une sémantique sous-jacente (la force des langages formels est de pouvoir faire abstraction d'une telle sémantique, ce qui rend les théories réutilisables dans plusieurs modèles)

Remarque: Ainsi, alors qu'un calcul particulier de paye ou de matrice inverse restera toujours un calcul de paye ou de matrice inverse, un théorème sur les groupes s'appliquera aussi bien sur l'ensemble des entiers que sur les transformations du cube de Rubik.

Le langage formel d'une discipline scientifique c'est donc effectivement un langage obéissant à une syntaxe formelle stricte et qui va servir à exposer des énoncés de manière précise, si possible concise et sans ambiguïté, et s'oppose en cela au langage naturel.

Le langage formel a pour avantage de rendre aisées la manipulation et la transformation de ces énoncés. En effet, on va disposer en général de règles de transformation précises (développement de formules logiques, formes normales, contrapositions, commutativité, associativité, etc.) qui peuvent être appliquées sans même connaître la signification de l'énoncé à transformer ou la signification de la transformation. C'est donc un outil d'exploration puissant, et c'est le seul langage qui permette aux machines de "faire des mathématiques".

L'inconvénient est évident: ne pas connaître le sens de l'énoncé empêche de savoir quelles sont les transformations pertinentes et nuit à l'intuition du raisonnement. Ainsi, il est bon de savoir lire rapidement un énoncé en langage formel et de le traduire tout aussi rapidement en un ou plusieurs énoncés du langage naturel, plus parlants.

C'est là que se trouve la limite de ce que nous appelons les "logiciels d'aide à la preuve": naturellement, l'ordinateur n'a pas d'intuition. Toute l'habileté du concepteur d'un tel programme consiste à trouver des moyens pour que l'ordinateur comprenne.

Donner un sens pertinent à un langage de programmation en vue d'exécuter ses programmes est relativement aisé, du fait que ces langages formels ont été conçus pour signifier des suites d'actions élémentaires de la machine. Pour prouver un programme (démontrer que l'algorithme se termine en un nombre fini de fois) ou un théorème de mathématiques (ce qui revient au même), il n'y a, en revanche, aucune méthode infaillible, la correction d'un programme étant un problème de décision indécidable. Ainsi, le prouveur doit se contenter d'appliquer certaines heuristiques (technique consistant à apprendre petit à petit en tenant compte de ce qui a été fait au préalable) et souvent appeler à l'aide l'utilisateur humain. Cependant, grâce à ses heuristiques et à sa puissance de calcul, l'ordinateur explore des milliers de voies que l'utilisateur humain n'aurait pas pu tester en plusieurs années, accélérant ainsi le travail du mathématicien.

Définition (un peu plus formelle): En tant qu'objet d'étude, un "langage formel" est défini comme un ensemble de mots de longueur finie (c.-à-d. de chaînes de caractères) déduits d'un certain alphabet fini, c'est-à-dire une partie du monoïde libre (l'ensemble des mots formé sur un alphabet, muni de la loi interne de concaténation (qui est une loi de composition), est un monoïde que nous appelons monoïde libre, dont le mot vide est l'élément neutre) sur cet alphabet.

Remarque: Il faut tout de même que cet ensemble de mots ait un sens, soit pertinent, soit opérationnel, serve à quelque chose. Sinon toute collection de groupements finis de caractères sera un langage formel. En somme que ces mots puissent s'articuler entre eux pour former sens, ou du moins construire une pensée, une démarche, un mécanisme logique, une technique de calcul...

SYNTAXE

Définition: La "syntaxe" est la branche de la linguistique qui étudie la façon dont les "morphèmes libres" (les mots) se combinent pour former des "syntagmes" (nominaux ou verbaux) pouvant mener à des propositions, lesquelles peuvent se combiner à leur tour pour former des énoncés.

Le syntagme "une modeste maison de briques rouges" est englobé dans le syntagme supérieur, c'est-à-dire, la phrase complète. Mais ce même syntagme "une modeste maison de briques rouges" inclut parmi ses éléments, le syntagme inférieur "de briques rouges", complément du nom "maison".

D1. En grammaire scolaire, une "proposition" est un syntagme articulé autour d'un verbe. Cette notion est surtout utilisée dans l'apprentissage des langues.

D2. Un "énoncé", en linguistique est tout ce qui est prononcé par un locuteur entre deux pauses. Syntaxiquement, l'énoncé peut donc s'étendre du simple mot à la phrase (voire au discours) en passant par le syntagme.

Le terme de syntaxe est aussi utilisé en informatique, où sa définition est similaire, modulo une terminologie différente. Ainsi la syntaxe est le respect, ou le non-respect, de la grammaire formelle d'un langage, c'est-à-dire des règles d'agencement des lexèmes (qui, en informatique, ne sont que des entités lexicales) en des termes plus complexes, souvent des programmes. Dans la théorie des langages formels, ce qui joue le rôle de lexème est en général appelé "lettre" ou "symbole", et les termes produits sont appelés "mots".

D'un point de vue purement grammatical, l'étude de la syntaxe concerne trois sortes d'unités:

U2. Le mot, qui en est le constituant de base, parfois appelé "élément terminal"

Les relations syntaxiques entre ces différentes unités peuvent être de deux ordres:

O2. La subordination dans le cas contraire (lorsqu'il y a subordination, l'élément subordonné remplit une fonction syntaxique déterminée par rapport à l'unité de niveau supérieur)

L'étude de la syntaxe tiendra compte, notamment, de la nature (ou catégorie ou espèce) des mots, de leur forme (morphologie) et de leur fonction. C'est ainsi que l'on parlera plus généralement de rapports morphosyntaxiques.

GRAMMAIRE FORMELLE

Définition (simpliste): Une "grammaire formelle" est un formalisme permettant de définir une syntaxe et donc un langage formel, c'est-à-dire un ensemble de mots sur un alphabet donné.

La notion de grammaire formelle est particulièrement utilisée dans les domaines suivants:

Pour définir une grammaire, nous avons besoin (voir l'exemple plus bas pour comprendre):

E1. Nous pouvons définir des expressions arithmétiques de la façon suivante (écritures que nous retrouvons fréquemment en théorie de la démonstration):

Les non-terminaux sont ici implicitement exp et num, les terminaux sont + , * ,(,) et les chiffres. L'axiome est exp.

Une utilisation de cette grammaire (règle de production) peut-être la suivante:

E2. la syntaxe de la logique propositionnelle classique ou calcul des propositions peut se définir de la façon suivante (cf. chapitre de Théorie De La Démonstration):

1. Les grammaires linéaires gauches qui produisent les mêmes langages que les expressions régulières (c'est ce qui va nous intéresser dans ce chapitre)

3. Les grammaires contextuelles (ce type de grammaire requiert un formalisme mathématique et ne peut être défini sans celui-ci)

Un langage est ainsi un ensemble de mots, qui sont simplement des séquences de symboles choisis dans un ensemble fini appelé "alphabet". Les langages de la hiérarchie de Chomsky sont formés de mots qui respectent une grammaire formelle particulière. Ce qui les distingue dans le cadre de la classification est la nature de la grammaire.

Remarque: Le plus souvent, les symboles que l'on considère sont formés de plusieurs caractères, de sorte qu'ils correspondent plutôt à ce que l'on appelle des mots dans la langue courante. Lorsqu'il y a ambiguïté, par exemple en analyse lexicale (vocabulaire) et syntaxique (partie de la grammaire qui traite de la fonction et de la disposition des mots et des propositions dans la phrase), on parle de caractères pour les symboles de l'alphabet utilisé pour coder les informations, et de lexèmes pour les symboles de l'alphabet abstrait, qui sont les unités de base du langage. De même, les mots du langage correspondent plutôt à des phrases ou à des textes.)

Définition (plus formelle): Une "grammaire formelle", ou simplement "grammaire", est formée d'un ensemble fini de symboles terminaux (qui sont les lettres ou les mots du langage), d'un ensemble fini de non-terminaux, d'un ensemble de productions dont les membres gauches et droits sont des mots formés de terminaux et de non-terminaux, et d'un axiome. Appliquer une production consiste à remplacer son membre de gauche par son membre de droite ; l'application successive d'un certain nombre de productions s'appelle une dérivation. Le langage défini par une grammaire est l'ensemble des mots formés uniquement de symboles terminaux qui peuvent être atteints par dérivation à partir de l'axiome.

La hiérarchie de Chomsky est formée des quatre niveaux suivants, du plus restrictif au plus large.

N1. Les "langages de type 3", ou "langages réguliers": ce sont les langages définis par une grammaire régulière ou une expression régulière, ou bien encore les langages reconnus par un automate fini.

N2. Les "langages de type 2", ou "langages algébriques": ce sont les langages définis par une grammaire formelle hors-contexte, ou bien encore les langages reconnaissables par un automate à pile non déterministe. Dans cette catégorie se trouvent les langages de programmation informatique.

N3. Les "langages de type 1", ou "langages contextuels": ce sont les langages définis par une grammaire contextuelle, ou encore les langages reconnaissables par une machine de Turing non-déterministe à ruban de longueur bornée par un multiple fixé de la longueur du mot d'entrée (ce type de langages requièrent un formalisme mathématique et ne peuvent être définis sans celui-ci).

N4. Les langages de type 0, ou "langages récursivement énumérables". Cet ensemble inclut tous les langages définis par une grammaire formelle. C'est aussi l'ensemble des langages acceptables par une machine de Turing (que l'on autorise à boucler sur un mot qui n'est pas du langage).

Remarques:

R1. Outre les 4 types de la hiérarchie de Chomsky, il existe des classes intermédiaires remarquables: entre 3 et 2: les langages non-contextuels déterministes, reconnaissables par automate à pile déterministe et les langages compris entre 1 et 0: les langages récursifs, c'est-à-dire reconnaissables par une machine de Turing (celle-ci doit refuser les mots qui ne sont pas du langage).

R2. Les six types ci-dessus sont strictement inclus les uns dans les autres.

Un analyseur pour un langage formel est un programme informatique qui décide si un mot donné en entrée appartient ou non au langage, et éventuellement en construit une dérivation.

On dispose de méthodes systématiques pour écrire des programmes d'analyse des langages de type 2 ou 3. Les interpréteurs ou compilateurs comprennent presque toujours une phase d'analyse lexicale, qui consiste à reconnaître des langages de type 3, suivie d'une phase d'analyse syntaxique qui est une analyse de langage de type 2.

Nous pouvons maintenant de manière vulgarisée (toujours dans l'objectif de préparer le terrain) définir ce qu'est un automate dans le cadre de la hiérarchie de Chomsky.

AUTOMATES ASSOCIÉS

Définition (simpliste): Dans le domaine de l'informatique, un "automate" est une machine à traiter de l'information par un modèle formel (une machine de Turing) sur un langage donné. Ainsi:

1. Sur un "langages fini" (langage contenant un nombre fini de mots), l'automate associé est une machine comparant un texte avec celui qui est enregistré dans une mémoire morte. La grammaire associée à un langage fini est une liste des mots du langage.

2. Sur un "langage régulier" (langage où la correction syntaxique se vérifie en ne mémorisant qu'un nombre fini d'informations), l'automate associé est "l'automate fini déterministe" (c'est-à-dire que, pour chaque mot entré, il n'existe qu'un parcours possible du graphe) ou "l'automate fini indéterministe". La grammaire associée à un langage régulier est une grammaire linéaire gauche.

3. Sur un "langage algébrique" (langage où la principale contrainte syntaxique est le parenthésage), l'automate associé est "l'automate à piles indéterministe". La grammaire associée est la grammaire algébrique.

4. Sur un "langage borné" (description nécessitant un formalisme mathématique), l'automate associé est "l'automate linéairement borné". La grammaire associée est la grammaire contextuelle.

5. Sur un "langage décidable" (un être intelligent arrive à trouver un procédé pour savoir si on est ou pas dans le langage), l'automate associé est une machine de Turing qui s'arrête sur toutes les données. Il n'y a aucune grammaire associée.

6. Sur un langage "semi-décidable" (un être intelligent arrive à trouver un procédé pour savoir si on est dans le langage, mais peut rester dans l'expectative si on est à l'extérieur d'un tel langage), l'automate associé est la machine de Turing (donc contient des structures conditionnelles et des boucles). Les grammaires associées sont des grammaires "semi-Turingienne", "de Vangarden", ou "grammaires affixes".

TERMINOLOGIE

Les automates travaillent donc essentiellement sur des lettres, mots, phrases et langues. Afin de construire des méthodes d'analyses et de traitement rigoureuses et optimales sur le sujet il est intéressant de formaliser les objets traités. C'est ce que nous allons faire dans un premier temps en définissant ceux-ci et leurs propriétés mathématiques (qui sont très intuitives).

MOTS

D1. Un "alphabet" est un ensemble dont les éléments sont des "lettres". Les alphabets sont toujours supposés finis.

D4. La "longueur" d'un mot w est le nombre de lettres qui le composent, et est notée

(le mot vite est le seul mot de longueur 0).

Le "produit de concaténation" de deux mots equation

est le mot xy obtenu par juxtaposition (concaténation):

Les gènes sont des mots sur l'alphabet ACGT, les protéines sont des mots sur un alphabet à 20 lettres. Les entiers naturels, écrits en base 10, sont des mots sur l'alphabet des dix chiffres décimaux...

Soit A un alphabet. Soit B une partie de A. Pour tout mot equation

, la longueur en B de w est le nombre d'occurrences de lettres de B dans le mot w. Ce nombre sera noté

Remarque: En particulier, nous avons trivialement

D1. Un mot u est un "préfixe" ou "facteur gauche" d'un mot v s'il existe un mot x tel que

. Le mot u est "préfixe strict" ou "propre" si, de plus,

. De manière symétrique, u est "suffixe" ou "facteur droit" de v si

pour un mot x. Si

, alors u est "suffixe strict" ou "propre". Le nombre de préfixes d'un mot v non vide est

(le mot vide étant toujours un préfixe, nous avons toujours n'importe quel mot non vide qui a comme préfixe au moins le mot vide).

Lemme de Levy: Soient x, y, z, t des mots tels que equation

. Alors il existe un mot w tel que:

Il en résulte logiquement en particulier que si equation

, le mot w est vide, et donc equation

. En d'autres termes, un monoïde libre (voir le rappel plus bas) est simplifiable à gauche et à droite.

Rappel: Dans le cadre des automates un "monoïde libre" est un ensemble A (l'alphabet), dont les éléments sont les lettres.

Remarque: Dans la section d'arithmétique, chapitre de théorie des ensembles, nous parlions simplement de "monoïde". Le monoïde equation

LANGAGES

Les sous-ensembles de

sont appelés des "langages formels". Par exemple, pour equation

, l'ensemble equation

est un langage.

Nous définissons sur les langages plusieurs opérations. Les opérations ensemblistes sont l'union, l'intersection, la complémentation et la différence qui s'en déduit. Si X et Y sont deux parties de

, alors:

Remarque: Nous avions bien évidemment equation

Suite à la demande d'un lecteur détaillons la 6ème ligne en rappellant la définition:

et dans le produit de concaténation des deux langages X et Y, les seuls mots où nous trouvons les éléments {0,1} du langage Z en tant que préfixe sont:

et comme par définition

est l'ensemble unique des termes w qui suivent les préfixes que constitue les termes de Z il ne reste alors plus que:

P2.

où l'inclusion est généralement stricte. Pour conceptualiser cette propriété, il ne faut surtout pas oublier que X est un ensemble de mots et que Y, Z n'ont pas nécessairement des mots de la même longueur !

ÉQUATIONS

D'abord voyons un petit quelque chose dont nous allons avoir besoin par la suite: soient u et v deux mots non vides. Les trois conditions suivantes sont équivalentes (sans démonstration car assez trivial de tête):

Remarque: Rappelons à nouveau que nous n'avons pas forcément equation

mais que nous pouvons très bien avoir equation

Passons maintenant aux choses intéressantes (certains points flous du chapitre de théorie de la démonstration peuvent s'éclaircir ici parfois...):

D1. Soient V et A deux alphabets disjoints (vous pouvez les imaginer comme l'ensemble des variables et respectivement celui des constantes par exemple...). Une "équation en mots" avec constantes sur A est un couple equation

de mots de equation

. Une telle équation est représentée par

. Il faut donc voir les deux mots choisis comme le membre de gauche et respectivement de droite d'une équation

D4. Une "solution" de l'équation e est un homomorphisme de monoïde (cf. chapitre de Théorie Des Ensembles) equation

invariant (car toute lettre sur A est envoyée sur

et par conséquent tout mot sur A est envoyé sur A) sur A tel que:

définissons h tel qu'il envoie x sur b, y sur a, a sur a, b sur b. Dès lors nous avons bien:

D5. Une solution h est dite "solution cyclique" s'il existe un mot w (appartenant à A) tel que

(en considérant le mot lui-même comme un alphabet donc) pour toute variable x.

Remarque: Selon cette définition, les solutions de l'équation sans constantes equation

en deux variables x,y sont cycliques telles que:

equation (62.38)

CODES

Définition: Nous appelons "code" toute partie C d'un monoïde libre

qui vérifie la condition suivante pour tout (mot)

En d'autres termes, C est un code si tout mot de

(mot composé de mots) se factorise, de manière unique, en un produit de mots de C. Lorsqu'un ensemble n'est pas un code, nous nous en apercevons en général assez facilement.

E1. L'ensemble (langage) equation

n'est pas un code puisque le mot aba s'écrit à la fois comme produit equation

et comme produit equation

Remarque: Les codes les plus simples sont les "codes uniformes". Ce sont des ensembles dont tous les mots ont une même longueur (ce qui fait qu'étant donné que chaque mot est différent, la combinatoire des mots peu très difficilement ne pas différer).

E2. L'ensemble

des mots de longueur n est un code, si equation

. Le code ASCII qui associe à certains caractères des mots binaires de longueur 7 (voir table ASCII) est un code uniforme.

CODES PRÉFIXES

Le morse code la lettre E, la plus fréquente, par un '.' et la lettre Y, plus rare, par '-.--': c'est un exemple de code de longueur variable, ce qui permet de représenter les lettres ou les mots les plus fréquents par des mots plus courts. Une propriété importante est l'unicité du décodage (application injective), problème qui ne se pose pas pour les codes de longueur constante. Il peut être résolu, mais de façon trop coûteuse, quand un symbole spécial sépare deux mots successifs du code (le blanc dans le cas du morse).

On peut ne pas recourir à cette technique si aucun mot du code n'est le préfixe d'un autre mot du code; un code présentant cette propriété est appelé un "code préfixe".

Supposons que nous décidons d'une convention de code à taille variable, qui fait correspondre, entre autres, les valeurs suivantes:

Et maintenant, nous sommes bien embarrassés! Avec plusieurs possibilités équivalentes entre lesquelles on ne sait pas trancher, on est incapable de retranscrire le code initial.

Le problème qui s'est posé ici est que certains codes sont le début d'autres codes. Ici, "11" est le code du nombre 0, mais c'est aussi le début de "11010", code du nombre 2. D'où l'ambiguïté.

Nous appelons alors "code-préfixe" un codage dans lequel aucun code n'est le début d'un autre. Ainsi, pour qu'il n'y ait aucune ambiguïté au moment du décodage, il nous faut absolument un code-préfixe.

L'ensemble

est un code. Ici, la connaissance du début abababa ne permet pas encore de savoir si la décomposition commence par

ou par

. Ce n'est qu'après la lecture de la lettre suivante (non encore indiquée dans l'exemple) que l'on sait si la décomposition commence par ab (si la lettre est b) ou par ababa (si la lettre est a)

Définition: Un code est à "délai de déchiffrage fini" s'il existe un entier d tel que, chaque fois qu'un message w commence par

avec

alors la factorisation complète de w commence par

. C'est donc après un "délai" de d mots de code que nous pouvons affirmer que le premier mot trouvé est le bon.

ALGORITHMES LINGUISTIQUES

Mettons un peu en pratique ce qui a déjà été vu jusqu'ici afin de nous appuyer un peu sur du concret "utile" ! Nous verrons plus loin une fois les automates introduits, quelques algorithmes de recherche de sous-chaînes (tels qu'utilisés en génomique).

ALGORITHME DE HUFFMAN

Rappel: en informatique, nous décidons de coder un nombre entier compris entre 0 et 255 par une séquence de 8 chiffres binaires (binary digits, ou "bits" en anglais, valant 0 ou 1), encore appelée octet.

A priori, il suffit pour cela de se donner une table de correspondance du genre:

La correspondance peut être quelconque, dictée par notre imagination, du moment qu'à chaque entier entre 0 et 255 est affecté un code binaire et un seul. Une fois une correspondance fixée, il suffit de la prendre comme convention.

En pratique, la convention qui a été choisie est celle de la représentation en base 2. Elle a le mérite d'être naturelle et logique. Dans la table ci-dessus, 10001010 est la représentation en base 2 de 138. C'est la manière de noter les chiffres que nous aurions adoptée si nous n'avions que deux doigts au lieu de dix.

L'octet défini selon cette convention est l'unité de base de stockage des données. Tout fichier informatique est une suite d'octets rangés selon un ordre bien défini. La taille du fichier est simplement le nombre d'octets qui le constituent. Le kilo-octet (Ko) correspond à 1024 (et non pas 1000) octets, le méga-octet (Mo) à 1024*1024 octets (convention absurde des informaticiens).

Il convient de noter que cette représentation en base 2, n'est qu'une convention. D'autres conventions sont possibles, qui conviendraient tout autant pour peu que tout le monde s'accorde à employer la même convention.

Le problème que nous nous posons est: y aurait-il une autre manière de coder les chiffres, peut-être moins logique mais plus judicieuse, de telle manière que la taille du même fichier réécrit selon la nouvelle convention, serait moins grande?

La convention de codage binaire est finalement très démocratique: que vous soyez un Zéro ou un DeuxCentCinquanteCinq, nous vous allouons 8 bits de toute manière pour pouvoir vous coder. Autrement dit, chaque entrée possible (un nombre entre 0 et 255) est codée sur 8 bits. Il s'agit d'un codage à taille fixe.

Du point de vue de notre problème (la compression de données), cela ne nous importerait pas si chacune des valeurs possibles (0 ... 255) était représentée aussi fréquemment que les autres. Mais en général c'est n'est pas le cas.

À titre d'exemple, voir l'analyse des octets du fichier Wordpad.exe (cf. dans votre dossier Accessoires...). Dans ce tableau, en abscisse comme en ordonnée sont portées les valeurs possibles d'un octet donné (donc 0 ... 255). Sur la diagonale, à l'abscisse et ordonnée correspondante la taille du cercle est proportionnelle au nombre d'octets ayant cette valeur dans le fichier:

Nous voyons clairement que les valeurs 0, 128 et 255 sont nettement plus fréquentes que les autres!

Nous allons maintenant décider d'une convention de codage à taille variable, qui représente une valeur fréquente par un petit nombre de bits, et une valeur peu fréquente par un grand nombre de bits.

Par exemple, 0 sera maintenant représenté par la séquence "11" (anciennement "00000000"), 128 par "1011010" (anciennement "10000000"), 255 par "0100" (anciennement "11111111"), etc.

Étant donné que 0 représente à lui seul un tiers du fichier, nous avons gagné une place considérable en le codant sur deux bits au lieu de huit! Et idem pour les autres valeurs fréquentes...

L'algorithme de Huffman est une recette pour générer un code-préfixe à taille variable, à partir de la table des fréquences d'une suite de valeurs. Donc, si vous nous avez bien suivis dans la théorie jusqu'ici, c'est une solution à notre problème.

Supposons que notre fichier soit extrêmement simple, et constitué d'un mot unique:

Il y a 25 caractères dans ce fichier; chaque caractère étant codé par un octet de 8 bits (codage ASCII) cela signifie donc 25 octets, ou encore 200 bits. Voyons ce que nous pouvons faire de cela.

Tous les autres octets ont une fréquence nulle: ils ne sont pas représentés dans le fichier.

Première étape, nous créons maintenant un "noeud terminal" pour chaque entrée du tableau:

Nous commençons maintenant une itération: à chaque fois nous supprimons les deux arbres de gauche et les remplaçons par un "arbre somme". Le nouvel arbre est inséré dans la liste en respectant l'ordre croissant, et l'on recommence jusqu'à ce qu'il ne reste plus qu'un seul arbre:

Maintenant, le code associé à chaque Clé n'est autre que le chemin d'accès au noeud terminal correspondant, depuis la racine, en notant 0 chaque branche de gauche et 1 chaque branche de droite.

110000001100110011101001111100110001111111011001101000010111101110101111101010001

ce qui nous fait 81 bits, au lieu de 200 au départ! Cela correspond à un taux de compression de 60%.

Le fait d'avoir généré un code en se servant d'un arbre binaire assure qu'aucun code ne peut être le préfixe d'un autre. Vous pouvez vérifier qu'à l'aide de la table de codage, il n'y a aucune ambiguïté possible pour décoder notre mot compressé!

En pratique, la table de codage étant spécifique à chaque fichier, il est indispensable de l'incorporer au fichier compressé, de manière à ce que le décryptage soit possible. Ce qui signifie que la taille du fichier compressé doit être augmentée d'autant. Dans le cas de notre fichier exemple, il faudrait incorporer au minimum 22 octets de plus pour insérer la table de codage, et le taux de compression n'est plus aussi bon.

Toutefois, pour des fichiers suffisamment larges (à partir de quelques kilo-octets) le surplus de taille généré par la table de codage devient négligeable par rapport à l'ensemble du fichier. Concrètement, l'algorithme de Huffman permet d'obtenir des taux de compression typiques compris entre 30% et 60%. Sans être aussi bien que ce que réalise Winzip (en moyenne 20% de mieux), c'est déjà pas mal!

ALGORITHME DE SARDINAS ET PATTERSON

Face à de longs codes, la difficulté est de vérifier si un code en est vraiment un... Pour cela, nous pouvons utiliser l'algorithme de Sardinas et Patterson (la démonstration de cet algorithme se fera lors de la prochaine mise à jour de ce chapitre).

Pour ce faire, nous construisons un graphe

, où P est l'ensemble des préfixes non vides (selon la définition des "préfixes" donnée plus haut) de mots de X, et U l'ensemble des couples (u, v) tels que l'un ou l'autre des possibilités suivantes soient satisfaites:

Pour

, l'ensemble P contient, en plus de X (qui sont préfixes de

), les mots

(respectivement préfixes de

)

où les sommets correspondants aux mots de X sont doublement cerclés. L'étiquette de chaque arc est un mot de l'ensemble X. Les "arcs croisés" sont tracés en pointillés et les "arcs avant" en traits pleins. Si l'arc

est croisé, alors l'étiquette est uv, sinon c'est le mot x tel que ux=v.

Dans notre exemple, il y a un chemin qui part de a et arrive en a. En vertu du théorème de Sardinas et Patterson (que nous démontrerons lors de la prochaine mise à jour de ce chapitre), l'ensemble X n'est pas un code (il suffit d'un seul et unique chemin entre deux sommets quelconques de X).

L'ensemble X est un code si et seulement si il n'y a pas de chemin non trivial dans

d'un sommet de X à un sommet de X (en d'autres termes, un ensemble X est un code si et seulement si il n'y a que le seul et unique chemin trivial qui mène d'un sommet de X à un autre - ce sommet pouvant être le même comme dans l'exemple précédent).