Université de Nice Sophia Antipolis Licence Informatique
4
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
4
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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
Voir
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
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={q0, q1, q2}, δ, q0, F={q0, q2}). La relation de transitionδest explicite sur le schéma suivant : 0
0 1 q0q1q2 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'ensembleCarrLdes carrés des mots deL:CarrL={m=ww, w∈L}.
2. l'ensembleFactLdes facteurs deL:FactL={v,∃u, wtels quez=uvw∈L}
R 3. l'ensembleRefletLdes mots deLsuivis de leur miroir :RefletL={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
