Université Bordeaux I
Licence Informatique TD OMI 2001


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


  1. L1 est reconnu par l'automate non déterministe suivant:
       



       
    On le déterminise:
      a b
    0 0,1 0
    0,1 0,1 0,2
    0,2 0,1,3 0
    0,1,3 0,1,3 0,2,3
    0,2,3 0,1,3 0,3
    0,3 0,1,3 0,3

    et après avoir renommé les états on obtient:
       



       
    Remarque: on voit facilement qu'il n'est pas minimal: les trois états terminaux peuvent ``fusionner'' en un seul état.

  2. L2 est reconnu par l'automate non déterministe suivant:
       


       
    On le déterminise:
      a b
    0 0,1 0,2
    0,1 0,1,3 0,2
    0,2 0,1 0,2,4
    0,1,3 0,1,3,5 0,2
    0,2,4 0,1 0,2,4
    0,1,3,5 0,1,3,5 0,2

    et après avoir renommé les états on obtient:
       



       


  3. L3 est reconnu par l'automate non déterministe suivant:
       

       
    On le déterminise:
      a b
    0 0,1 0,2
    0,1 0,1,3 0,1,2
    0,2 0,1,2 0,2,4
    0,1,3 0,1,3 0,1,2
    0,1,2 0,1,2,3 0,1,2,4
    0,1,2,3 0,1,2,3 0,1,2,4
    0,1,2,4 0,1,2,3 0,1,2,4

    et après avoir renommé les états on obtient:
       

       
    Remarque: on voit facilement qu'il n'est pas minimal: les états {0,1,2,3} et {0,1,2,4} peuvent ``fusionner'' en un seul état.

This document was translated from LATEX by HEVEA.