La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Université de Nice Sophia Antipolis Licence Informatique

De
4 pages
Niveau: Supérieur, Licence, Bac+3
Université de Nice – Sophia Antipolis 2009–2010 Licence 3 Informatique UE – Automates & Langages Contrôle continu du 4 novembre Durée : 1h30 1 feuille manuscrite autorisée Note : N om :Prénom : Exercice 1 : (4 points) On se place sur l'alphabet binaire et on s'intéresse au langage L décrit par l'expression régulière suivante : E : (0 + 1)0?10?1(0 + 1)? Construisez l'automate minimalA reconnaissant le langage L par la méthode des résiduels puis dessinez-le (vous détaillerez les calculs menant aux états). 1

  • usage des points de suspension

  • expression régulière pour le langage

  • automate fini

  • dates allant

  • feuille manuscrite

  • classe des langages rationnels

  • dé- nombrable


Voir plus Voir moins
Université de Nice – Sophia Antipolis Licence 3 Informatique
UE – Automates & Langages
Contrôle continu du 4 novembre
Durée :1h30 1 feuille manuscrite autorisée
Note :
2009–2010
Exercice 1 :(4 points)On se place sur l'alphabet binaire et on s'intéresse au langa geLdécrit par l'expression régulière suivante : ∗ ∗E+ 1)10 1(0: (0 + 1)0 Construisez l'automate minimalAreconnaissant le langageLpar la méthode des résiduels puis dessinez-le (vous détaillerez les calculs menant aux états).
1
a
a a a b q0q1q2
b b q3q4q5 b b
a
a, b
Exercice 2 :(4 points) 1. Construisezpuis dessinez ci-dessous l'automate minima lMobtenu en minimisant l'automateAde la figure.
2. Trouvezune grammaire régulière pour engendrer le langageL(A).
2
3. Donnezune expression régulière pour le langage reconnu par l'automateA.
p Exercice 3 :(4 points)Montrez à l'aide du théorème de l'étoile que le langageL={1, ppremier} n'est pas rationnel.
Exercice 4 :(4 points)Répondez aux questions suivantes en argumentant brièvement :
1. Surl'alphabet{0,1}? l'ensemble des la ngages est-il dé-, l'ensemble des mots est-il dénombrable nombrable ?
2. Laclasse des langages rationnels est close pour un certain nombre d'opérations. Précisez lesquelles.
3
3. Quelest le nombre maximal d'états que peut compter un automate obtenu par déterminisation d'un automate fini ànétats ?
4. Quesignifie le terme d'analyse lexicale?
Exercice 5 :(4 points)Dans cet exercice, on appelledatetoute expression du type : 04 novembre 2009 On cherche une grammaireG= (N, T , P, S)afin d'engendrer toutes les dates allant du 1 janvier 2000 au 31 décembre 2010, sachant que les années 2000, 2004 et 2008 sont bissextiles. L'ensemble des terminaux sera naturellement : {a, b, c, d, e,é, f, i, j, l, m, n, o, p, r, s, t, u,û, v,0,1,2,3,4,5,6,7,8,9} 1. Donnezvotre grammaireG, en précisant ses ensemblesNetP(vous veillerez à ne pas grossir incon-sidérément leurs cardinaux). Vous pouvez commenter votre grammaire, notamment la signification de ses non-terminaux. Enfin, l'usage des points de suspensio n n'est autorisé que pour les jours.
2. LelangageL(G)est rationnel, algébrique non-rationel ou non-algébrique? Justifiez votre réponse.
4