SEG-2506 - Lab 6

Partie A: Expressions régulières et automates non déterministes

Exercice 1

Soit l’automate non-déterministe suivant:

• Décrivez (en français) le langage accepté par l'automate.
• Construisez un automate déterministe équivalent, en utilisant la méthode montrée en classe
  

Exercice 2

Soit l'alphabet L={a,b}. Soit l'expression régulière E=aa(a|b)*a

• Construisez un automate non-déterministe à partir de cette expression en utilisant l'algorithme de Thompson.
  

Exercice 3

Soit l'alphabet L={a,b}. Soit l'expression régulière définissant tous les mots qui terminent par abb ou par aaa. E=(a|b)*(abb|aaa)

1. Construisez un automate non-déterministe à partir de cette expression en utilisant l'algorithme de Thompson.
2. Construisez un automate déterministe équivalent, en utilisant la méthode montrée en classe
3. Trouver l'automate déterministe minimal (équivalent).

Partie B: Grammaires hors-contextes

Exercice 4: Construire un arbre syntaxique

Considérez la grammaire suivante :
E --> T | E - T | E + T
T --> SE | T * SE | T / SE
SE --> V | C | ( E )
V --> A | B
C --> 0 | 1 | 2 | 3

Écrivez un arbre syntaxique pour l'expression suivante:
A + ( 2 + B ) / ( 2 * A )

Exercice 5: Ambiguïté

Est-ce que la grammaire suivante est ambiguëe ? Expliquer en quelques mots pourquoi elle l'est ou ne l'est pas.

Grammaire (avec symbole de racine A) :
A --> a A c | a A | b

Exercice 6: Ambiguïté

Prouvez que la grammaire suivante est ambiguë:

S --> A B
A --> A id | id
B --> B id | id
id --> a | b | c

Exercice 7: Phrases générées

Nous considérons la grammaire suivante:
S --> S a B | A
A --> d A | c
B --> b | A

Lesquelles des phrases suivantes sont générées par cette grammaire ?

1. cab
2. c
3. cabb
4. caab
5. ccaabb
6. ccaab
7. ddcac

Exercice 8: Concevoir une grammaire

Écrivez une grammaire pour le langage qui consiste de toutes les chaînes formées des caractères a et b qui ont le même nombre de a que de b. Par exemple, les chaînes aabb, baba, et aabbababba font partie du language, mais pas les chaînes abb, bba, et aabbabb. Expliquez pourquoi votre grammaire fait l'affaire !

Exercice 9: Concevoir une grammaire

Écrivez une grammaire qui génère tous les phrases de la forme suivante:

• Une phrase commence avec un x qui est suivi par un certain nombre de y (au moins 2); puis il y a un certain nombre de z (possiblement zéro) suivi d'un u et un certain nombre de v, pour finalement se terminer avec un autre x. Le nombre de y doit être égal au nombre de v.

Pas besoin de préparer de rapport de laboratoire

À la fin du laboratoire, svp, montrez au TA les brouillons de textes et de diagrammes que vous avez préparés pour votre travail sur les exercices (1) à (9). Le TA prendra note de la complétude (ou non) de votre travail, mais n'évaluera pas la qualité de vos travaux.

Svp, consultez le TA pendant les sessions de laboratoire. Le rôle du TA est de vous aider à faire les travaux suggérés dans les laboratoires.