Qui connait la reponse vrai?

[Anonyme]

Langages
Exercice 1
L’alphabet ´etant ;)= {a, b}, on note L le langage : L = a*b = b + ab + a2b + ... + anb + ....
1. Pour chacun des langages suivants, donner la liste des mots de longueur inf´erieure ou
´egale `a 4 :
L , L2 , L3 , L4.
2. Le mot abbaab appartient-il `a l’un des langages Ln ? Si oui, lequel ?
Mˆeme question pour les mots : ababa, abbaab et aabaabb.
3. Montrer que tous les mots de Ln (n ;) 1) se terminent par une occurrence de la lettre
b.
4. Pour n ;) 1, combien chaque mot de Ln contient-il d’occurrences de la lettre b ?
5. [facultatif ] On note : L+ = L+L2+L3+...+Ln+..., et M = ;)*b (M est donc l’ensemble
des mots se terminant par une occurrence de la lettre b). Montrer que L+ = M.



_____________________________________________________________

Automates
Exercice 2
L’alphabet ´etant ;)= {a, b}, on note A l’automate dont le diagramme est :

b
;) (1) ;) (2)
a ;) b a ;)
(4) b ;) (3)
a,b b a ;)
(5) a


1. Donner la liste des mots de longueur inf´erieure ou ´egale `a 5 reconnus par cet automate.
2. ´Ecrire le syst`eme du d´epart de A, et le r´esoudre compl`etement (c’est-`a-dire, d´eterminer
tous les langages du d´epart de A).
En d´eduire le langage L accept´e par A.
3. ´Ecrire le syst`eme de l’arriv´ee de A, et le r´esoudre compl`etement (d´eterminer tous les
langages de l’arriv´ee de A).



_____________________________________________________________

Applications, ensembles et cardinaux
Exercice 1
Soient E = {0, 1, 2, 3, 4, 5}. On note f, l’application de E ;)! E d´efinie par la
table de valeurs :

n 0 1 2 3 4 5
f(n) 2 4 5 1 0 3
h, l’application de E ;)! E d´efinie par : h(n) = 5 ;) n,
p, l’application de E ;)! E d´efinie par : p(n) = { n + 1, si n < 5
{ n ;) 5, si n ;) 5 .
1. f est-elle bijective ?
2. h est-elle bijective ?
3. Donner les tables des valeurs de f2 = f o f, de f3 = f o f o f, et de h.
4. Quelle est l’application h o h ? Quelle est la fonction reciproque de h ?
5. On note,
pm = p o p o · · · o p
| m{fzois }
a- D´eterminer m pour que pm = Id, Id ´etant l’application identit´e de E ;)! E.
b- D´eterminer un entier m tel que pm o h = f3 et un entier q tel que h o pq = f3
(en vous aidant des r´esultats de la question 2).
Indication : pour cette question, se servir des tables de valeurs des diff´erentes
applications compos´ees (par exemple, celles de p, puis p2, jusqu’`a pm, tel que
pm = Id).
6. En d´eduire une expression de la fonction r´eciproque de f3 `a l’aide de h et de
p.
Exercice 2
Soient les ensembles E = {a, b} et F = {0, 1}.
1. Ecrire la liste des ´elements de E × F et celle de E2.
2. Quel est le cardinal de (E × F)n, pour n entier positif.
3. Ecrire la liste des ´el´ements de P(E). Caract´eriser (sans les enumerer) les
´elements de P(E × F). En deduire P(E) \ P(E × F).
4. Calculer le cardinal de P(E) et celui de P2(E) = P(P(E)).

_________________________________________________________________

qui connait la reponse vrai?