Théorie des langages : Td 1 automate langage formel
Télécharger PDFSérie N°1 : Alphabet et Langages Formels
Exercice 1
1) Proposer un ensemble fini de symboles qu’on appelle α. 2) α est appelé alphabet. Un mot ou une chaîne est une séquence de symboles appartenant à un alphabet. Proposer 4 mots définis sur l’alphabet α et donner leurs tailles (nombre d’occurrences de symboles dans le mot).
Exemple : Si α = {0, 1}, alors les mots suivants peuvent être proposés : - mot1 = 010 (taille = 3) - mot2 = 111 (taille = 3) - mot3 = 0011 (taille = 4) - mot4 = 0 (taille = 1)
3) Pour un mot proposé w, donner des exemples de préfixes de w et de suffixes de w. Exemple : Si w = 0110, alors : - préfixes : 0, 01, 011, 0110 - suffixes : 0, 10, 110, 0110
4) Peut-on parler de mot vide ? Que peut-on en dire sur sa taille ? Le mot vide, noté ε, est une chaîne contenant aucun symbole. Sa taille est égale à 0.
5) α* est l’ensemble infini de tous les mots que nous pouvons construire sur l’alphabet α. Un langage est un sous-ensemble de α*. Proposer deux langages définis sur l’alphabet α*.
Exemple : Si α = {a, b}, alors : - langage1 = {aa, ab, ba} - langage2 = {tous les mots de longueur paire}
Exercice 2
Soient les langages suivants définis sur un alphabet α, avec α un ensemble constitué de symboles de longueur 1 : L1 = {abc, abcd, cba, dcba} L2 = {u ∈ α* / u = 01 ou u = 0101000} L3 = l’ensemble de toutes les chaînes constituées des symboles α et de la chaîne vide.
1) Déterminer l’ensemble α pour chacun des langages L1, L2, et L3, notés αL1, αL2, et αL3. - αL1 = {a, b, c, d} - αL2 = {0, 1} - αL3 = {0, 1} (ou tout autre alphabet fini)
2) Que peut-on remarquer sur ces trois langages ? L1 est un ensemble fini de mots, L2 est un ensemble fini de mots spécifiques, et L3 est un ensemble infini incluant la chaîne vide.
3) Proposer 3 mots w1, w2, et w3 tels que : w1 ∈ αL1* avec |w1| = 10, w2 ∈ αL2* avec |w2| = 4, w3 ∈ αL3* avec |w3| = 12.
Exemple : - w1 = aabbbccdd (si αL1 = {a, b, c, d}) - w2 = 0101 - w3 = 001100110011 (si αL3 = {0, 1})
4) A-t-on w1 ∈ L1, w2 ∈ L2, et w3 ∈ L3 ? Comparer alors Li et α*.
Réponse : - w1 n’appartient pas à L1 (L1 est un ensemble fini de mots spécifiques). - w2 appartient à L2 (car 0101 est soit 01, soit 0101000). - w3 appartient à L3 (car c’est une chaîne de symboles 0 et 1). L1 est un sous-ensemble fini de α*, L2 est un sous-ensemble fini de α*, et L3 est un sous-ensemble infini de α*.
5) A-t-on ε ∈ L1 ? ε ∈ L2 ? Justifier vos réponses. - ε n’appartient pas à L1 (car L1 ne contient que des mots de longueur ≥ 3). - ε appartient à L2 si la définition inclut la chaîne vide (sinon, non).
6) Soit L4 = l’ensemble des mots formés sur l’alphabet αL2 commençant par 1. Formuler L4 d’une manière formelle ainsi que L3.
L4 = {u ∈ αL2* / u commence par 1}. L3 = {tous les mots construits sur l’alphabet αL3}.
7) Soit L5 = αL2*. Quel est le langage L5 ? L5 = l’ensemble infini de tous les mots construits sur l’alphabet αL2.
8) Soit L6 = L1 · L2 et L7 = L1 · L5. Spécifier formellement L6 et L7.
L6 = {w ∈ αL1* · αL2* / w = x · y, où x ∈ L1 et y ∈ L2}. L7 = {w ∈ αL1* · αL2* / w = x · y, où x ∈ L1 et y ∈ αL2*}.
Exercice 3
(cas pratique) 1) Proposer 5 éléments de l’alphabet relatif au langage C (ou C++). Exemple : { ; , ( , ) , { , } , = , + , - , * , / , % , < , > , <= , >= , == , != , # , #include , #define , if , else , for , while , int , float , double , char , void , main , printf , scanf }
2) Donner une phrase (un mot) appartenant à ce langage et de taille égale à 4. Exemple : int x = 5;
Exercice 4
Donner des définitions par propriétés puis par récurrence des langages suivants : Les 3 langages sont définis sur l’alphabet α = {a, b}.
L1 : l’ensemble des mots qui se terminent par b.
Définition par propriétés : Un mot w ∈ L1 si et seulement si w ∈ α* et w se termine par b.
Définition par récurrence : - ε ∉ L1. - Si w ∈ L1 et x ∈ α, alors xw ∈ L1. - b ∈ L1.
L2 : l’ensemble des mots de longueur impaire.
Définition par propriétés : Un mot w ∈ L2 si et seulement si w ∈ α* et |w| est impair.
Définition par récurrence : - ε ∉ L2. - Si w ∈ L2 et x ∈ α, alors xw ∉ L2. - Si w ∉ L2 et x ∈ α, alors xw ∈ L2 si |w| est pair. - a ∈ L2, b ∈ L2.
L3 : l’ensemble des mots qui comportent la séquence aaa (pas d’autres a).
Définition par propriétés : Un mot w ∈ L3 si et seulement si w ∈ α* et w contient exactement la séquence aaa.
Définition par récurrence : - ε ∉ L3. - Si w ∈ L3 et x ∈ {b}, alors xw ∈ L3. - aaa ∈ L3. - Si w ∈ L3 et x ∈ {b}, alors w · x ∈ L3.
FAQ
1. Qu’est-ce qu’un alphabet en théorie des langages ?
Un alphabet est un ensemble fini de symboles utilisés pour construire des mots ou chaînes dans un langage formel.
2. Comment définir un langage par récurrence ?
Un langage est défini par récurrence en spécifiant : - une base (mots de départ), - des règles de construction (comment former de nouveaux mots à partir des existants).
3. Que signifie un mot de longueur impaire ?
Un mot de longueur impaire est une chaîne composée d’un nombre impair de symboles (exemple : "ab" a une longueur de 2, donc paire ; "aba" a une longueur de 3, donc impaire).