| 1) |
Trouver une grammaire non contextuelle (BNF) pour les langages suivants. [8 credits]
- Tous les palindromes sur l'alphabet T = {a, b, c}. Un palindrome est un mot symétrique;
par ex. aa,aba, bbccbb, etc.
- Tous les mots sur l'alphabet T = {a, b} de longueur paire; par ex. bb, abaa,
abbaba, etc.
- Tous les mots sur l'alphabet T = {a, b} qui commencent et finissent par un a;
par ex. a, abaa, ababba, etc.
- Tous les mots sur l'alphabet T = {a, b} formés de
n a's suivis par (n-1) b's, n > 0; par ex. a, aab,
aaaabbb, etc.
|
| 2) |
Parmi les langages de la question 1, lesquels sont réguliers ? Pour ceux qui le sont, prouvez-le.
[3 credits]
|
| 3) |
Les grammaires suivantes définissent des langages réguliers. Donner une seule
règle EBNF non récursive pour chaque grammaire. [6 credits]
-
A = A b | A c | a
-
A = a A | A b b | c
-
A = A a | A A A | c
Le mot caacac appartient au langage décrit par la troisième grammaire. Dessinez un arbre
de dérivation de ce mot correspondant à cette grammaire BNF.
|
| 4) |
Trouvez une grammaire EBNF non récursive qui spécifie la syntaxe des nombres à virgule flottante.
Les nombres suivants doivent appartenir au langage défini par votre grammaire: [3 credits]
-3.1415927, 1.4e10, 127.0e-2, -0.1e-1, .0
Les nombres entiers comme 1, 4589 ou -000335
(i.e. les nombres sans point dans leur représentation) ne doivent pas être couverts par votre grammaire.
|
|
