Le complément d’un langage reconnaissable

Le complément d’un langage reconnaissable

Le complément d’un langage reconnaissable (l’ensemble de mots sur le même alphabet n’appartenant pas au langage en question) est encore reconnaissable. Soit D un automate déterministe et complet reconnaissant le langage X. Pour construire un automate reconnaissant le complément de X, il suffit de prendre comme ensemble d’états terminaux le complément de l’ensemble d’états terminaux de D. Exemple Construisons un automate sur A = {a, b} qui reconnaît l’ensemble des mots n’ayant pas aba en facteur. On commence par la construction d’un automate (non déterministe) reconnaissant tous les mots ayant aba en facteur. Figure 5.8 Appliquons l’algorithme de déterminisation : Tableau 5.7 État États résultant en lisant a en lisant b (initial) (0) (0,1) (0) (0,1) (0,1) (0,2) (0,2) (0,1,3) (0) (terminal) (0,1,3) (0,1,3) (0,2,3) (terminal) (0,2,3) (0,1,3) (0,3) (terminal) (0,3) (0,1,3) (0,3) Figure 5.9 Cet automate déterministe et complet reconnaît tous les mots ayant aba en facteur. Il a trois  états terminaux : (0,1,3), (0,2,3) et (0,3). Chapitre 5 • Automates Maintenant pour obtenir un automate (lui aussi déterministe et complet) reconnaissant tous les mots qui n’ont pas aba en facteur, il suffit de faire de tous les états terminaux, des états non terminaux, et vice versa : Figure 5.10 Ici, on a obtenu un automate complet sans qu’il y ait besoin de le compléter en introduisant l’état poubelle. Évidemment, ceci n’est pas toujours le cas. Si on a affaire à un automate non complet, on n’a pas le droit de remplacer directement les états terminaux par des états non terminaux et vice versa : il faut d’abord le compléter. Alors l’état poubelle (qui ne peut pas être terminal) devient un état terminal de l’automate reconnaissant le complément du langage.

Minimisation

Pour tout langage reconnaissable il existe le plus petit (c.-à-d. contenant le plus petit nombre d’états) automate déterministe qui le reconnaît, et il est unique : c’est l’automate minimal du langage. • Algorithme de minimisation par la méthode des équivalences Il est basé sur la notion de partitionnement de l’ensemble d’états de l’automate. Principe Tout d’abord, si l’automate à minimiser n’est pas complet, il faut lui ajouter l’état poubelle pour qu’il le devienne. Sinon on risque de faire une erreur grave, qui se manifeste facilement au cas d’un automate déterministe non complet dont tous les états sont des états terminaux (essayez le voir vous-mêmes après avoir compris l’algorithme de minimisation). On sépare tous les états de l’automate déterministe initial en deux groupes : terminaux et non-terminaux. Puis, on analyse la table des transitions en marquant vers quel groupe va chaque transition. On repartitionne les groupes selon les patterns des transitions en terme de groupes. On répète ce processus en utilisant cette nouvelle partition, et on réitère jusqu’à ce qu’on arrive à ne plus pouvoir partitionner. Les groupes restants forment l’automate minimal. On appelle souvent les itérations les étapes. Description du processus de partitionnement itératif Soit un automate fini déterministe complet D = (Q, i, T , E). Résultat à obtenir : Un automate fini déterministe complet D ′ qui reconnaît le même langage que D et qui a aussi peu d’états que possible. Méthode Construire une partition initiale Q0 de l’ensemble des états avec deux groupes : les états terminaux T et les états non-terminaux Q − T . 1

L’interprétation intuitive

Procédure applicable à la partition courante Qi , à commencer par Q0 : POUR chaque groupe G de Qi FAIRE début partitionner G en sous-groupes de manière que deux états e et t de G soient dans le même sous-groupe ssi pour tout symbole a ∈ A, les états e et t ont des transitions sur a vers des états du même groupe de Qi ; /* au pire, un état formera un sous-groupe par lui-même */ remplacer G dans par tous les sous-groupes ainsi formés ; on obtient la partition de l’étape suivant, Qi+1 ; fin Si Qi+1 = Qi alors Qf inal = Qi et continuer à l’étape 4. Sinon, répéter l’étape (2) avec Qi+1 comme partition courante. Choisir un état dans chaque groupe de la partition Qf inal en tant que représentant de ce groupe. Les représentants seront les états de l’automate fini déterministe réduit D ′ . Soit e un état représentatif, et supposons que dans D il y a une transition e a −→t. Soit r le représentant du groupe de t (r peut être égal à t). Alors D ′ a une transition de e vers r sur a (e a −→r). L’état initial de D ′ est le représentant du groupe qui contient l’état initial i de D ; les états terminaux de D ′ sont des représentants des états de T . Pour tout groupe G de Qf inal, soit G est entièrement composé d’états de T , soit G n’en contient aucun. Remarque En réalité, il est parfois plus facile, au lieu de choisir un représentant, marquer les groupes finaux comme tels, ou bien les renommer par, par exemple, A, B, C … , et remplacer dans les transitions tout état par le nom de son groupe : Si e a −→r , e ∈ A, r ∈ B où les groupes A, B ∈ Qf inal, alors dans l’automate minimisé on a A a −→B où maintenant on considère A et B comme états de l’automate minimisé. Cette remarque deviendra tout à fait claire à la fin de l’exemple suivant.