Langages réguliers et hors-contexte

Cours M1 INaLCO, 2012-2013

Interrogation écrite du 29/11/2012

1. Première partie

   
   

   Définition Étant donné un ensemble fini de mots E, on appelle arbre lexical associé à E un automate fini ainsi conçu : son alphabet est formé des lettres qui apparaissent dans les mots de E ses états sont tous les préfixes des mots de E, y compris le mot vide "" et les mots de E eux-mêmes (le mot préfixe est donc pris au sens large) l'état initial est le préfixe vide "" les états terminaux sont les mots de E transitions : pour une lettre x et un état (préfixe) p on fait suivre p de la lettre x, obtenant le mot px si px est un des préfixes de E, c'est le résultat de la transition sinon il n'y a pas de transition pour l'état p et la lettre x. Questions L'arbre lexical est-il un automate déterministe ? Quel est le langage reconnu par cet automate ? L'automate est-il minimal ? Si non, à quelles conditions peut-il l'être ?

   Exemple ensemble E = { le, leur, lui, ses } Alphabet : { e, i, l, r, s, u } États : { "", l, s, le, lu, se, leu, lui, ses, leur } État initial : "" États terminaux : { le, leur, lui, ses} Transitions e i  l  r s u "" l s l le lu s se le leu lu lui se ses leu leur lui ses leur

   
   
   
   
   
   

2. Seconde partie

   On veut décrire de manière précise la structure des balises ouvrantes en XML.
   Exemple :
   <transition source="0" lettre="x" but="1" >
   
   
   1. Une balise ouvrante commence par '<', immédiatement suivi d'un nom, et se termine par '>',
      qui peut être précédé de blancs, de tabulations et même de sauts de ligne.
      
      
   2. Entre le nom et le chevron fermant se trouve une suite (qui peut être vide) de couples attributs-valeurs formés
      
      • d'un nom
      • d'un signe '=' qui peut être entouré de blancs, de tabulations et de sauts de ligne
      • d'une valeur placée entre '"'
        
        
   3. Un nom est non-vide, formé de lettres et de chiffres, mais ne peut pas commencer par un chiffre
      
      
   4. Une valeur est une chaîne qui peut être vide, sans restriction sur les caractères qui la composent,
      y compris blancs, tabulations et  sauts de ligne,
      mais elle ne doit pas contenir de chevron ouvrant '<'.
      
   
   Questions
   
   
   1. De quelles classes de caractères avez-vous besoin pour décrire cette structure ?
      Désignez-les par des lettres conventionnelles A, B, C...
      
      
   2. Utilisez ces lettres pour écrire une expression régulière décrivant le langage des balises ouvrantes.
      
      
   3. Dessinez un automate fini déterministe reconnaissant ce langage.