Machine caractères pour automate
Automate d'états finis (AEF)
Nous disposons d'une machine virtuelle très réduite qui travaille sur des caractères. Cette machine est munie d'une mémoire et de deux registres numérique N1 et N2 pouvant contenir chacun un entier (0, 1, 2,) et de deux registres de caractère C1 et C2 pouvant contenir chacun un caractère (a, b, c).
Les instructions et leur définition sont les suivantes :
- (LOA <reg> <mem>) charge dans le registre <reg> le contenu de la case mémoire mem. mem est soit une valeur numérique litérale soit un registre numérique.
- (STO <mem> <reg>) qui écrit dans la case mémoire <mem> le contenu du registre <reg>.
- (INC reg) incrémente de 1 le registre numérique <reg>. (DEC <reg>) décrémente de 1 le registre numérique <reg>.
- (BEQ <reg1> <reg2> <adresse>) branche le pointeur de programme PC à l'adresse adresse si le contenu du registre reg1 est égale au contenu du registre reg2. Idem avec (BNE <reg1> <reg2> <adresse>) dans le cas d'inégalité. (BRA <adresse>) est le branchement inconditonnel à l'adresse adresse. Les étiquettes n'existent pas, adresse est soit une valeur numérique litérale soit un registre numérique.
- (STP) stoppe l'exécution.
Avec cette machine, on souhaite faire fonctionner des automates déterministes. À la fin de l'exécution, le registre N1 contient 1 si la chaîne candidate à tester appartient au langage reconnu par l'automate (et 0 sinon). Pour cela, il faut compiler des définitions externes d'automates en code de la machine.
Par exemple, l'automate A sur V={a,b} reconnaissant le langage :
a*ba*
peut avoir, par exemple, la définition (à la LISP) suivante :
((:voc a b) (:init 0) (:finals 1) (:trans (0 a 0 b 1) (1 a 1))).
L'ordre des champs importe peu, ils sont uniquement repérés par leur mot-clé. Pour le champs :trans tous les états sont indiqués (même ceux qui n'ont aucune transition). Il n'y a toujours qu'un seul état initial (pas forcément 0), mais potentiellement plusieurs état finaux. Pour le code d'automate généré pour la machine virtuelle, nous prendrons les conventions suivantes. Le premier caractère de la chaîne candidate à tester se trouve à l'adresse Max et les caractères suivants vont décroissant. Le dernier caractère de la chaîne est suivi d'un caractère spécial null réservé pour marquer la fin. Le code que produit le générateur G pour A est le suivant :
000 LOA N1 Max
001 INC N1
002 BRA 003
003 DEC N1
004 LOA C1 N1
005 BEQ C1 a 003
006 BEQ C1 b 008
007 BEQ C1 null 015
008 DEC N1
009 LOA C1 N1
010 BEQ C1 a 008
011 BEQ C1 b 015
012 BEQ C1 null 013
013 LOA N1 1
014 BRA 016
015 LOA N1 0
016 STP
Le code suivant n'est toujours satisfaisant. On essayera de produire du code qui puisse être à la fois le plus réduit possible, et le plus efficace possible (il peut s'agir d'une option du compilateur).
Transcripteur
On peut étendre les définitions ci-dessus de façon à simuler un transcripteur. Il suffit de rajouter une second mémoire (dite bande de sortie) et de disposer de fonction permettant d'écrire dans cette seconde mémoire. Les instructions et leur définition pourraient être les suivantes :
- (LOA1 <reg> <mem>) et (LOA2 <reg> <mem>) comme LOA mais pour respectivement les mémoires 1 et 2.
- Même chose avec STO1 et STO2
Les autres instruction ne sont pas modifiées. On peut avoir, par exemple, la définition suivante pour un transcripteur :
((:voc a b) (:init 0) (:finals 1)
(:trans
(0 a 0 c) (0 b 1 a)
(1 a 1 b)
)).
Pour chaque transition nous avons rajouté un caractère à écrire sur la bande de sortie. Ce caractère peut éventuellement être null.
Question subsidiaire: Comment peut-on simuler un transcripteur à deux bandes avec une seule bande?
Mathieu LAFOURCADE LIRMM - 161, rue Ada — 34392 Montpellier Cedex 5 - Bureau : 2.114 - Téléphone : 67 41 85 71 - Fax : 67 41 85 00. mathieu.lafourcade@lirmm.fr