Université Bordeaux I
Licence Informatique TD OMI 2001


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


  1. Il s'agit du langage des mots dont la troisième lettre avant la fin est un 'a'.

      a b
    1 1,2 1
    1,2 1,2,3 1,3
    1,2,3 1,2,3,4 1,3,4
    1,3 1,2,4 1,4
    1,2,3,4 1,2,3,4 1,3,4
    1,3,4 1,2,4 1,4
    1,2,4 1,2,3 1,3
    1,4 1,2 1

    Après avoir renommé les états on obtient:

       
       
    Remarque: les quatre états terminaux correspondent aux quatres facteurs droits possibles: les mots se terminant par aaa sont reconnus à l'état 5, les mots se terminant par aab sont reconnus à l'état 6, les mots se terminant par aba sont reconnus à l'état 7, mots se terminant par abb sont reconnus à l'état 8.

  2. on obtient le même automate que ci-dessus!

This document was translated from LATEX by HEVEA.