Td 1 automates - Théorie des langages

Théorie des langages : Td 1 automatique

Télécharger PDF

1 UNIVERSITE DE CONSTANTINE 2 Faculté des NTIC Module : TL / Licence 2

ème année

Année 2019/2020

TD n°1

Exercice 1

On considère l’alphabet V = {a, b, c}. Soit deux mots w = abc et q = cba. 1. Calculez w0 , w1 et w2 2. Calculez wq2 w 3. Calculez |w| et | w2 | 4. Donnez les préfixes et les suffixes de q 5. Donnez le miroir du mot wq.

Exercice 2

On considère l’alphabet V . Soient deux mots différents w1 ∈∈∈ ∈ V∗ ∗∗

∗ et w2 ∈∈∈ ∈ V∗ ∗∗∗ Montrer que : ( w

1 . w2 ) ̃= w

2 ̃ . w

1 ̃

Exercice 3

On considère l’alphabet V = {a, b}.

1. Soit le langage L ={w ∈∈∈ ∈ V* / w = (ab

n )bm /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)n bm mm

m /n,m>= 0}

Exercice 4

Soient les deux langages L

1 et L

2 tels queL 1

= {ab, bb} et L2 = {a, ab,bc, ca}

Donnez : L1 ∗∗∗ ∗ , L1 ∩ L2 , L1 ∪∪∪ ∪ L2 , L1 xL2 , L2 xL1

Exercice 5

Soient L

1 et L

2 deux langages, démontrez que

Exercice 6

1. Si L

1 et L

2 sont deux langages tel que L1 x L2 ={εεε ε} Que peut-on dire de L

1 et L

2 ? 2. Si L

3 et L

4 sont deux langages et que L3 xL

4 =000 0/// / Que peut-on dire de L

3 et L

4 ? 3. Si L

5 est un langage et que L5 *={εεε ε} Que peut-on dire de L

5 ?