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 Examen du 21 janvier Durée : 2h 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 + 1)?0 1. Construisez l'automate minimal A reconnaissant le langage L par la méthode des résiduels puis dessinez-le (vous détaillerez le calcul menant aux états). 2. Décrivez en français ce que sont les mots de L. 1

• automate


• langage algébrique


• grammaire


• classe des langages ration- nels


• minimala travaillant sur l'alphabet fini

Sujets

• Antipolis
• Universidad de Niza Sophia Antipolis
• Automate
• Langage algébrique
• Grammaire
• Français

Informations

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

Extrait

Université de Nice – Sophia Antipolis Licence 3 Informatique

UE – Automates & Langages

Examen du 21 janvier

Durée :2h 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 : ∗ E0: 0 + 1(0 + 1) 1. Construisezl'automate minimalAreconnaissant le langageLpar la méthode des résiduels puis dessinez-le (vous détaillerez le calcul menant aux états).

2. Décrivezen françaisce que sont les mots deL.

1

Exercice 2 :(6 points)Supposons qu'il n'existe que des pièces de 1, 2 et de 5e. Pour obtenir une somme donnée ene, cela induit un certain nombre possibilités. 1. Trouvezl'automate fini minimalAtravaillant sur l'alphabet fini{1,2,5}et rendant compte de toutes les possibilités pour décomposer la somme de 6een pièces de 1, 2 et 5e. On codera indifféremment 15 ou bien 51 le fait de prendre une pièce de 1eet une pièce de 5e.Pour plus de lisibilité, merci d'aligner les différents états de l'automate.

2. Déduirede l'automate précédent une grammaire régulièreGengendrant le même langage que le langageL(A)reconnu par l'automateA.

′ 3. Trouvezune grammaireGéquivalente àGet sous forme normale de Chomsky.

2

4. Analysezle mot212115qué à la gram-à l'aide de l'algorithme Cocke-Younger-Kasami (CYK) appli ′ ′ maireG. Bien-sûr, il n'appartient pas àL(G)mais cette trace vous permet tout de même de déceler certaines combinaisons valides. Dites lesquelles.

Exercice 3 :(6 points)La machine de TuringM= (Q,Γ,Σ, δ, q 0 , ♯, F)est définie comme suit : –Q={q 0 , q 1 , q 2 , q 3 , q 4 , q 5 } –Γ ={X, Y, ♯} –Σ ={0,1} –q 0 est l'état initial –F={q 3 } – lafonction de transitionδest décrite par les quintuplets ci-dessous : (q 0 , Y, q 0 , Y, D) (q 1 ,1, q 2 , Y, G) (q 4 , X, q 0 , X, D) (q 0 ,0, q 1 , X, D) (q 2 ,0, q 2 ,0, G) (q 5 ,1, q 5 ,1, D) (q 0 , ♯, q 3 , ♯, D) (q 2 , Y, q 2 , Y, G) (q 5 , Y, q 5 , Y, D) (q 0 ,1, q 5 , X, D) (q 2 , X, q 0 , X, D) (q 5 ,0, q 4 , Y, G) (q 1 ,0, q 1 ,0, D) (q 4 ,1, q 4 ,1, G) (q 1 , Y, q 1 , Y, D) (q 4 , Y, q 4 , Y, G) 1. Dessinezla machine de Turingau brouillonen veillant à disposer ses états en cercle suivant leur numérotation. Quel est donc le langageLreconnu parM?

2. Dessinezun automate à pileAreconnaissant le langageL(M)vu que ce dernier est algébrique.

3

3. Donnezune grammaire algébrique pour le langageL(M).

Exercice 4 :(4 points)Répondez aux questions suivantes en argumentant brièvement :

1. Tousles langages algébriques sont-ils reconnus par un automate à pile déterministe ?

2. Citeztrois applications directes de la théorie des langages formels vues ou entrevues cette année :

3. Quelssont les langages qui peuvent être engendrés par des grammaires ?

4. Lemiroirclasse des langages ration-d'un mot est le mot obtenu en inversant son sens de lecture. la nels est-elle close par l'opérationmiroir? Et celle des langages algébriques?

4