Td 1 mots langages automates Théorie des langages-téléc...

Théorie des langages : Td 1 mots langages automates

Télécharger PDF

Université Paris DiderotAnnée 2007–2008AF4

TD 1 : Mots, langages, automates

Adésigne un alphabet fini. Le mot vide est notéε.

Exercice 1

Généralités

1. Compter les occurrences des lettresaetbdans les mots suivants :a3 cbbca,aabgjdd,titi,babc. 2. Donner l’ensemble des couples(u, v)tels queu·v=abaac.

3. CalculerL·Mpour les ensembles suivants :

–L={a, ab, bb}etM={ε, b, a2 };

–L=∅etM={a, ba, bb};

–L={ε}etM={a, ba, bb};

–L={aa, ab, ba}etM=A∗ .

4. Un motuest unfacteurd’un motvsiuapparaît à l’intérieur dev:vs’écritw1 ·u·w2 pour

certains motsw1 etw2 . Un motuest unsous-motd’un motvsi on peut obteniruà partir

devpar « effacement » de certaines lettres (pas forcément consécutives) dev. Le nombre

d’occurrencesd’un facteur (resp. sous-mot)udans le motvest le nombre de façons de voir

ucomme facteur (resp. sous-mot) dev.

Donner le nombre d’occurrences du facteurabadans le motv=ababab. Donner le nombre

d’occurrences du sous-motabadans le même motv.

5. Montrer que le produit est une opération distributive parrapport à l’union, c’est-à-dire que,

pour tous langagesL,MetN, 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 degrep

La commandegrep -E ’regexp’ fichierretourne les lignes d’un fichier où l’on reconnaît l’expression

régulièreregexp. Une expression régulière est formée à partir de lettres de l’alphabet (chaque lettre

constituant unélément) et des symboles :

–∗qui indique que l’élément précédent apparaît un nombre quelconque de fois

–+qui indique que l’élément précédent apparaît au moins une fois

–(et)qui entourent une expression régulière pour former un élément

–|qui indique une disjonction entre deux expressions régulières (on reconnaît l’une ou l’autre)

–?qui indique que l’élément précédent est facultatif (i.e. ilapparaît au plus une fois).

Une expression régulière représente donc sous forme condensée un ensemble de mots (c’est-à-dire

unlangage).

Soittutule fichier contenant :caa cbbabcabab caaabba

1. Que répond la commandegrep -E ’regexp’ tutulorsqueregexpvaut respectivement :–ca +–c(ab) +–ca +(a ∗b ∗) –(aa+ )|(bb+ )–baa?b –a∗ et pourquoi ?

2. Décrire sous forme ensembliste le langage correspondantaux expressions régulières précé-dentes. Université Paris DiderotAnnée 2007–2008AF4012 a, ba b

(a) AutomateA1 012b aa b

a, b

(b) AutomateA2

Exercice 3

Calcul par un automate

L’alphabet considéré est{a, b}.

1. Dans quel état se trouve l’automateA1 après lecture des motsa,ab,abb,abba? Après lecture

du motε?

2. Lesquels de ces mots sont reconnus par l’automateA1 ?

3. Que se passe-t-il quand on donne le motaabà lire à l’automateA1 ?

4. Les motsaba2 b,a2 ba2 b,ab4 etb3 a2 sont-ils reconnus par l’automateA1 ?

5. Décrire les mots reconnus par l’automateA1 .

6. Après lecture du motb3 a2 , dans quel état se trouve l’automateA2 ?

7. Y a-t-il des mots que l’automateA2 ne peut pas lire jusqu’au bout ?

8. S’il n’a lu aucuna, dans quel état se trouve l’automateA2 ?

9. Dans quels cas l’automateA2 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

Soientuetvdeux mots. On dit queuetvcommutentsiu·v=v·u.

Montrer queuetvcommutent si et seulement s’il existe un motwet deux entiers positifs ou nuls

metntels queu=wm etv=wn . Pour le sens⇒, on pourra procéder par récurrence sur|u|+|v|.