Langages réguliers et hors-contexte Cours M1 INaLCO, 20010-2011

Interrogation écrite du 07/12/2010


  1. Première partie

    On considère un alphabet à deux lettres a et b, et l'automate suivant sur cet alphabet :

    (a*b)*a det-2
    Les états de l'automate sont étiquetés X, Y, Z, T et U, l'état initial est X, le seul état terminal est Y.
    Appelons A cet automate.

    1. L'automate A est-il déterministe ?
      Si oui, donnez sa table de transitions.
      Exemple :

      Exemple

    2. L'automate A est-il minimal ?
      Si non, réduisez-le et donnez l'automate minimal qui reconnaît le même langage.

    3. Donnez une expression régulière décrivant le langage reconnu par l'automate A .

  2. Deuxième partie

    On considère l'automate B non-déterministe à 5 états I, II, III, A, B, où I est l'état initial et I, III, B les états terminaux.

    (a*b)*a non-det
    1. Que pouvez-vous dire du langage reconnu par l'automate B ?
      En d'autres termes, donnez a priori une forme d'expression régulière pour ce langage.

    2. Reste à déterminer le langage reconnu par l'automate C que voici

      (a*b)* det-2
      Vérifiez que (a*b)* = Σ*b ∪ {ε}, où Σ désigne l'alphabet {a, b}, cela peut vous aider...

    3. Montrez que l'automate déterministe associé à l'automate B n'est autre que l'automate A qui a été envisagé dans la première partie.
      Pouvez-vous en déduire une autre réponse à la question I.3 ?