LES GRAPHES DE TRANSITION, L'ANALYSE LEXICALE, L'ETUDE DES CIRCUITS DIGITAUX, LE TEMPS REEL ET TURBO

216LES GRAPHES DE TRANSITION, L'ANALYSELEXICALE, L'ETUDE DES CIRCUITS DIGITAUX, LETEMPS REEL ET TURBO-PROLOGSerge MOUTOULe but de cet article est d'introduire des propriétés simples desgraphes de transition. Comme le suggère le titre de l'article, cette notionpeut être utilisée dans un nombre important de domaines. Nous nousproposons d'en examiner quelques uns ici. Pour ne pas rester trop abstrait, nous illustrons cet article à l'aidede programmes écrits en Turbo Prolog. La raison de ce choix, est laconcision d'écriture que permet ce langage (la recherche d'un chemindans un graphe de transition se programme en trois lignes !), permettantde ne pas transformer cet article en un "listing".I) L'ANALYSE LEXICALENous allons dans un premier temps définir la notion de graphe detransition.1) Définition.On appellera graphe de transition (ou diagramme de transition)dans la suite du cours un ensemble de données constitué par :-un ensemble d'états notés souvent par des entiers-un ensemble d'arêtes ou transitions d'un état vers un autre avec lesconditions de franchissement correspondantes appelées étiquettes.Il existe plusieurs manières de représenter un tel graphe. Nousprésentons ci-dessous un schéma simple, ainsi que la liste destransitions, généralement donnée sous forme de tableau appelé tablétats.LE BULLETIN DE L'EPI N° 49LE TEMPS RÉEL ET TURBO-PROLOG217Il existe deux sortes de graphes de transition : déterministes ounon indéterministes. On parle de ...