| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente |
| tc_info:2023-td-texte [2023/11/27 14:49] – [Exercice 5] edauce | tc_info:2023-td-texte [2023/11/30 14:51] (Version actuelle) – [Exercice 4 : Expressions régulières] edauce |
|---|
| ==== Exercice 4 : Expressions régulières ==== | ==== Exercice 4 : Expressions régulières ==== |
| |
| * Les langages réguliers sont un type de langage formel qui peuvent être reconnus par un automate fini. | * Les langages réguliers sont des types de langages formels qui peuvent être reconnus par un automate fini. |
| * Le langage des expressions régulières permet de décrire des motifs (c'est à dire des classes de mots) dans une chaîne de caractère. | * Le langage des expressions régulières est un langage régulier qui permet de décrire des motifs (c'est à dire des classes de mots) dans une chaîne de caractère. |
| |
| - Donnez l'expression régulière permettant de reconnaître les entiers relatifs et dessiner l'automate fini correspondant. | - Donnez l'expression régulière permettant de reconnaître les entiers relatifs et dessiner l'automate fini correspondant. |
| - Donnez l'expression régulière permettant de reconnaître les nombres décimaux (par exemple ''-3'', ''12.3'', ''-12.34'', ''+3'', ''0.'') et dessiner l'automate fini correspondant. | - Donnez l'expression régulière permettant de reconnaître les nombres décimaux (par exemple ''-3'', ''12.3'', ''-12.34'', ''+3'', ''0.'') et dessiner l'automate fini correspondant. |
| - Donnez l'expression régulière expression régulière qui valide les noms de fichiers se terminant par l'une des extensions spécifiées : ''.jpg'', ''.png'', ou ''.gif'' et dessiner l'automate fini correspondant. | - Donnez l'expression régulière expression régulière qui valide les noms de fichiers se terminant par l'une des extensions spécifiées : ''.jpg'', ''.png'', ou ''.gif'' et dessiner l'automate fini correspondant. |
| | - Donnez une expression régulière pour reconnaître les URL commençant par {{https://|https://}}... |
| | - Écrivez une expression régulière pour reconnaître la date et l'heure au format ''YYYY-MM-DD (HH:MM)'' |
| |
| ==== Exercice 5 ==== | ==== Exercice 5 ==== |
| - Ecrire l'algorithme de reconnaissance de l'expression régulière ''(a|b)*c'' | - Ecrire l'algorithme de reconnaissance de l'expression régulière ''(a|b)*c'' |
| - Dessiner son automate fini | - Dessiner son automate fini |
| - Soit ''G'' le graphe orienté décrivant cet automate, chaque arête étant indexée par un caractère | - Soit ''G'' le graphe orienté décrivant cet automate, chaque arête étant indexée par un caractère. Donner l'algorithme qui indique si oui ou non l'expression est reconnue dans une chaîne ''s'' à partir de son automate fini. |
| d'une expression dans une | |
| - L'algorithme qui indique si oui ou non l'expression est reconnue dans une chaîne ''s'' à partir de son automate fini. | |
| - tester cet algorithme sur l'automate (on suppose pour simplifier que l'automate est déterministe) | |
| - Quelle est sa complexité? | - Quelle est sa complexité? |
| |
| |
| | ==== Exercice 6 ==== |
| | |
| | - Ecrire l'algorithme de reconnaissance de l'expression régulière ''(a|b)*ab'' |
| | - Dessiner son automate fini |
| | - Soit ''G'' le graphe orienté décrivant cet automate, chaque arête étant indexée par un caractère. Donner l'algorithme qui indique si oui ou non l'expression est reconnue dans une chaîne ''s'' à partir de son automate fini. |
| | - Quelle est sa complexité? |
| |