Théorie des langages : Exercices langages regulliers
Télécharger PDFISG, Année Universitaire : 2011/2012 Théorie des Langages et des Automates : (2
ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI
- TD : M. Badr MEFTAHI _________________________________________________________________________________________________________________ Série N°2 : Langages Réguliers
Spécifications par des expressions régulières et Reconnaissance par des AEF
Exercice 11) Le langage décrivant les chaînes de caractères (en Pascal ou en C par exemple) en binaire est-il un langage régulier ? justifier. 2) Peut-on dire que le langage des mots définis sur l’alphabet å = {# , i, j} qui commencent par des chaînes non vides constituées aléatoirement de symboles i et/ou j suivis de la sous chaîne ## puis d’un nombre supérieur à 1 de i et enfin un j (exemples de mots : w1 = ijiiijiij##iiiij ; w1 = j##iij ) est un langage régulier ? pourquoi ? 3) Le langage des crochets ouvrants et fermants (si on ouvre un crochet, on doit systématiquement le fermer) est –il régulier ? justifier.
Exercice 2Décrire les langages définis par les expressions régulières suivantes (on donne d’abord l’alphabet puis l’expression régulière). 1) å = {a, b, ..., z} , regarder(ai | as | a | ons | ez | ont) 2) å = {0, 1, 2, 3, 4, 5, 6, 7, 8 , 9,H} ,
0 (0 é 1 é 2 é 3 é 4 é 5 é 6 é 7 é 8 é 9) é 10 é 11 é 12) H (0 é 1 é 2 é 3 é 4 é 5) (0 é 1 é 2 é 3 é 4 é 5 é 6 é 7 é 8 é 9).
Exercice 3Soit l'alphabet å = {a,b}, Donner les expressions régulières correspondants aux langages suivants : L1 = {e, a, b, ab} L2 = {b
n / n>=2, n étant un entier} L3 = {wÎ{a,b}*, tel que w contient seulement 3b, le reste c'est des a's} L4 = {wÎ{a,b}*, tel que w contient un nombre de a divisible par 3} L5 = {wÎ{a,b}*, tel que w contient un nombre paire de a} L6 = {wÎ{a,b}*, tel que w contient un nombre impaire de b} L7 = {wÎå*, w ne contient pas 3b consécutifs} L8 = {wÎ{a,b}*, tel que w contient la sous chaîne aaa ou la sous chaîne bbb mais pas les
deux en même temps}
Exercice 41) Proposer pour chacun des langages L1, L2, L3 et L5 de l’exercice 3 un automate d’état fini (AEF) reconnaissant les mots du langage. 2) Donner les AEF complets correspondants aux automates de la question 1. Un automate à états fini déterministe est complet si et seulement si δ est une fonction totale sur Q x Σ. C'est à dire de chaque état, il part exactement une flèche étiquetée par chacune des lettres de l'alphabet Σ. Dans la pratique, on doit créer un état "spécial" qui est ni initial ni final et vers lequel se dirigent toutes les flèches qu'on ajoute c'est-à-dire pour chaque état qui n'a pas de flèche étiquetées par des symboles de l'alphabet, on les crée et ils se dirigent vers cet état ISG, Année Universitaire : 2011/2012 Théorie des Langages et des Automates : (2
ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI
- TD : M. Badr MEFTAHI spécial; en plus, cet état comportera aussi des flèches vers lui-même qui sont étiquetés par tous les symboles de l'alphabet.