Grammaires et automates. Programmation d'une liste d'orpérations sur les automates et les grammaires

Dans un langage formel d'alphabet très vaste, A, qui représente l'ensemble des caractères du web (l’Unicode), on assimile les états de l'automate aux caractères, E=A. (Pour saisir un caractère à partir de son code Unicode hexadécimal : Ctrl+Maj+U suivi du code puis Entrée.)

Un automate déterministe est une fonction de E×A->E.

On définit un automate déterministe par une string. La string comprend une liste de mots séparés par le caractère séparateur, et commence par ce caractère séparateur :

    1) Le premier caractère de la string indique qu'elle est le caractère qui est utilisé comme caractère séparateur. On choisira souvent ¡ (le caractère U+00A1).

    2) Le premier mot contient un caractère désignant l'état initial.

    3) Le second mot désigne la liste des états acceptant.

    4) Les mots suivants désignent des arêtes. Une arête est définie par un mot de trois caractères, le premier caractère désigne l'état de départ de l'arête, le second caractère désigne l'état d'arrivé de l'arête, le troisième caractère désigne le caractère devant être lu pour effectuer cette transition.

Exemple : x¡xz¡xya¡xzb¡yza¡zxb

Puis on programme un compilateur d'automate, L'automate compilé est une fonction de A*->{0,1}. il prend en entrée un mot et retourne 1 si il reconnaît le mot, et il retourne 0 sinon.

Les fonctions sont programmés dans un premier mode comme des fonctions go, ayant vocation à être appelées dans un programme écrit en go, puis elles sont programmées une seconde fois dans un second mode comme des fonctions en ligne de commande, ayant vocation à être appelées dans un terminal.

On programme une synopsie, c'est à dire des exemples illustratifs qui couvrent toutes les fonctionnalités. Chaque exemple affichant son code d'appel, les arguments exemples, le résultat, et sa description.

Un automate non-déterministes et une fonction de E×A*->P(E).

On définit un automate non-déterministe en étendant la définition précédente. On définir un automate déterministe par une string. La string comprend une liste de mots séparés par le caractère séparateur, et commence par ce caractère séparateur :

    1) Le premier caractère de la string indique qu'elle est le caractère qui est utilisé comme caractère séparateur. On choisira souvent ¡ (le caractère U+00A1).

    2) Le premier mot contient la liste des états initiaux possibles.

    3) Le second mot désigne la liste des états acceptant.

    4) Les mots suivants désignent des arêtes. Une arête est définie par un mot d'au moins deux caractères. le premier caractère désigne l'état de départ de l'arête, le second caractère désigne l'état d'arrivé de l'arête, les caractères suivant désignent le mot devant être lu pour effectuer cette transition.

Exemple : x¡xy¡xya¡xz¡yzab¡zbbx

Puis on programme la transformation d'un automate indéterministe en un automate déterministe.