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 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
Voir
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
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
