11 décembre 2008

1. Observations sur l'interrogation écrite du 11/12/08
2. Continuation vers une expérimentation sur machine

Jean-François Perrot

Observations sur l'interrogation écrite du 11/12/08

• La transcription en notation mathématique doit témoigner d'une lecture correcte de E. En stricte orthodoxie, il faut distinguer les lettres et les singletons, qui sont des entités de nature différente,
  d'où une écriture beaucoup trop lourde en pratique : E = ({7}∪{9})+∪{0}.({7}+∪{x}.({7}∪{9}∪{h})+) 
  
  
• Les deux sous-ensembles (7|9)+ et 0(7+|x(7|9|h)+) sont disjoints, car les mots du premier ne commencent pas par 0,
  contrairement à ceux du second. Cette circonstance est un guide dans l'analyse de l'expression.
  En allant plus loin dans cette voie, on s'aperçoit que l'ensemble-facteur (7+|x(7|9|h)+) est lui-même
  la réunion de deux parties disjointes 7+ et x(7|9|h)+, de sorte que notre langage est formé de trois parties disjointes
  E = A|B|C, avec A = (7|9)+,  B = 07+ et  C = 0x(7|9|h)+.
  
  
• Moyennant quoi :
  779 appartient à A, il est donc accepté
  0779 devrait appartenir à B, mais 9 est impossible, il est donc rejeté
779h devrait appartenir à A, mais h est impossible, il est donc rejeté
0779h devrait appartenir à B, mais h est impossible, il est donc rejeté
0x779h appartient à C, il est donc accepté
  h779 est complètement inacceptable, aucun mot du langage ne commence par h
0h779 devrait appartenir à B, mais h est impossible, il est donc rejeté
0xh779 appartient à C, il est donc accepté.
  
  
• L'automate proposé est déterministe car on trouve pour chaque état et chaque lettre de l'alphabet
  une et une seule transition vers un autre état.
  En pratique, on constate sur le dessin tracé par le logiciel automate,
  que les ensembles de lettres qui étiquettent les différentes flèches issues de chaque sommet
  sont disjoints et que leur réunion est l'alphabet tout entier X = {0, x, 7, 9, h} :
  
  0. 0 - h|x - 7|9
  1. 0|7|9|h|x (état-poubelle)
  2. 7|9 - 0|h|x
  3. 7 - x - 0|9|h
  4. 0|x - 7|9|h
  5. 0|x - 7|9|h
  6. 7 - 0|9|h|x
  
  
• Il est minimal car chaque paire de sommets est séparable par au moins une lettre (cf. cours n° 4)
  
  • les trois états terminaux sont séparés : 2-5 par h, 2-6 par 9, 5-6 par 9; 
  • la "poubelle" 1 est séparée du reste ;
  • 3 et 4 sont séparés par 9 ;
  • 0 et 3 sont séparés par x ;
    
  • 0 et 4 sont séparés par h ;
    
    
• Il a un rapport fort étroit avec l'e.r. initiale : c'est l'automate minimal qui reconnaît le langage de l'e.r.,
  comme on le voit à partir de la tripartition A|B|C, où A correspond à l'état terminal 2, B à 6 et C à 5.
  
  
• Quant à donner une interprétation, voyez ci-dessous.

Continuation vers une expérimentation sur machine

• décimale : une suite non vide de chiffres décimaux ne commençant pas par 0
• octale : une suite non vide de chiffres octaux commençant par 0
• hexadécimale : une suite non vide de chiffres hexadécimaux préfixée par 0x.

• La lettre 0 s'interprète comme le chiffre 0
• La lettre x s'interprète comme le caractère x (marqueur)
• La lettre 7 s'interprète comme l'intervalle [1-7] (chiffres "octaux")
• La lettre 9 s'interprète comme l'ensemble {8, 9}
• La lettre h s'interprète comme l'intervalle [A-F] (chiffres "hexadécimaux")

• le premier terme doit s'écrire (7|9)(0|7|9)* pour exprimer ue seul le premier chiffre doit être non nul
• dans le second terme 0 peut apparaître sitôt après le préfixe, on doit donc écrire
  0((0|7)+|x(0|7|9|h)+)

• 7 se traduit par [1-7]
• (0|7) se traduit par [0-7]
• (7|9) se traduit par [1-9]
• (0|7|9) se traduit par [0-9]
• (0|7|9|h) se traduit par [0-9A-F]