L'une des constructions les plus connues pour transformer une expression régulière (ou rationnelle) en automate est sans doute celle de l'automate de Thompson. C'est le point de départ de cet exposé. Nous verrons pourquoi cet automate n'est pas adapté dans le cas des automates et expressions pondérés. L'automate NET est une alternative à l'automate de Thompson; il en préserve les avantages et peut s'appliquer à toute expression rationnelle pondérée.

L'automate NET, comme l'automate de Thompson, est défini inductivement, mais il peut aussi être défini directement sur l'arbre syntaxique de l'expression, ce qui permet de mettre en évidence sa parenté avec une structure bien connue au LITIS.

Enfin, nous verrons comment cette construction définie au départ pour traiter les expressions pondérées permet, dans le cadre des expressions classiques, de revisiter la forme normale de Brüggeman-Klein.

Il s’agit d’un travail en collaboration avec Jacques Sakarovitch.