(1) Expressions régulières: Nous considérons des langages sur l'alphabet (vocabulaire) de deux lettres: V={a, b}. Donnez des expressions régulières qui correspondent aux langages définis informellement ci-dessous:

1. Toutes les phrases qui commencent par aa.
   
2. Toutes les phrases qui contiennent aa.
   
3. Toutes les phrases qui contiennent un nombre pair de lettres.
   
4. Toutes les phrases qui contiennent un nombre pair d'occurences du lettre a.
   
5. Toutes les phrases dont la longueur est un multiple de 5.
   
6. Toutes les phrases qui contiennent trois a consécutifs.
   
7. Toutes les phrases qui ne contiennent pas trois a consécutifs.
   

(2) Automates: Pour chacun des langages ci-hauts, trouvez un automate (détermniste) qui accepte le langage.

(3) Automate correspondant à une expression régulière: Pour chaque expression régulière ci-dessous, donnez un automate (détermniste) qui accepte le language défini par l'expression régulière:

1. L = (a | b) c         ex. {ac, bc}
2. L = a* b                ex. {b, ab, aab, aaab, ...}
   
3. L = a* (a b c)*
4. L = (a | b)*
5. L = (a | b) c* c b b*

(4) Automate non déterministe: L'automate suivant est non déterministe. Questions:

1. Dans quel état pourrait être l'automate après avoir lu la séquence " a, a, c, c "
   • Est-ce que cette séquence est acceptée par l'automate ?
2. Dans quel état pourrait être l'automate après avoir lu la séquence " a, c, a, c "
   • Est-ce que cette séquence est acceptée par l'automate ?
3. Dans quel état pourrait être l'automate après avoir lu la séquence " a, a, b, c"
   • Est-ce que cette séquence est acceptée par l'automate ?

(5) Équivalences: Nous considérons les pairs d'expressions régulières suivants. Pour chaque pair, indiquez si les deux expressions désignent le même langage ou non. Si elle désignent le même langage, donnez une preuve de l'égalité des langages en utilisant les propriétés algébriques des opérateurs des expressions régulières. Si elle désignent des langages différents, donnez un exemple de chaîne qui fait partie de l'un des langages mais pas de l'autre.

1. ab(abc)*ab             aba(bca)*b
2.    (a | b)*                   (  a* b* )+

(6) Jouer avec le programme egrep: Ce programme est disponible sous Unix et peut être appelé avec une commande Unix. Essayez d'utiliser l'outil egrep (qui fait la recherche d'un patron défini par une expression régulière) pour vous familiariser avec les expressions régulières. Par exemple, si le fichier test.txt contient la chaîne accbbb et si vous utilisez

egrep "(a|b)c*cbb*" test.txt

vous allez voir toutes les lignes du fichier qui contiennent un patron "(a|b)c*cbb*", tel que accbbb.

Note: Vous pouvez utiliser le tutoriel RegexOne pour vous familiariser avec la notation utilisée par egrep, la classe Pattern en Java, et Lex.

(7) Programmer un simple analyseur en Java: Svp, écrire un programme simple en Java qui demande l'usager une chaîne de caractères, et qui vérifie si la chaîne contient une sous-chaîne correspondant à l'expression a*b. Il devrait sortir toutes les sous-chaînes de cette sorte.

(8) Utiliser la classe Pattern de Java: Le package utilitaire regex de Java contient les classe Pattern et Matcher (voir Java documentation). Le méthode compile de la classe Pattern génère un "pattern" qui peut être utilisé pour créer un objet "matcher" qui contient un algorithme pour analyser une chaîne de caractères pour la présence d'un patron défini par une expression régulière (de type regex) qui était donnée comme paramètre à la méthode compile. Voici un programme exemple qui utilise ces classes, préparé par Ahmed Jeddah inspiré par l'exemple dans un tutoriel Java qui contient aussi des explications sur la syntaxe des expressions régulières acceptées par Pattern. Vous avez les tâches suivantes:

1. Lire le programme et le comprendre (consulter la documentation sur les méthodes utilisées dans le progamme)
2. Exécuter le programme dans votre environnement Java et le tester avec plusieurs expressions régulières et plusieurs châines de caractères à analyser. Vous pouvez vous servir des exemple donnés ci-haut.