THESE 2009

Informations

• Publié par: Zodaj
• Nombre de lectures: 40
• Langue: Français

Extrait

BRISSON Etienne 08/01/2009 Conversion du graphe en langage Transformation graphique de l'automate : La transformation consiste en la suppression des nœuds, les uns après les autres. Cela doit être fait jusqu'à suppression totale de tous les nœuds. Il est à noter que les arcs ne contiendront plus des lettres mais des expressions comprenant des lettres ainsi que des opérateurs comme l'étoile, l'addition et les parenthèses Première étape: créer un état initial et un état terminal virtuel

Seconde étapeSuppression de boucle en répartissant le contenu sur les arcs : entrants ou sortants. Le contenu de la boucle sera insérée en fin des expressions des flèches entrantes ou en début des expressions des flèches sortantes.

Page : 1

BRISSON Etienne

08/01/2009

Troisième étapeSuppression d'un nœud. Pour cela, pour tout arc entrant, pour : tout arc sortant, on crée un arc partant de l'initiale de l'arc entrant, allant jusqu'à la borne de l'arc sortant. Ainsi, tous les arcs entrants et sortants du nœud à supprimer peuvent être supprimés. Le nœud étant maintenant isolé peut être supprimé.

REMARQUE : Si arc existe déjà, la création consistera uniquement à ajouter le contenu de l'arc désiré a celui de l'arc déjà existant mais avec un signe plus (UNION) pour séparer les données Quatrième étape : Cette étape consiste a réexécuter les étapes deux et trois jusqu'à entière suppression des nœuds.

Page : 2

BRISSON Etienne

08/01/2009

REMARQUELes simplifications des expressions peuvent être réalisées au fur et à : mesure des traitements. Il est en effet plus facile de simplifier quand les expressions sont encore simples.

La complexité : 2 La complexité pour la suppression des boucles est en O(N ) si on les supprime toutes à chaque passage et en O(N) si on ne supprime que la boucle du nœud que l'on supprime. La complexité de la suppression des nœuds est en O(N).

Page : 3

BRISSON Etienne 08/01/2009 Optimisations possibles :  Il n'est pas nécessaire de supprimer toutes les boucles avant chaque traitement, seul le nœud a supprimé doit être débarrassé de son éventuelle boucle.  Le processus est semiparallélisable : en effet on peut traiter en parallèle des nœuds, sous condition, qu'ils ne soient pas connexes.

Page : 4

BRISSON Etienne 08/01/2009 Transformation de l'automate dans la table : Les automates sont généralement représentés sous forme d'une table à deux dimensions, ayant pour horizontal les nœuds de départ, en vertical les lettres de l'alphabet et pour donnée les nœuds d'arrivées... La représentation que je propose est une matrice carrée dans ayant pour vertical les nœuds de départ, pour horizontal les nœuds d'arrivée et les données sont des empressions. Ces expressions sont construites au fur et à mesure de la suppression des nœuds comme décrit précédemment. EXEMPLE:

5 I

e

1 1

a

b

a

2 2

b

c

3 3

c

a b

4 4

6 T

c  1 2 3 4 1 a b c 2 b c 3 a c c a 4 b La première étape consiste à créer un état virtuel initial ainsi qu'un état virtuel terminal. Arbitrairement, j'utilise l'indice zéro pour y créer ces deux états virtuels : La verticale pour l'état terminal et l'horizontal pour l'état initial. REMARQUE: De ce fait la solution finale apparaîtra dans la case de coordonnée (0,0). Si en fin de traitement, cette case est vide alors on pourra en conclure que l'automate représentait un langage vide.  0 1 2 3 4

Page : 5

BRISSON Etienne 08/01/2009 0 e 1 a b c 2 b c 3 a c c a 4 e  b La seconde étape consiste à supprimer l'éventuel boucle du nœud à supprimer. Suppression du nœud 1 :  0 1 2 3 4 0 a* 1 b c 2 b c 3 a.a* c c a 4 e  b REMARQUE: On remarque sur cet exemple que des simplifications peuvent être faite * + au fur et à mesure de traitement (Ex: le a.a peut être remplacé par un a ).

Page : 6

BRISSON Etienne La troisième étapeconsiste à supprimer le nœud.  0 1 2 3 4  a*b a*c 0 1  b c 2 + +  c+(a b) c a+(a c) 3 e  b 4

Page : 7

08/01/2009

BRISSON Etienne 08/01/2009 Automate universel Représentation graphique des automates minimaux/maximaux : Imaginons un automate qui puisse représenter tous les langages. Celuici devrait dont pouvoir représenter les automates et les transducteurs à pile. Au niveau de la programmation de ces automates, les traitements resteraient les mêmes, mais la représentation graphique, inexistante actuellement, pourrait être réalisés grâce à des quantificateurs sur les arcs. Ces quantificateurs, je les ai appelés minima/maxima. Ils définissent le nombre minimal et maximal de fois que la lettre de l'arc peut être lu afin de passer au nœud suivant. Ainsi :

1 2 3 4 a a a 1 2 3 4 Peut s'écrire 3 a 1 2 2 1 2 Le langage pourrait alors porter sur des expressions comprenant, pour chaque lettre, un minima et un maxima. REMARQUE : Les expressions parenthèsées auraient le même type de min/max Exemple : 2¥2 1¥ ¥ a.b. (a.b. )a. 1 0 2 1 1 0

Page : 8

BRISSON Etienne 08/01/2009 Automate aller/retour Recherche sur des automates définis comme aller/retour Imaginons des automates où les arcs n'auraient pas de sens. Il n'y aurait donc plus ni arc entrant, ni arcs sortant mais seulement une liste d'arc connecté à un nœud. Cette catégorie d'automate représente une sous ensemble bien précis des automates classiques. En effet, ils correspondent aux automates qui possèdent systématiquement un arc de retour pour chaque arc aller (Avec la même lettre). Exemple :

1 1

1 1

a

a

a

2 2

b

Devient

2 2

b

b

2 2

2 2

Il est difficile d'établir le langage dégager par ces automates car il devient rapidement très touffu. Par contre quelques réduction d'automate sont possible  Si deux nœuds distincts possèdent les mêmes arcs alors l'un d'eux peut être éliminés.

Page : 9

BRISSON Etienne

JKL

1 1

a

a

1 1

1 1

b

b

1 1

08/01/2009

Devient alors a b 1 1 1 1 1 1  Si deux nœuds distincts possèdent les mêmes arcs et sont reliés entre eux alors l'un d'eux peut être éliminés et l'autre se voit affublé d'une boucle sur laquelle trône la lettre que les reliait.

XXXXXXX

1 1

1 1

a

a

1 1

1 1

c

b

b

Devient alors c

a

1 1

Page : 10

b

1 1

1 1

Page XX