Td 1 automate langage formel Théorie des langages-téléc...

Théorie des langages : Td 1 automate langage formel

Télécharger PDF

ISG, Année Universitaire : 2011/2012 Théorie des Langages et des Automates : (2

ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI

- TD : Mr Badr MEFTAHI _________________________________________________________________________________________________________________ Série N°1 : Alphabet et Langages Formels

Exercice 1

1) Proposer un ensemble fini de symboles qu’on appelle å. 2) å est appelé alphabet. Un mot ou une chaîne est une séquence de symboles appartenant à un alphabet, proposer 4 mots définis sur l’alphabet å et donner leurs tailles (nombre d’occurrence de symboles dans le mot). 3) Pour un mot proposé w, donner des exemples de préfixes de w et de suffixes de w. 4) Peut-on parler de mot vide ? Que peut-on en dire sur sa taille ? 5) å

* est l’ensemble infini de tous les mots que nous pouvons construire sur l’alphabet å , un langage est un sous ensemble de å

*. Proposer deux langages définis sur l’alphabet å*. 6) Soit l’alphabet å = {h,t,s} donner la taille du mot w1 = hhththts. 7) Soit l’alphabet å = {h,th,s} donner la taille du mot w1 = hhthths.

Exercice 2

Soient les langages suivants définis sur un alphabet å avec å un ensemble constitué de symboles de longueur 1: L

1 = {abc, abcd, cba, dcba} L

2 = { u Î å

* / u = 01 ou u = 0101000 } L

3 = l’ensemble de toutes les chaînes constituées des symboles * et de la chaîne vide. 1) Déterminer l’ensemble å pour chacun des langages L1 , L

2 , et L

3, notés åL1 , å

L2 et åL3 . 2) Que peut-on remarquer sur ces trois langages ? 3) Proposer 3 mots w

1 , w

2 , et w

3 tels que : w

1 Î åL1 * avec | w

1 | = 10 , w

2 Î åL2 * avec | w

2 | = 4 et w

3 ÎåL3 * avec | w

3 | = 12. 4) A-t-on w

1 Î L

1 , w

2 Î L

2 et w

3 Î L

3 ? Comparer alors L

i et å*

Li (i=1, 2, 3). 5) A-t-on e Î L

1 ? e Î L

2 ? Justifier vos réponses. 6) Soit L

4 = l’ensemble des mots formés sur l’alphabet å

L2 commençant par 1. Formuler L

4 d’une manière formelle ainsi que L3 . 7) Soit L

5 = åL2 *

. Quel est le langage L

5 ? 8) Soit L

6 = L1 . L

2 et L

7 = L1 . L5 . Spécifier formellement L

6 et L7 .

Exercice 3

(cas pratique) 1) Proposer 5 éléments de l’alphabet relatif au langage C (ou C++) 2) Donner une phrase (un mot) appartenant à ce langage et de taille égale à 4.

Exercice 4

Donner des définition par propriétés puis par récurrence des langages suivants : Les 3 langages sont définis sur l'alphabet å = {a,b} L1 : l'ensemble des mots qui se terminent par b (exemples : ab, aaaaaab, aaaaaaaaab, ...} L2 : L'ensemble des mots de longueur impaire. L3 : L'ensemble des mots qui comportent la séquence aaa (pas d'autres a).