Scribd
Importer
42 vues1 page

Grammaires et Automates : Exercices de Langages

Le document contient 10 exercices portant sur les automates finis, les expressions régulières et les grammaires régulières. Les exercices demandent de reconnaître des langages formels, de donner des expressions régulières ou des grammaires équivalentes.

Transféré par

yousrayos02
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
42 vues1 page

Grammaires et Automates : Exercices de Langages

Le document contient 10 exercices portant sur les automates finis, les expressions régulières et les grammaires régulières. Les exercices demandent de reconnaître des langages formels, de donner des expressions régulières ou des grammaires équivalentes.

Transféré par

yousrayos02
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Compilation l3A Serie 02 INF/UFAS I

ExerciceOl
Sur l'alphabet A= {a, b}, donner un automate fini deterministe reconnaissant les langages suivants :
- tous les mots contenant un nombre pair de "a" et un nombre pair de "b";
- tousles mots contenant un nombre pair de "a" ou un nombre pair de "b";
- tousles mots qui n'ont pas plus(>=) de quatre "a" consecutifs ;
- le langage L == {d'b", n = P mod 3, n, p>=O}.

Exercice 02
Donnez, si vous pouvez, des expressions regulieres pour les langages precedents.

Exercice 03
Cet automate reconnait quoi ? Donnez-en une expression reguliere,
H
(> ' ;'\ a-%
"-"--,.',\ .....2 ·'~--)
·,

Exercice 04
Si on l'utilise pour trouver des lexemes dans un fichier d'entree, combien de caracteres doit on examiner au pine apres
la fin d'un lexeme pour pouvoir I'identifier ?

Exercice 05
En general un analyseur lexical reconnait le plus long prefixe. Comment traiter le cas des commentaires de maniere 'a
ne pas oublier du code dans l' exemple ci-dessous en Caml ?
let f x = (* une fonction Cami *)
ifx mod 2 == 0 then x/2 else x+3;;
(* fin de la fondion Cami *)

Exercice 06
a. On considere I'alphabet (symboles terminaux) .E = {-+-, x, id, nb} dans lequel id et nb symbolisent respectivement
des identificateurs et des nombres. Soit la grammaire :
S --> id I nb I SS+ I SSx : Que representent les productions de cette grammaire ?
b. Donner deux derivations produisant : id id + nbx
c, Donner une grammaire produisant les expressions arithmetiques prefixees (operateurs +et x binaires),

Exercice 07
Donner une grammaire pour le langage {an b" I n2:0}

Exercice 08
a a
Un palindrome est un mot qui se lite de la meme maniere de gauche droite OU de droite gauche. Exemples : abba,
ababababa, ressasser. Ecrire une grammaire reconnaissant les palindromes sur I'alphabet {a,b}.

Exercice 09
En vous appuyant sur l'exemple suivant, imaginez un precede pour construire, a partir d'une grammaire reguliere, un
automate reconnaissant le meme langage.
S~abAlbaA
A~bBIB
B~ajabA
2. Imaginez le precede inverse: de I'automate vers la grammaire reguliere,

Exercice 10
Ecrire des grammaires reconnaissant les langages suivants. Sont-elles lineaires ? Regulieres ?
- Chaines de 0 et de 1 ou tout 0 est suivi d 'au moms un 1
~ Chain es de 0 et de 1 comprenant autant de 0 que de 1. V ariantes : langages bien parentheses.
~ Expressions arithmetiques prefixees ( exo 4)
- Palindromes (exo 8)

Vous aimerez peut-être aussi