Reduction d'automates

Auteurs

Vivien Delmon

Type

techreport

Année

2008

Numéro

0830

Projects

Vaucanson

Mots-clés

parser, rational expression, Bison, transducerautomaton

Résumé

Un automate dèterministe peut être minimisè de manière efficace et donne un automate dont le nombre d'états est minimal. L'algorithme de réduction présenté dans ce rapport permet de construire un automate dont le nombre d'états est minimal à partir d'un automate non déterministe dont les poids sont définis sur un semi-anneau qui est un corps. L'algorithme calcule pour cela la base de l'espace vectoriel engendré par la série représenté par l'automate, ce qui permet de construire un automate dont le nombre d'états est égal à la dimension de cette base. L'algorithme se base sur la représentation matricielle des automates et nous amène à résoudre un système d'équations linéaires, ce qui force le semi-anneau de notre série à avoir les propriétés d'un corps. Nous voulons aussi que notre algorithme fonctionne sur des séries dont le semi-anneau est un corps non commutatif ce qui nous empêche d'utiliser les techniques classiques de résolution de systèmes linéaires. Ce rapport montre comment passer outre ces difficultés. Nous verrons enfin comment adapter notre algorithme pour qu'il fonctionne sur Z qui n'est pas un corps mais qui possède des propriétés suffisantes.