//img.uscri.be/pth/acf21cae9429b44f920f768b9a1ee27b3f859c76
La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Université de Nice Sophia Antipolis Licence Informatique

De
4 pages
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


Voir plus Voir moins

Vous aimerez aussi

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 = {SaB|bA Aa|aS|bAA Bb|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 Rlangage 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