Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Aut td1 L Licence d'Informatique - TD N Langages et Automates Expressions régulières a Donner une expression pour les langages suivants - a b aa ab ba bb - les mots constitués d'un seul a ou d'une cha? ne de a éventuellement vide suivie d'un b - les autom

L Licence d'Informatique - TD N Langages et Automates Expressions régulières a Donner une expression pour les langages suivants - a b aa ab ba bb - les mots constitués d'un seul a ou d'une cha? ne de a éventuellement vide suivie d'un b - les automates suivants b Comparer les langages dé ?nis par les expressions régulières en indiquant les inclusions éventuelles - a b et a b - a b c d et ac bd - a et a que peut-on dire de x dans le cas général o? x est une expression rationnelle - ba et a a b a comment peut-on caractériser ces deux langages - a b et ab Dé ?nitions régulières Pour écrire des expressions régulières en pratique sous Unix on utilise un certain nombre d'abréviations abc pour a b c a-z pour a b ? z a-zA-Z - pour toutes les lettres et chi ?res x pour un x optionnel Il est également commode d'introduire des dé ?nitions régulières d r d r ? d r n n o? les di sont des identi ?cateurs et les ri des expressions régulières sur ? ?? d ? d i- CExemple nombres suites de chifres ne commençant pas par chi ?renonnul - chi ?re chi ?renonnul nombrenonnul chi ?renonnul chi ?re N B nombrenonnul peut ensuite servir dans une autre dé ?nition cf plus loin a Un identi ?cateur est une suite de lettres ou de chi ?res commençant par une lettre Ecrire une dé ?nition régulière b Idem mais en imposant la première lettre soit une majuscule variables dans le langage de programmation Prolog c Un nombre entier divisible par d Chaines de lettres o? les voyelles apparaissent chacune une fois et o? elles sont dans l'ordre a e i o u avec répétitions possibles e Nombres réels tels que E E E- Décrire les langages reconnus par les automates suivants ? a b Construire les tables de transition des automates a b c Ecrire les automates reconnaissant les langages suivants a L L ' tous les mots non vides b L ab et L ab c L ab b Décrire la forme générale des mots de L L les mots qui ? ? d L le complémentaire de L Décrire la forme générale des mots de L e L mots se terminant par aa et qui ont un nombre pair de b NB Deux méthodes di ?érentes comme produit d' automates de manière directe CL Licence d'Informatique - Langages et Automates TD N - CORRECTION a b a b a b a ab a b ab ab a ab ab b a b contient a b a b c d contient ac bd a a et x x dans le cas général ba a a b a tous les mots qui ne ?nissent pas par b a b ab On a certaines égalités dans les expressions rationnelles a b ab a ab a ba b a aa etc Dé ?nitions régulières a lettre