L'étude des langages formels nous dévoile la hierarchie de Chomsky, une hierarchie des langages associés à une hierarchie des automates qui les reconnaissent. La notion de calculabilité est ainsi abordée par l'intermédiaire des automates. Et on commence par l'automate le plus simple qui est l'automate déterministe qui reconnait les langages rationnels, puis l'automate non-déterministe qui en est une version de composition plus libre, puis l'automate à pile qui reconnait les langages algébriques, puis l'automate à ruban qui est une machine de Turing et que l'on scinde en deux types de programme : L'automate à ruban à borne linéaire c'est à dire où la taille du ruban est bormé par `ax+b` où `a` et `b` sont des constantes et où `x` est la taille du mot d'entré, et qui reconnait les langages contextuels. Et l'automate à ruban non borné linéairement, et qui reconnait les langages récursivementénumérable que nous appelons simplement les langages calculables.
Les automates sont assimilables à des programmes informatiques. Nous allons définir un ensemble d'opérations sur ces automates, et chercher à les utiliser comme outils de programmation. Nous allons développer un framework.
Les mathématiques mettent en exergue un langage plus spécifique qu'est le langage d'opérateurs d'arité fixe. C'est un langage algébrique. Quel correspondance y-a-t-il entre la procédure d'unification de termes (qui est de complexité linéaire) dans un langage d'opérateurs et le fonctionnement d'un automate ?.
La première brique logiciel consiste à programmer un automate déterministe. C'est un automate qui lit un mot en une seul fois sans revenir en arrière et qui répond oui ou non s'il accepte le mot. Et il peut parfois répondre oui ou non avant d'avoir fini de lire complètement le mot. Ces automates reconnaissent les langages rationnels.
L'automate est un graphe orienté sur un ensemble d'états où chaque arête est étiqueté d'un caractère qui correspond au caractère lu par l'automate pour effectuer cette transition d'état en prenant cette arête. L'automate étant déterministe, pour chaque état, il ne doit pas y avoir deux arêtes partantes ayant le même caractère comme étiquette. L'automate étant déterministe, il ne possède qu'un état initial. Parcontre la lecture du mot peut s'arrêter sur plusieurs états possibles qui sont alors appelés les états acceptant.
Se pose la question de savoir comment représenter un automate de `n` états utilisant un langage de `m` caractères. La représentation la plus basique consiste en un triplet comprenant l'état initial, les états finaux, et les arêtes de l'automate.
Puis on fait un compromis avec l'exigence d'une lecture humaine. Les caractères sont les caractères lisibles du web mondial, un immense alphabet `A`, où chaque caractère est désigné par un code entier, qui est l'unicode et qui tient sur 4 octets, un mot de 32 bits.
Les états sont représentés de la même façon par des caractères. Pourquoi ce choix ? parceque l'on choisie d'appliquer l'heuristique du moindre effort par le choix de la plus grande unification possible. Autrement dit, on s'inspire de la philosophie élémentarienne qui affirme que le modèle le plus général parmi plusieurs modèles se contenant entre eux est par principe celui qui a la définition la plus simple.
Rappellons les principes de base du développement qui accompagne Unix et Linux, la philosophie Unix :
Tout est fichier
Les exécutables sont des fichiers normaux, et qui peuvent être stockés en mémoire vive ou sur un périphérique d'accès plus lent mais plus pérenne.
Les données sont du texte
Un fichier texte peut être lu par les autres outils unix, et donc respecte de principe "faire une chose et le faire bien". Il peut être lu par un être humain et donc respecte le principe "kiss". Un fichier texte permet une interopérabilité avec d'autres systèmes. Un fichier texte facilite le débugage.
KISS (Keep it simple, stupid !)
Il s'agit ici de disposer d'outils très simples. Plus c'est simple mieux c'est. Ce n'est pas que l'utilisateur soit stupide, c'est qu'il n'a aucune raison d'aller perdre du temps à comprendre le fonctionnement de quelque chose qui est fondamentalement simple. Qui dit outils simples, dit faciles à manipuler, faciles à réutiliser.
Mais on ne parle pas seulement d'usage ici. Il s'agit aussi de garder le code simple, trivial. Cela s'applique aussi aux commentaires dans le développement. Si votre code est bien écrit, bien architecturé, simple, alors il sera aussi simple à lire, à maintenir et à débuger, pas besoin de milliers de lignes de commentaires.
Faire une chose et le faire bien
Unix a inventé le pipe '|', une méthode simpliste pour faire communiquer 2 programmes entre eux. Cette communication est unidirectionnelle et non formatée, seules des données brutes y passent. Et pourtant, à lui seul le pipe a fait beaucoup plus pour unix que n'importe qui. Grâce au pipe et au fait que la plupart des programmes communiquent avec un format texte, il est possible de faire des programmes qui ne soient que des filtres, qui ne fassent qu'une chose sur les données qu'on leur donne, et qui le fassent bien. Cela assure un moyen simple et efficace de communiquer avec les autres logiciels unix. Ainsi vous garantirez une utilisation bien plus large à votre produit que celle que vous aviez dans la tête. Et puisque les autre outils sont déjà des outils simples qui font une chose et bien, vous pouvez aussi les réutiliser et vous appuyer sur les épaules d'un géant.
Ainsi nous pourrions programmer nos automates comme des simples commandes linux pouvant se combiner librement dans un interpréteur de commande tel que le shell bash. Mais pourquoi faudrait-il absolument s'appuyer sur cet interpréteur ? Autant prendre ce qui se fait de mieux, tel le shell ruby, qui offre un interface de programmation de script d'une grande puissance et d'une grande facilité, en gèrant de façon quasi-exhaustive toutes les normes de codage de caratères. Cela peut se faire sans changer radicalement de philosophie Unix. Par contre l'accès au commande système se fait toujours par le shell Bash, appelé par le shell ruby, faisant que le shell ruby n'est en fait qu'un interface s'intercalant entre le shell Bash et notre framework, l'ensemble des outils que nous voulons développer. C'est pourquoi en l'état de nos connaissances informatiques, les deux types de développement doivent être explorés.
L'ensemble des états `E` est posé par principe égal à l'alphabet `A`. Mais on garde la distinction des types puisqu'ils correspondent à des fonctionnalités différentes. Et dans un automate, ces ensembles seront restreints aux seuls états et caractères présents dans l'automate. Concrètement cela signifie que l'automate en interne va renuméroter ses états de `1` à `n` et ses caractères de `1` à `m` dans un dictionnaire.
Les arcs de l'automate forme une fonction de `E"×"A"→"E` où l'ensemble des caractères `A` et indentique à l'ensemble des états `E` et constitue un très vaste alphabet commun, plus grand que le nombre d'états pour que tous les états de l'automate puissent être ainsi assimilés à des caractères. La fonction prend en argument un état et un caractère puis retourne un état. Et on préférera définir l'automate par une application, en réservant le caractère `ø` pour désigner un état spécial supplémentaire dit état zéro, dont la production par l'application indique que la fonction n'est pas définie.
Puis on veut programmer les automates sous forme d'outils linux en ligne de commande shell Bash. Un automate sera mémorisé sous forme d'une chaine de caractères. Le premier caractère est un caractère quelconque pour lequel on attribut le rôle spécial de caractère séparateur`,`, les caractères suivants sont la liste des états finaux, puis le caractère spéciale de séparation, puis une liste d'arêtes composé de trois caractères. Pour chaque arète, le premier caractère désigne l'état de départ, le deuxième caractère désigne l'état d'arrivé, et le troisième caractère désigne le caractère devant être lû pour effectuer cette transition d'état. Et les arètes sont séparées par le caractère spécial de séparation. Par exemple :
`«","x","xz","xya","xzb","yza","zxb»`
où
`«|x|xz|xya|xzb|yza|zxb»`
Puis on programme le moteur `"Moteur"` qui va appliquer un automate sur un mot et retrourner `0` s'il ne l'accepte pas, et `1` s'il l'accepte. Le programme `"Moteur"` s'utilise en ligne de commande linux shell Bash comme suit avec deux arguments :
`"Moteur" «","x","xz","xya","xzb","yza","zxb» «aabbb»`
Et veuillez ne pas omettre les caractère blanc entre `"Moteur"` et `«","x","xz","xya","xzb","yza","zxb»` et `«aabbb»`.
Mais cela ne nous satisfait pas, il nous faux définir un type d'object spécifique qu'est un automate. On définit le type `"Automate"`, qui joue le rôle le constructeur, et qui s'utilise en ligne de commande linux en shell Bash comme suit avec un seul argument :
`"Automate" «","x","xz","xya","xzb","yza","zxb»`
Et veuillez ne pas omettre le caractère blanc entre `"Automate"` et `«","x","xz","xya","xzb","yza","zxb»`
Mais on ne sait pas encore très bien ce que va retourner ce constructeur, peut-être qu'il retournera un exécutable nommé par un nom générique. On remarque alors qu'il n'est plus nécessaire que l'automate soit mémorisé en un seul mot, en un seul argument, et qu'il peut être défini par une liste d'arguments. On veut programmer les automates sous forme de fonction plus générale, telle que utilisable dans le shell Ruby. On définit le type `"Automate"` comme une fonction ce qui permet de donner un sens formel à l'expression fonctionnelle suivante qui définit un automate :
`"Automate"( «x»,«xz»,«xya»,«xzb»,«yza»,«zxb»)`
Et on remarque qu'une telle fonction peut se subdiviser en fonctions plus petites. En effet, on peut considérer un automate sans préciser ni son état de départ, ni ses états finaux autorisés. Cela correspond alors à un graphe étiqueté, où les sommets et les étiquètes sont pris dans un même ensemble `A`. Autrement dit, c'est une relation ternaire sur `A`.
Mais on ne s'intéresse pas à toutes les relations ternaires sur `A`, seulement celles qui sont déterministes c'est à dire telle qu'il ne doit pas y avoir deux arêtes de même étiquette et partant d'un même état, allant sur deux états différents. Notez que cette condition peut être réalisée après coup, soit en fusionnant ces états doubles, ou soit en occultant les occurences suivantes ce qui revient a appliquer la première règle opérationelle rencontrée, ou soit en occultant les occurences précédente ce qui revient a appliquer la dernière règle opérationelle rencontrée. C'est ce dernier choix que nous ferons, pour garder la possibilité de changer la relation en ajoutant des arêtes à la fin de la liste, et en considérant la liste comme chronologique.
Et il y a deux implémentations possibles d'une telle relation ternaire :
Puis l'automate s'applique à un mot, une séquence de caractères, et va procéder à des changement d'état. Cela indique donc qu'il existe une variable parente représentant l'état en cours de l'automate. Ainsi la fonction `"R3D"` construit une relation ternaire déterministe (qui est un graphe étiqueté tel qu'il n'existe pas deux arètes partant d'un même état avec une même étiquette) et se connecte à une variable parente désignant l'état en cours de l'automate, ou bien la définit si celle-ci n'existe pas encore en l'initialisant par défaut à `ø`, la seule valeur que nous avons pour l'instant sous la main.
Plus exactement la fonction `"R3D"` va compiler l'expression littérale de la relation ternaire, et connecter une variable d'état. Elle retourne `5` objets ; Un hachage pour les états utilisés, la liste correspondante des états utilisés, un hachage pour les caractères utilisés, la liste correspondante des caractères utilisés, et un tableau d'entiers.
`"R3D"(«xya»,«xzb»,«yza»,«zxb»)`
Ces `5` objets correspondent à des applications. On nomme `En` l'ensemble des numéros des états utilisés, et `An` l'ensemble des numéros des caractère utilisés. Nous avons :
Le hachage pour les états utilisés correspond à une application `t_E` de `A -> En`.
La liste correspondante des états utilisés correspond à l'application inverse `t_E^-1`, qui appartient à `En -> A`.
Le hachage pour les caractères utilisés correspond à une application `t_A` de `A -> An`.
La liste correspondante des caractères utilisés correspond à l'application inverse `t_A^-1`, qui appartient à `An -> A`.
Le tableau d'entiers correspond à une application `varphi` de `En"×"An->En`.
Puis l'application de l'automate à un caractère `alpha` correspond à changer l'état en cours `beta` comme suit :
`beta:= t_E^-1(varphi(t_E(beta), t_A(alpha)))`
On procède à une traduction, qui correspond à une compression. Autrement dit, on compresse les arguments, on effectue l'opération, puis on décompresse le résultat.
---- 31 août 2019 ----
Le but d'un automate est de reconnaitre un mot en effectuant un calcul de complexité linéaire selon la taille du mot. Appliqué à un mot, il retourne `1` s'il l'accepte et `0` sinon.
`"Automate"(x,xz,xay,xbz,yaz,zbx)(aab\b) |-- 1`
On programme cette opération que l'on nomme`"run"`. Elle prend deux arguments. Par exemple :
`"run" "Automate"(x,xz,xay,xbz,yaz,zbx) aab\b |-- 1`
Il lit la définition de l'automate et il la transforme en une représentation interne sous forme d'un tableau de caractères, une forme de compilation interne, puis procède à la lecture du mot. A chaque lecture d'un carcactère, il regarde si l'existe un arête partant de l'état en cours et ayant ce caractère commea libellé. Si c'est le cas, il change l'état en cours par le nouvel état figurant au bout de l'arête. Sinon il retourne `0` et s'arrête. Puis après avoir lu le dernier caractère et avoir changé son état en cours correspondant, il retourne la valeur d'acceptation de l'état en cours.
On peut compiler l'automate en un executable. On programme un compilateur nommé `"compile"`, en intégrant dans celui-ci la commande de compilation go.
`"compile" "Automate"{x,xz,xay,xbz,yaz,zbx} |-- "prog"`
`"prog" aab\b |-- 1`
Puis il convient de définir les automates non-déterministes. La différence tient dans le fait qu'un automate non-déterministe peut avoir plusieurs arêtes partant d'un même états et ayant le même caractère comme étiquette. Et dans le même esprit, il peut possèder plusieurs états initiales. On peut donc utiliser la même notation en liste d'arêtes. Puis il convient de permettre des compositions plus libres où les transitions peuvent correspondent à la lecture non pas d'un seul caractère mais d'une séquence de caractères, séquence qui peut aussi être la séquence vide. Une arête définie par plus de trois caractères ou par seulement deux caractères permet de définir ces différents cas. Le premier caractère désigne l'état de départ, le dernier caractère désigne l'état d'arrivé, et la liste des caractères indermédiaires désignent la séquence lue. Par exemple :
`xyz,xz,xaby,xb\bz,xaz,ybx`
L'automate non-déterministe est donc une fonction de `E"×"A"*""→"ccP(E)` où `A=E` est un très vaste alphabet, plus grand que le nombre d'états pour que tous les états de l'automate puissent être assimilés à des caractères. La fonction prend en argument un état et une séquence de caractères qui peut être vide, puis retourne un état.
Le types `"Automate"` s'étend aux automates non-déterministes, ce qui permet de donner un sens formel au mot suivant qui définit un automate non-déterministe :
`"Automate"(xyz,xz,xaby,xb\bz,xaz,ybx)`
L'automate non-déterministe peut-être vue comme une grammaire algébrique :
`"Grammaire"(x,y,z,x"→"epsilon,z"→"epsilon,x"→"aby,x"→"b\bz,x"→"az,y"→"bx)`
....
Un automate indéterministe peut être tranformé en un automate déterministe dans lequel les nouveaux états sous les ensembles d'états du premier automate.
...
...
La grammaire algébrique est un énumérateur des mot du langage algèbrique correspondant. L'ordre de déclaration des mots et des règles dans la grammaires a une importance car cela déterminera l'ordre exacte d'énumération par defaut des mots du langage.
La grammaire est une liste de mots quelconques et de règles de la forme suivante :
`X→ alpha`
où `X` désigne un caractère, et `alpha` désigne un mot.
L'ensemble des caractères utilisés comme premier terme d'une règle est appellé l'ensemble des variables.
Considérons la grammaire suivante décrite par une liste de mots et de règles :
`"Grammaire"(x,aybz,x"→"ya,y"→"by,y,z"→"yy,y"→"epsilon)`
Cet exemple peut se noter come suit :
`((x),(aybz),(x"→"ya),(y"→"by),(y),(z"→"yy),(y"→"epsilon))`
Et l'ordre des règles et mots dans la définition de la grammaire, va déterminer l'ordre précis d'énumération des mots.
Notez que l'on a utilisé 4 caractères spéciaux, les parenthèses`()` pour entourer la définition, la virgule pour séparer chaque règle ou mot, et le caractère de production `"→"`.
---- 9 septembre 2018 ----