Université Bordeaux I
Licence Informatique TD OMI 2001


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


  1. L1 = aab*(ab)* + ab* + a*bba* :
    L1 = K1 + K2 + K3 avec:

    K1 + K2 est reconnu par l'union de AK1 et AK2.
    Puisque l'union de deux automates doit se calculer à partir d'automates complets, on complète les deux automates AK1 et AK2 avec les deux états ``puits'', appelés respectivement p et p'.
    On déterminise:
      a b
    1,1' 2,2' p,p'
    2,2' 3,p' p,2'
    3,p' 4,p' 3,p'
    p,2' p,p' p,2'
    4,p' p,p' 5,p'
    5,p' 4,p' p,p'

    et après avoir renommé les états (l'état ``puits'' s'appelle p) on obtient l'automate AK1+K2:
       

       
    Rappel: lors d'une union d'automates l'état initial est le couple des deux états initiaux, les états terminaux sont les couples qui contiennent au moins un état terminal.
    Il reste à déterminiser l'union des automates AK1+K2 et AK3 pour obtenir l'automate qui reconnait L1 (le dessin se trouve, sur papier, dans mon bureau!).
    Table des transitions de l'automate qui reconnait L1:
      a b
    1,1" 2,1" p,2"
    2,1" 3,1" 4,2"
    p,2" p,p" p,3"
    3,1" 5,1" 3,2"
    4,2" p,p" 4,3"
    p,3" p,3" p,p"
    5,1" p,1" 6,2"
    3,2" 5,p" 3,3"
    4,3" p,3" 4,p"
    p,1" p,1" p,2"
    6,2" 5,p" p,3"
    5,p" p,p" 6,p"
    3,3" 5,3" 3,p"
    4,p" p,p" 4,p"
    6,p" 5,p" p,p"
    5,3" p,3" 6,p"
    3,p" 5,p" 3,p"

    On peut aussi construire l'automate reconnaissant L1 en utilisant la méthode du calcul des résiduels:
    (epsilon)-1L1 = L1     = Q0
    a-1L1 = ab*(ab)* + b* + a*bba*     = Q1
    b-1L1 = ba*     = Q2
    (aa)-1L1 = b*(ab)* + a*bba*     = Q3
    (ab)-1L1 = b* + ba*     = Q4
    (ba)-1L1 = Ø     = p
    (bb)-1L1 = a* = (bba*)-1L1 = Q5
    (aaa)-1L1 = b(ab)* + a*bba*     = Q6
    (aab)-1L1 = b*(ab)* + ba*     = Q7
    (aba)-1L1 = Ø     = p
    (abb)-1L1 = b* + a*     = Q8
    (bbb)-1L1 = Ø     = p
    (aaaa)-1L1 = a*bba* = (a+)-1L1 = Q9
    (aaab)-1L1 = (ab)* + ba*     = Q10
    (aaba)-1L1 = b(ab)*     = Q11
    (aabb)-1L1 = b*(ab)* + a*     = Q12
    (abba)-1L1 = a* = (abba+)-1L1 = Q5
    (abbb)-1L1 = b* = (abbb+)-1L1 = Q13
    (bbab)-1L1 = Ø     = p
    (aaaab)-1L1 = ba*     = Q2
    (aaaba)-1L1 = b(ab)*     = Q11
    (aaabb)-1L1 = a* = (aaa+bb)-1L1 = Q5
    (aabaa)-1L1 = Ø     = p
    (aabab)-1L1 = (ab)*     = Q14
    (aabba)-1L1 = b(ab)* + a*     = Q15
    (aabbb)-1L1 = b*(ab)* = (aabbb+)-1L1 = Q16
    (abbab)-1L1 = Ø     = p
    (abbba)-1L1 = Ø     = p
    (bbaab)-1L1 = Ø     = p
    (aaabaa)-1L1 = Ø     = p
    (aaabab)-1L1 = (ab)*     = Q14
    (aababa)-1L1 = b(ab)*     = Q11
    (aababb)-1L1 = Ø     = p
    (aabbaa)-1L1 = a*     = Q5
    (aabbab)-1L1 = (ab)*     = Q14
    (aabbba)-1L1 = b(ab)*     = Q11

    p est l'état ``puits''.
    La table des transitions de l'automate ainsi obtenu sera:
      a b
    Q0 Q1 Q2
    Q1 Q3 Q4
    Q2 p Q5
    Q3 Q6 Q7
    Q4 p Q8
    Q5 Q5 p
    Q6 Q9 Q10
    Q7 Q11 Q12
    Q8 Q5 Q13
    Q9 Q9 Q10
    Q10 Q11 Q5
    Q11 p Q14
    Q12 Q15 Q16
    Q13 p Q13
    Q14 Q11 p
    Q15 Q5 Q14
    Q16 Q11 Q16

    L'état initial est Q0 = (epsilon)-1L1, les états terminaux sont tous les Qi qui correspondent aux residuels contenant epsilon.

  2. L2 = a((ab)*cb*)* + a((ab)2cb*)*a*:
    L2 = K1 + K2 avec:
  3. L3 = ((a*bc*)* acbb*b)*:
    L3 = (L)* avec L = (a*bc*)* acbb*b)
    L = M1M2 avec M1 = K*, K = a*bc*, et M2 = acbb*b
    L = M1M2 est reconnu par l'automate non déterministe:
       

       

    On le déterminise:
      a b c
    1 3,4 2 p
    3,4 3 2 5
    2 3,4 2 2
    3 3 2 p
    5 p 6 p
    6 p 7 p
    7 p 7 p

    p désigne l'état ``puits''.
    Après avoir renommé l'état {3,4} en état 4 on obtient l'automate (non complet: on a omis le puits et toutes les transitions le concernant) AL:
       

       
    L3 = (L)* est reconnu par l'automate non déterministe:
       

       

    On le déterminise:
      a b c
    1 4 2 p
    4 3 2 5
    2 4 2 2
    3 3 2 p
    5 p 6 p
    6 p 7 p
    7 4 2,7 p
    2,7 4 2,7 2

    p désigne l'état ``puits''.
    Après avoir renommé l'état {2,7} en état 8 on obtient l'automate (non complet: on a omis le puits et toutes les transitions le concernant) AL3:
       

       

This document was translated from LATEX by HEVEA.