Théorie des langages : Exercices langages regulliers
Télécharger PDFSé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 ; w2 = 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 21) Σ = {a, b, ..., z}, décrire le langage défini par l’expression régulière : regarder(a(i|s|) | on(s|) | ez | ont).
2) Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, H}, décrire le langage défini par les expressions régulières suivantes :
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 correspondant aux langages suivants :
L1 = {ε, a, b, ab}
L2 = {bn / n ≥ 2, n étant un entier}
L3 = {w ∈ Σ*, tel que w contient exactement 3 b, le reste étant des a}
L4 = {w ∈ Σ*, tel que w contient un nombre de a divisible par 3}
L5 = {w ∈ Σ*, tel que w contient un nombre pair de a}
L6 = {w ∈ Σ*, tel que w contient un nombre impair de b}
L7 = {w ∈ Σ*, w ne contient pas 3 b consécutifs}
L8 = {w ∈ Σ*, 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 à états finis (AEF) reconnaissant les mots du langage.
2) Donner les AEF complets correspondants aux automates de la question 1. Un automate à états finis déterministe est complet si et seulement si δ est une fonction totale sur Q × Σ. Cela signifie que, 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 ajoutées, c’est-à-dire pour chaque état qui n’a pas de flèches étiquetées par des symboles de l’alphabet. Cet état comportera aussi des flèches vers lui-même, étiquetées par tous les symboles de l’alphabet.
FAQ
Q : Qu’est-ce qu’un langage régulier ?
R : Un langage régulier est un ensemble de chaînes de caractères sur un alphabet donné qui peut être décrit par une expression régulière ou reconnu par un automate à états finis.
Q : Comment reconnaître un langage régulier avec un AEF ?
R : Un automate à états finis (AEF) reconnaît un langage régulier si, à partir de son état initial, il accepte exactement les chaînes appartenant au langage. Les états finaux de l’automate marquent la fin des chaînes valides.
Q : Pourquoi certains langages ne sont-ils pas réguliers ?
R : Certains langages ne sont pas réguliers car ils nécessitent une mémoire infinie pour être reconnus, comme dans le cas des crochets ouvrants et fermants où l’on doit compter le nombre de crochets ouverts pour les fermer correctement.