Université de Nice-Sophia Antipolis École Supérieure en Sciences Informatiques

2004–2005

Contrôle de Mathématiques Discrètes du 20 octobre 2004

Nom : Prénom : Groupe:

Durée : 55 minutes

1 2 3 4 5 6

1

Que représente le symbole ϵ ?

2

On considère l’ensemble E défini de manière inductive par

– Base : ϵ ∈ E

– Règles :

– Si m ∈ E alors 10m ∈ E – Si m ∈ E alors 01m ∈ E – Si m ∈ E alors m10 ∈ E – Si m ∈ E alors m01 ∈ E

Soit M le sous-ensemble de {0,1}^{∗} formé des mots ayant autant de 0 que de 1. 1. A-t-on M inclus dans E?

2. A-t-on E inclus dans M?

3. Montrer que le schéma définissant E n’est pas libre

4. Modifier le schéma pour le rendre libre (sans modifier l’ensemble E obtenu, bien sûr)

Donner et prouvez un schéma inductif pour {(m,n) ∈ N^{2},m ≤ n}

Donner et prouver un schéma inductif pour l’ensemble des entiers naturels qui sont des multiples de 5.

5

Donner une définition inductive pour l’ensemble des mots binaires ne comportant pas trois zéros consécutifs

Donner et prouver un schéma inductif pour l’ensemble des mots binaires comportant autant de 0 que de 1. Votre schéma est-il libre ?