Scribd Logo
Importer

Bienvenue sur Scribd !

  • 156 vues

    TD Comp 02

    Transféré par

    vbzrg
    Ce document contient 11 exercices portant sur les expressions régulières, les automates finis et les grammaires régulières. Les exercices couvrent la description de langages dénotés par des expressions régulières, la construction d'automates finis reconnaissant certains langages, et l'écriture de grammaires régulières.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    TD Comp 02

    Transféré par

    vbzrg
    156 vues2 pages
    Ce document contient 11 exercices portant sur les expressions régulières, les automates finis et les grammaires régulières. Les exercices couvrent la description de langages dénotés par des expressions régulières, la construction d'automates finis reconnaissant certains langages, et l'écriture de grammaires régulières.

    Titre original

    TD_Comp_02

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document contient 11 exercices portant sur les expressions régulières, les automates finis et les grammaires régulières. Les exercices couvrent la description de langages dénotés par des expressions régulières, la construction d'automates finis reconnaissant certains langages, et l'écriture de grammaires régulières.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    156 vues2 pages

    TD Comp 02

    Transféré par

    vbzrg
    Ce document contient 11 exercices portant sur les expressions régulières, les automates finis et les grammaires régulières. Les exercices couvrent la description de langages dénotés par des expressions régulières, la construction d'automates finis reconnaissant certains langages, et l'écriture de grammaires régulières.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 2

    Compilation L3A Série 02 INF/UFAS I

    Exercice 01
    Décrire les langages dénotés par les expressions régulières suivantes:
    a) a(a|b)*a.
    b) ((ε|a)b*)*.
    c) (a|b)*a(a|b)(a|b).
    d) a*ba*ba*ba*.
    !! e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*.

    Exercice 02
    Ecrire les définitions régulières pour les langages suivants:
    a) Toutes les chaines sur les lettres minuscules contenant les cinq voyelles en ordre.
    b) Toutes les chaines sur les lettres minuscules dans lesquelles les lettres sont dans un ordre
    lexicographique ascendant.
    c) Toutes les chaines sur les chiffres sans qu’un chiffre soit répété (successivement).
    Astuce : commencer par exemple avec (0, 1 ,2).

    Exercice 03
    Donner les diagrammes de transition pour la reconnaissance des langages dénotés par les ERs précédentes.
    a) a(a|b)*a

    b) ((ε|a)b*)*

    c) (a|b)*a(a|b)(a|b)

    d) a*ba*ba*ba*

    !! e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*.

    Exercice 4
    Cet automate reconnait quoi ? Donnez-en une expression régulière.

    Exercice 05
    Si on l’utilise pour trouver des lexèmes dans un fichier d’entrée, combien de caractères doit on examiner au
    pire après la fin d’un lexème pour pouvoir l’identifier ?

    Exercice 06
    En général un analyseur lexical reconnait le plus long préfixe. Comment traiter le cas des commentaires de
    manière `a ne pas oublier du code dans l’exemple ci-dessous en Caml ?
    let f x = (* une fonction Caml *)
    if x mod 2 = 0 then x/2 else x+3;;
    (* fin de la fonction Caml *)
    Compilation L3A Série 02 INF/UFAS I

    Exercice 07
    a. On considère l'alphabet (symboles terminaux) Σ = {+, x, id, nb} dans lequel id et nb symbolisent
    respectivement des identificateurs et des nombres. Soit la grammaire :
    S  id | nb | SS+ | SSx : Que représentent les productions de cette grammaire ?
    b. Donner deux dérivations produisant : id id + nbx
    c. Donner une grammaire produisant les expressions arithmétiques préfixées (opérateurs + et x binaires).

    Exercice 08
    Un palindrome est un mot qui se lite de la même manière de gauche à droite ou de droite à gauche.
    Exemples : abba, ababababa, ressasser. Ecrire une grammaire reconnaissant les palindromes sur l’alphabet
    {a,b}.

    Exercice 09
    En vous appuyant sur l’exemple suivant, imaginez un procédé pour construire, à partir d’une grammaire
    régulière, un automate reconnaissant le même langage.
    SabA|baA
    AbB|B
    Ba|abA
    2. Imaginez le procédé inverse : de l’automate vers la grammaire régulière.

    Exercice 10
    Ecrire des grammaires reconnaissant les langages suivants. Sont-elles linéaires ? Régulières ?
    - Chaînes de 0 et de 1 où tout 0 est suivi d’au moins un 1
    - Chaînes de 0 et de 1 comprenant autant de 0 que de 1. Variantes : langages bien parenthèsés.
    - Expressions arithmétiques préfixées (exo 4)
    - Palindromes (exo 8)

    Exercice 11 (à laisser pour la révision)


    Sur l’alphabet A = {a, b}, donner un automate fini déterministe reconnaissant les langages suivants :
    – tous les mots contenant un nombre pair de “a” et un nombre pair de “b”;
    – tous les mots contenant un nombre pair de “a” ou un nombre pair de “b”;
    – tous les mots qui n’ont pas plus (>=) de quatre “a” consécutifs ;
    – Le langage L = {anbp, ntextrmmod3, n, p>=0}.
    – Donnez, si vous pouvez, des expressions régulières pour les langages précédents.

    Vous aimerez peut-être aussi