Université Bordeaux I
Licence Informatique TD OMI 2001


Feuille d'exercices 1
Corrigé de l'exercice 11




Si L est reconnaissable, on peut construire un automate déterministe AL qui le reconnait. On suppose que: tous les états de AL sont accessibles, tous les états de AL sauf le ``puits'' sont coaccessibles.

À partir de AL on peut construire les quatre automates comme suit:
  1. L'automate AFG(L) se construit à partir de AL en rendant terminaux tous les états coaccessibles.
  2. L'automate AFD(L) se construit à partir de AL en rendant initiaux tous les états coaccessibles.
  3. L'automate AFACT(L) se construit à partir de AL en rendant initiaux et terminaux à la fois tous les états coaccessibles.
  4. L'automate ALtilda se construit à partir de AL de la façon suivante:
    l'état initial de AL devient état terminal de ALtilda, les états terminaux de AL deviennent tous états initiaux de ALtilda, le sens de toutes les transitions est inversé.
Pour les trois dernières constructions, on obtient en général des automates non déterministes.
This document was translated from LATEX by HEVEA.