Université de Nice Sophia Antipolis Licence Informatique

Sophia Antipolis

Description

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

Sujets

• Antipolis
• Universidad de Niza Sophia Antipolis
• Automate fini

Informations

• Publié par: vehot
• Nombre de lectures: 41
• Langue: Français

Extrait

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 q 0 q 1 q 2

b b q 3 q 4 q 5 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