Théorie des langages : Td 1 mots langages automates
Télécharger PDFTD 1 : Mots, langages, automates
Soit Σ un alphabet fini. Le mot vide est noté ε.
Exercice 1
Généralités
1. Compter les occurrences des lettres a et b dans les mots suivants : a³cbbca, aabgjdd, titi, babc.
2. Donner l’ensemble des couples (u, v) tels que u·v = abaac.
3. Calculer L·M pour les ensembles suivants :
- L = {a, ab, bb} et M = {ε, b, a²};
- L = ∅ et M = {a, ba, bb};
- L = {ε} et M = {a, ba, bb};
- L = {aa, ab, ba} et M = Σ*.
4. Un mot u est un facteur d’un mot v si u apparaît à l’intérieur de v : v s’écrit w₁·u·w₂ pour certains mots w₁ et w₂. Un mot u est un sous-mot d’un mot v si on peut obtenir u à partir de v par « effacement » de certaines lettres (pas forcément consécutives) de v. Le nombre d’occurrences d’un facteur (resp. sous-mot) u dans le mot v est le nombre de façons de voir u comme facteur (resp. sous-mot) de v.
Donner le nombre d’occurrences du facteur aba dans le mot v = ababab. Donner le nombre d’occurrences du sous-mot aba dans le même mot v.
5. Montrer que le produit est une opération distributive par rapport à l’union, c’est-à-dire que, pour tous langages L, M et N, on a : L·(M∪N) = (L·M)∪(L·N). Montrer que le produit n’est pas distributif par rapport à l’intersection.
Exercice 2
Un peu de grep
La commande grep -E 'regexp' fichier retourne les lignes d’un fichier où l’on reconnaît l’expression régulière regexp. Une expression régulière est formée à partir de lettres de l’alphabet (chaque lettre constituant un élément) et des symboles suivants :
- ∗ indique que l’élément précédent apparaît un nombre quelconque de fois (y compris zéro) ;
- + indique que l’élément précédent apparaît au moins une fois ;
- (et) entourent une expression régulière pour former un groupe ;
- | indique une disjonction entre deux expressions régulières (on reconnaît l’une ou l’autre) ;
- ? indique que l’élément précédent est facultatif (i.e., il apparaît au plus une fois).
Une expression régulière représente donc un ensemble de mots sous forme condensée (c’est-à-dire un langage).
Soit tutu le fichier contenant : caa cbbabcabab caaabba.
1. Que répond la commande grep -E 'regexp' tutu lorsque regexp vaut respectivement :
- ca* ;
- c(ab)+ ;
- ca+(a∗b∗) ;
- (aa+)|(bb+) ;
- baa?b ;
- a∗.
Pourquoi ?
2. Décrire sous forme ensembliste le langage correspondant aux expressions régulières précitées.
Exercice 3
Calcul par un automate
L’alphabet considéré est {a, b}.
1. Dans quel état se trouve l’automate A₁ après lecture des mots a, ab, abb, abba ? Après lecture du mot ε ?
2. Lesquels de ces mots sont reconnus par l’automate A₁ ?
3. Que se passe-t-il quand on donne le mot aab à lire à l’automate A₁ ?
4. Les mots aba²b, a²ba²b, ab⁴ et b³a² sont-ils reconnus par l’automate A₁ ?
5. Décrire les mots reconnus par l’automate A₁.
6. Après lecture du mot b³a², dans quel état se trouve l’automate A₂ ?
7. Y a-t-il des mots que l’automate A₂ ne peut pas lire jusqu’au bout ?
8. S’il n’a lu aucune lettre, dans quel état se trouve l’automate A₂ ?
9. Dans quels cas l’automate A₂ se trouve-t-il dans l’état 1 ?
10. Dans quels cas arrive-t-il à l’état final 2 ? Quels mots reconnaît-il ?
Exercice 4
Commutation
Soient u et v deux mots. On dit que u et v commutent si u·v = v·u.
Montrer que u et v commutent si et seulement s’il existe un mot w et deux entiers positifs ou nuls m et n tels que u = wᵐ et v = wⁿ. Pour le sens ⇒, on pourra procéder par récurrence sur |u| + |v|.
FAQ
Qu’est-ce qu’un alphabet fini en théorie des langages ?
Un alphabet fini est un ensemble fini de symboles, par exemple {a, b}, {0, 1}, ou {c, d, e}. Ces symboles sont utilisés pour construire des mots ou des langages.
Comment différencier un facteur d’un sous-mot dans un mot ?
Un facteur est un sous-mot consécutif (ex. aba dans ababab), tandis qu’un sous-mot est un sous-ensemble non consécutif de lettres (ex. aba obtenu en effaçant b de ababab).
Que signifie la notation Σ* ?
Σ* désigne l’ensemble de tous les mots possibles construits à partir des lettres de l’alphabet Σ, y compris le mot vide ε. Par exemple, si Σ = {a, b}, alors Σ* contient ε, a, b, aa, ab, etc.