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:
-
L'automate AFG(L) se construit à
partir de AL en rendant terminaux tous les
états coaccessibles.
- L'automate AFD(L) se construit à
partir de AL en rendant initiaux tous les
états coaccessibles.
- L'automate AFACT(L) se construit à
partir de AL en rendant initiaux et terminaux
à la fois tous les états coaccessibles.
- 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.