Université de Nice Sophia Antipolis Licence Informatique

Sophia Antipolis

Description

Niveau: Supérieur, Licence, Bac+3
Université de Nice – Sophia Antipolis 2010–2011 Licence 3 Informatique UE – Automates & Langages Contrôle continu du 21 octobre 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 : ?+ (0 1)? 0 1 0? Construisez l'automate minimal M reconnaissant le langage L par la méthode des résiduels à gauche puis dessinez-le. Vous détaillerez les calculs des états (Indication : M a 6 états, y compris l'état-puits ?). 1

• grammaire régulière


• relation de transition ?


• propriétés de clôture


• automate fini


• langage rationnel


• feuille manuscrite

Sujets

• Antipolis
• Universidad de Niza Sophia Antipolis
• Grammaire régulière
• Automate fini
• Langage rationnel

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 21 octobre

Durée :1h30 1 feuille manuscrite autorisée

Note :

2010–2011

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 : ∗ ∗ ε0 1 0+ (0 1) Construisez l'automate minimalMreconnaissant le langageLpar la méthode des résiduels à gauche puis dessinez-le. Vous détaillerez les calculs des états (Indication :Ma 6 états, y compris l'état-puits∅).

1

Exercice 2 :(5 points)Soit l'automate finiA= (Σ ={0,1}, Q={q 0 , q 1 , q 2 }, δ, q 0 , F={q 0 , q 2 }). La relation de transitionδest explicite sur le schéma suivant : 0

0 1 q 0 q 1 q 2 1

1. Déduisezde l'automate finiAune grammaire régulière à droite pour engendrerL(A).

2. Calculezpuis dessinez l'automateDobtenu par déterminisation de l'automateA.

2

3. Calculezpuis dessinez ci-dessous l'automate minimalMobtenu en minimisant l'automateDpré- cédent.

Exercice 3 :(3 points)SoitLun langage rationnel reconnu par un automate finiA. Dites si les ensembles suivants sont rationnels et le cas échéant, expliquez brièvement comment construire un automate fini les reconnaissant à partir de l'automateA. 1. l'ensembleCarr L des carrés des mots deL:Carr L ={m=ww, w∈L}.

2. l'ensembleFact L des facteurs deL:Fact L ={v,∃u, wtels quez=uvw∈L}

R 3. l'ensembleReflet L des mots deLsuivis de leur miroir :Reflet L ={uuu ,∈L}

Exercice 4 :(4 points)Le langage de Dyck est constitué des parenthésages bien formés. En TD, nous avons montré qu'il n'était pas rationnel en utilisant des pr opriétés de clôture. Montrez qu'il n'est pas rationnel en utilisantcette fois-ci le théorème de l'étoil e.

3

Exercice 5 :(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. Qu'est-cequ'une grammaire ambiguë ? Vous pouvez bien-sûr donner un exemple.

3. Quedire du langage rationnel reconnu par un automate fini ne comportant aucun cycle (en particulier aucune boucle) ?

4. Unegrammaire régulière et une grammaire non-régulière peuvent-elles engendrer le même langage ?

4