Université de Nice Sophia Antipolis Licence Informatique

Sophia Antipolis

Description

Niveau: Supérieur, Licence, Bac+3
Université de Nice – Sophia Antipolis 2008–2009 Licence 3 Informatique UE – Automates & Langages Contrôle continu du 27 octobre Durée : 1h30 1 feuille manuscrite autorisée Note : N om :Prénom : Exercice 1 : (6 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). 1

• utilitaire flex


• contrôle continu


• analyse avec l'algorithme de cocke


• expression régulière


• feuille manuscrite


• mot baabaab


• automate minimal

Sujets

• Antipolis
• Universidad de Niza Sophia Antipolis
• Évaluation continue
• Expression rationnelle

Informations

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

Extrait

Université de Nice – Sophia Antipolis Licence 3 Informatique

UE – Automates & Langages

Contrôle continu du 27 octobre

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

Note :

2008–2009

Exercice 1 :(6 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).

1

2. Apartir de l'expression régulièreE, dessinez dans le coin en haut à droite un automate non-déterministe pour le langageLpuis déduisez-en une grammaire régulière à droite pourL:

3. Expliquezen "français" ce qui caractérise les mots deL.

Exercice 2 :(6 points) GrammaireG Axiome =S N = {S,A,B} T = {a,b} P = {S→aB|bA A→a|aS|bAA B→b|bS|aBB} 1. Cettegrammaire est-elle régulière ? algébrique ? Pourquoi ?

2

2. Mettezcette grammaire sous forme normale de Chomsky.

3. Procédezà l'analyse avec l'algorithme de Cocke, Youngeret Kasami (CYK) du motbaabaab. Indiquez également quels sont les préfixes de ce mot qui appartiennent àL(G).

4. Quelest donc le langageL(G)engendré par cette grammaire ? Est-il rationnel ? algébrique ?

3

Exercice 3 :(5 points)Montrez à l'aide du théorème de l'étoile pour les langages ra tionnels que le R∗ langage des palindromesL={w=wavecw∈ {0,1} }n'est pas rationnel.

Exercice 4 :(3 points)Répondez aux questions suivantes qui se rapportent aux TP. 1. Aquoi sert l'utilitaire? Expliquez brièvement son usage et son fonctionnement. Flex

2. Expliquezen restant très général les ressemblances et les différences des algorithmes de Boyer- Moore et de Knuth-Morris-Pratt.

4