Théorie des langages : Td 1 automatique
Télécharger PDFExercices sur les Mots et Langages en Théorie des Langages
Exercice 1
On considère l’alphabet V = {a, b, c}. Soient deux mots w = abc et q = cba.
1. Calculez w0, w1 et w2.
2. Calculez wq2w.
3. Calculez |w| et |w2|.
4. Donnez les préfixes et les suffixes du mot q.
5. Donnez le miroir du mot wq.
Exercice 2
On considère un alphabet V. Soient deux mots différents w1 ∈ V* et w2 ∈ V*. Montrer que : (w1w2)~ = w2~w1~.
Exercice 3
On considère l’alphabet V = {a, b}.
1. Soit le langage L = {w ∈ V* | w = (ab)nbmmm / n, m ≥ 0}. Parmi les mots suivants : ε, a, aa, ba, abbb, ababb, baba, quels sont ceux qui appartiennent au langage L ?
2. Même question avec le langage L = {w ∈ V* | w = (ab)nbmmm / n, m ≥ 0}.
Exercice 4
Soient les deux langages L1 = {ab, bb} et L2 = {a, ab, bc, ca}. Donnez :
L1 * (fermeture de Kleene de L1), L1 ∩ L2, L1 ∪ L2, L1 × L2, L2 × L1.
Exercice 5
Soient L1 et L2 deux langages. Démontrez que :
L1 ∪ L2 = L2 ∪ L1.
Exercice 6
1. Si L1 et L2 sont deux langages tels que L1 × L2 = {ε}, que peut-on dire de L1 et L2 ?
2. Si L3 et L4 sont deux langages et que L3 × L4 = ∅, que peut-on dire de L3 et L4 ?
3. Si L5 est un langage et que L5 * = {ε}, que peut-on dire de L5 ?
FAQ
Qu’est-ce qu’un miroir d’un mot en théorie des langages ?
Le miroir d’un mot est la version inversée de ce mot. Par exemple, le miroir de abc est cba.
À quoi correspond la fermeture de Kleene d’un langage ?
La fermeture de Kleene d’un langage L, notée L*, est l’ensemble de tous les mots formés par la concaténation de zéro ou plus de mots de L.
Quelle est la différence entre un préfixe et un suffixe ?
Un préfixe est une sous-séquence de début de mot, tandis qu’un suffixe est une sous-séquence de fin de mot. Par exemple, pour abc, les préfixes sont ε, a, ab, et les suffixes sont ε, c, bc.