Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Théorie des Langages – TD 1 et 2 ALPHABETS, LANGAGES ET GRAMMAIRES Exercice 1 -

Théorie des Langages – TD 1 et 2 ALPHABETS, LANGAGES ET GRAMMAIRES Exercice 1 - On considère l’alphabet X = {a,b,c}. On rappelle que |w| représente la longueur du mot w, et ε représente le mot vide. Soit deux mots w = ababc et q = caba. 1. Calculez w0, w1 et w2 2. Calculez wq2w 3. Calculez |w|ab, |(ab)4| et |(ab)4|aba 4. Donnez les préﬁxes, les préﬁces propres, les sufﬁxes et les sufﬁxes propres de q 5. Donnez le miroir du mot wq. Exercice 2 - 1. Montrez qu’il ne peut y avoir de mot x tel que ax = xb. 2. Quels sont les deux langages dont la fermeture par l’étoile donne le langage uniquement composé du mot vide ε ? 3. Les mots suivants sont-ils générés par le langage (ab∗)b∗: ε, a, aa, ba, abbb, ababb, baba ? Même question avec le langage (ab)∗b∗. Exercice 3 - On considère l’alphabet X = {a,b}. Donner les langages correspondant aux propriétés suivantes : 1. les mots qui ne contiennent aucun b ; 2. les mots qui ne contiennent pas ab ; 3. les mots qui contiennent au moins un a ; 4. les mots de longueur paire ; Exercice 4 - On considère l’alphabet X = {a,b,c}. 1. Calculez les ensembles X0, X1 et X2 2. Pour chacun des ensembles suivants, caractérisez L∗ 1, et calculez L1 ∩L2, L1 ∪L2, L1.L2, L2.L1 L1 = {ab,bb} et L2 = {a,ab,bbc,ca} L1 = {ε} et L2 = {bbc,ca} L1 = / 0 et L2 = {bbc,ca} L1 = {ab,bb} et L2 = X∗ 3. Soient L1 et L2. L1 = {w ∈X∗| |w| = 3n, avec n ∈N} L2 = {w ∈X∗| |w| = 5n, avec n ∈N} Caractérisez en français les langages L1 ∪L2, L1 ∩L2 Exercice 5 - On considère l’alphabet X = {a,b}, et les langages L1 et L2 suivants : L1 = {anbn|n ∈N} L2 = {bnan|n ∈N} Calculez L1 ∪L2, L1 ∩L2, L1.L2, L2.L1, L2 1. 1 Exercice 6 - On considère des langages sur un alphabet quelconque. 1. Démontrez les propriétés suivantes : L1 ⊆L2 ⇒L.L1 ⊆L.L2 L.(L1 ∪L2) = L.L1 ∪L.L2 2. Montrez que L.(L1 ∩L2) ⊆L.L1 ∩L.L2. A l’aide d’un contre-exemple, montrez que l’égalité n’est pas forcément atteinte. 3. Montrez que (L1 ∩L2)∗⊆L∗ 1 ∩L∗ 2. A l’aide d’un contre-exemple, montrez que l’égalité n’est pas forcément atteinte. Exercice 7 - On considère des langages sur un alphabet X quelconque. Soient les deux langages suivants : Lp = {w| |w|estpaire} Li = {w| |w|estimpaire} 1. Montrez que L2 p = Lp 2. Montrez que L+ p = Lp, puis que L∗ p = Lp 3. Montrez que Lp.Li = Li.Lp = Li 4. Montrez que L2 i = Lp \{ε}, puis que L∗ i = X∗ Exercice 8 - Soient les langages L1, L2 et L3 construits sur l’alphabet X = {a,b}. On rappelle que (a + b) = {a}∪{b}. L1 = {anb(a+ b)n,n ∈N} L2 = {(a+ b)nban,n ∈N} L3 = {(a+ b)nb(a+ b)n,n ∈N} 1. Montrez que les langages L1, L2 et L3 ne sont pas égaux 2. Soit L4 = {(a+ b)mban,m,n ∈N}. Montrez que L2 ̸= L4 3. Donnez les grammaires qui engendrent L2 et L4 Exercice 9 - Soit la grammaire G = ⟨V,Σ,P,S⟩, avec V = {a,b,S}, Σ = {a,b} et P = {S →aSa;S →bSb;S →ε}. 1. Soit G′ = ⟨V,Σ,P′,S⟩, avec P′ = P∪{S →SS}. Montrez que aabaab ∈L(G′). Montrez ensuite que G′ est ambigüe. 2. Quel est le langage engendré par G ? Démontrez 3. Pourquoi G n’est pas ambigüe ? Exercice 10 - Proposez une grammaire qui permet d’engendrer les formules de la logique des propositions. Exercice 11 - Soit la grammaire G = ⟨V,Σ,P,S⟩, avec V = {if,then,else,a,b,S}, Σ = {if,then,else,a,b} et P = {S →if b then S else S ; S →if b then S ; S →a}. 1. Démontrez que cette grammaire est ambigüe 2. Proposez une solution pour lever l’ambiguïté 2 uploads/Philosophie/ td1-2.pdf