Centrale Informatique MP 2009

- version du 12 mars 2009 10h19

INFORMATIQUE

Cette notation exprime bien le lien entre les points Pi et Pj lorsque j = c[i].

Filière

MP

P5

P6

P4

c1
c2

1
2
2

P7

P3

2
1
1

P2

3
6
7

P8

1

P

4
5
5

5
4
4

P5

P6

6
3
8
P4

7
8
3

P7

P3

8
7
6

P8

P2

1

P

I.B - Soit i, j, k, l quatre entiers distincts tels que : 1 6 i < j 6 2n et 1 6 k < l 6 2n. I.B.1) Donner une condition nécessaire et suffisante, portant uniquement sur ces entiers, pour que les segments [Pi Pj ] et [Pk Pl ] se croisent. I.A.1) Dans le cas n = 3, donner le nombre de stratégies possibles, admissibles ou non. I.A.2) Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les représenter sur une figure. I.A.3) Déterminer le nombre de stratégies de taille n entier positif (qu'elles soient ou non admissibles). La figure de gauche correspond à c1 qui est donc admissible, et celle de droite à c2 qui, elle, ne l'est pas. Par exemple, pour les stratégies de taille 4, c1 et c2 ci-contre : En Pascal, on représente le vecteur par un tableau avec un type tr défini par : st     {de taille suffisante pour tout le problème} tr  rr   tr En Caml, on représente le vecteur avec le type « tr » de Caml. On peut utiliser la fonction t. Les éléments des vecteurs en Caml sont numérotés de 0 à N - 1. On prendra des vecteurs de taille 2n + 1, dont le premier élément ne sera pas utilisé, pour que les points soient bien aux indices 1 à 2n dans le vecteur Caml. On considère des stratégies où les points d'une paire sont reliés par des segments de droites situés dans un même plan. Une stratégie est dite « admissible » si les segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend pas de la position des points sur la circonférence mais seulement de la stratégie. Page 1/3 Dans toute la suite on fixe un entier n > 0 et on appelle stratégie de taille n 
un
vecteur c[1], c[2], . . . , c[2n] , tel que pour tout entier i vérifiant 1 6 i 
6 2n on ait :
 
1 6 c[i] 6 2n,
c c[i] = i,
c[i] 6= i.

i) chaque point est une extrémité d'une et une seule corde,
ii) les différentes cordes ne doivent pas se couper.

I.A - Les 2n protagonistes sont représentés par des points distincts P1 , P2 , 
..., P2n
répartis dans l'ordre des indices croissants sur la circonférence d'un cercle 
parcouru
dans le sens trigonométrique ; n sont des chasseurs, n des fantômes, mais, dans
cette section I.A, on cherche les liens possibles entre les Pi sans s'occuper 
de qui
est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par 
une
corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il 
faut
donc respecter les deux conditions :

Un groupe de n chasseurs de fantômes combat un groupe de n fantômes. Chaque
chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de
rayon. Un rayon se propage en ligne droite et termine sa course en touchant le 
fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire 
d'éliminer
tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre
initial de n fantômes ; il est très dangereux que deux rayons se croisent, cela 
ne doit
donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse,
dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont 
possibles que sur un rebord confondu avec la circonférence, mais les tirs se 
font entre
deux points de la circonférence, selon des cordes du cercle.

Les candidats devront indiquer clairement en tête de copie le langage
de programmation choisi (Pascal ou Caml). Les fonctions et procédures demandées 
seront rédigées dans ce langage.

Partie I - La chasse aux fantômes

Note : les parties I, II.A, II.B et II.C sont indépendantes.

trs trsés

Épreuve :

Concours Centrale - Supélec 2009

- version du 12 mars 2009 10h19

INFORMATIQUE

Cette notation exprime bien le lien entre les points Pi et Pj lorsque j = c[i].

Filière

MP

P5

P6

P4

c1
c2

1
2
2

P7

P3

2
1
1

P2

3
6
7

P8

1

P

4
5
5

5
4
4

P5

P6

6
3
8
P4

7
8
3

P7

P3

8
7
6

P8

P2

1

P

I.B - Soit i, j, k, l quatre entiers distincts tels que : 1 6 i < j 6 2n et 1 6 k < l 6 2n. I.B.1) Donner une condition nécessaire et suffisante, portant uniquement sur ces entiers, pour que les segments [Pi Pj ] et [Pk Pl ] se croisent. I.A.1) Dans le cas n = 3, donner le nombre de stratégies possibles, admissibles ou non. I.A.2) Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les représenter sur une figure. I.A.3) Déterminer le nombre de stratégies de taille n entier positif (qu'elles soient ou non admissibles). La figure de gauche correspond à c1 qui est donc admissible, et celle de droite à c2 qui, elle, ne l'est pas. Par exemple, pour les stratégies de taille 4, c1 et c2 ci-contre : En Pascal, on représente le vecteur par un tableau avec un type tr défini par : st     {de taille suffisante pour tout le problème} tr  rr   tr En Caml, on représente le vecteur avec le type « tr » de Caml. On peut utiliser la fonction t. Les éléments des vecteurs en Caml sont numérotés de 0 à N - 1. On prendra des vecteurs de taille 2n + 1, dont le premier élément ne sera pas utilisé, pour que les points soient bien aux indices 1 à 2n dans le vecteur Caml. On considère des stratégies où les points d'une paire sont reliés par des segments de droites situés dans un même plan. Une stratégie est dite « admissible » si les segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend pas de la position des points sur la circonférence mais seulement de la stratégie. Page 1/3 Dans toute la suite on fixe un entier n > 0 et on appelle stratégie de taille n 
un
vecteur c[1], c[2], . . . , c[2n] , tel que pour tout entier i vérifiant 1 6 i 
6 2n on ait :
 
1 6 c[i] 6 2n,
c c[i] = i,
c[i] 6= i.

i) chaque point est une extrémité d'une et une seule corde,
ii) les différentes cordes ne doivent pas se couper.

I.A - Les 2n protagonistes sont représentés par des points distincts P1 , P2 , 
..., P2n
répartis dans l'ordre des indices croissants sur la circonférence d'un cercle 
parcouru
dans le sens trigonométrique ; n sont des chasseurs, n des fantômes, mais, dans
cette section I.A, on cherche les liens possibles entre les Pi sans s'occuper 
de qui
est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par 
une
corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il 
faut
donc respecter les deux conditions :

Un groupe de n chasseurs de fantômes combat un groupe de n fantômes. Chaque
chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de
rayon. Un rayon se propage en ligne droite et termine sa course en touchant le 
fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire 
d'éliminer
tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre
initial de n fantômes ; il est très dangereux que deux rayons se croisent, cela 
ne doit
donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse,
dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont 
possibles que sur un rebord confondu avec la circonférence, mais les tirs se 
font entre
deux points de la circonférence, selon des cordes du cercle.

Les candidats devront indiquer clairement en tête de copie le langage
de programmation choisi (Pascal ou Caml). Les fonctions et procédures demandées 
seront rédigées dans ce langage.

Partie I - La chasse aux fantômes

Note : les parties I, II.A, II.B et II.C sont indépendantes.

trs trsés

Épreuve :

Concours Centrale - Supélec 2009

- version du 12 mars 2009 10h19

INFORMATIQUE

Cette notation exprime bien le lien entre les points Pi et Pj lorsque j = c[i].

Filière

MP

P5

P6

P4

c1
c2

1
2
2

P7

P3

2
1
1

P2

3
6
7

P8

1

P

4
5
5

5
4
4

P5

P6

6
3
8
P4

7
8
3

P7

P3

8
7
6

P8

P2

1

P

I.B - Soit i, j, k, l quatre entiers distincts tels que : 1 6 i < j 6 2n et 1 6 k < l 6 2n. I.B.1) Donner une condition nécessaire et suffisante, portant uniquement sur ces entiers, pour que les segments [Pi Pj ] et [Pk Pl ] se croisent. I.A.1) Dans le cas n = 3, donner le nombre de stratégies possibles, admissibles ou non. I.A.2) Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les représenter sur une figure. I.A.3) Déterminer le nombre de stratégies de taille n entier positif (qu'elles soient ou non admissibles). La figure de gauche correspond à c1 qui est donc admissible, et celle de droite à c2 qui, elle, ne l'est pas. Par exemple, pour les stratégies de taille 4, c1 et c2 ci-contre : En Pascal, on représente le vecteur par un tableau avec un type tr défini par : st     {de taille suffisante pour tout le problème} tr  rr   tr En Caml, on représente le vecteur avec le type « tr » de Caml. On peut utiliser la fonction t. Les éléments des vecteurs en Caml sont numérotés de 0 à N - 1. On prendra des vecteurs de taille 2n + 1, dont le premier élément ne sera pas utilisé, pour que les points soient bien aux indices 1 à 2n dans le vecteur Caml. On considère des stratégies où les points d'une paire sont reliés par des segments de droites situés dans un même plan. Une stratégie est dite « admissible » si les segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend pas de la position des points sur la circonférence mais seulement de la stratégie. Page 1/3 Dans toute la suite on fixe un entier n > 0 et on appelle stratégie de taille n 
un
vecteur c[1], c[2], . . . , c[2n] , tel que pour tout entier i vérifiant 1 6 i 
6 2n on ait :
 
1 6 c[i] 6 2n,
c c[i] = i,
c[i] 6= i.

i) chaque point est une extrémité d'une et une seule corde,
ii) les différentes cordes ne doivent pas se couper.

I.A - Les 2n protagonistes sont représentés par des points distincts P1 , P2 , 
..., P2n
répartis dans l'ordre des indices croissants sur la circonférence d'un cercle 
parcouru
dans le sens trigonométrique ; n sont des chasseurs, n des fantômes, mais, dans
cette section I.A, on cherche les liens possibles entre les Pi sans s'occuper 
de qui
est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par 
une
corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il 
faut
donc respecter les deux conditions :

Un groupe de n chasseurs de fantômes combat un groupe de n fantômes. Chaque
chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de
rayon. Un rayon se propage en ligne droite et termine sa course en touchant le 
fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire 
d'éliminer
tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre
initial de n fantômes ; il est très dangereux que deux rayons se croisent, cela 
ne doit
donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse,
dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont 
possibles que sur un rebord confondu avec la circonférence, mais les tirs se 
font entre
deux points de la circonférence, selon des cordes du cercle.

Les candidats devront indiquer clairement en tête de copie le langage
de programmation choisi (Pascal ou Caml). Les fonctions et procédures demandées 
seront rédigées dans ce langage.

Partie I - La chasse aux fantômes

Note : les parties I, II.A, II.B et II.C sont indépendantes.

trs trsés

Épreuve :

Concours Centrale - Supélec 2009

2n

Filière MP

Un automate (fini) non déterministe est un quintuplet A = (Q, A, I, , F) avec 
cette
fois I  Q l'ensemble des états initiaux et  : Q × A  P(Q) la fonction de
transition : si p  Q et   A, (p, ) désigne l'ensemble (éventuellement vide)
des q  Q tels qu'il existe une transition étiquetée par  de p vers q. Si on 
choisit
de représenter les transitions par un ensemble inclus dans Q × A × Q, la 
condition
(D) n'a plus à être vérifiée.
Pour présenter un automate, les candidats pourront, bien entendu, les 
représenter
par un schéma. Ils veilleront alors à bien identifier l'état initial (ou les 
états initiaux)
et les états terminaux par une notation adaptée.

Lorsque  est défini sur l'ensemble Q × A tout entier, on parle d'automate fini 
complet. Que l'automate soit complet, ou non, on peut choisir de représenter 
les transitions non par une fonction de transition , mais par un ensemble de 
transitions
T  Q × A × Q (le graphe de ), avec la condition de déterminisme :
(D)
si (q, , q1 ), (q, , q2 )  T, alors q1 = q2 .

Un automate (sous entendu fini) déterministe est un quintuplet A = (Q, A, i, , 
F)
avec :
· Q l'ensemble fini non vide des états ;
· A l'alphabet c'est-à-dire l'ensemble fini non vide des lettres ;
· i  Q l'état initial ;
·  : Q × A  Q la fonction de transition (éventuellement partielle) ;
· F  Q l'ensemble des états terminaux.

Définitions et notations

On rappelle que les sections II.A, II.B, II.C sont indépendantes et peuvent 
être traitées dans un ordre quelconque.

Partie II - Automates finis

de fantômes que de chasseurs. Écrire une fonction s, qui prend en paramètre
le vecteur p (et en Pascal, le nombre n de chasseurs) et qui renvoie la liste 
des indices
(i, j) des couples (Pi , Pj ) (où Pi est un chasseur et Pj un fantôme), 
composant une
stratégie admissible du problème.

i=1

 p[i] = 0 puisqu'il y a autant

Un vecteur p contient la nature des points Pi : p[i] = 1 pour un chasseur,

p[i] = -1 pour un fantôme (1 6 i 6 2n). On a donc

I.D.4)

Page 2/3

I.D - La méthode précédente teste si une stratégie est admissible. On souhaite 
maintenant, le statut (chasseur ou fantôme) des points étant donné, déterminer 
directement une stratégie admissible, de façon également efficace.
I.D.1) Montrer que si Pi est un chasseur (1 6 i 6 2n), alors il existe j 6= i, 
avec
1 6 j 6 2n tel que Pj est un fantôme et tel que le nombre de chasseurs soit 
égal au
nombre de fantômes de chaque côté de l'axe Pi Pj .
I.D.2) En déduire un algorithme simple pour construire une stratégie admissible.
I.D.3) On se propose d'évaluer la complexité de cette méthode.
a) Déterminer la complexité dans le pire des cas.
b) Évaluer, sans démonstration, la complexité moyenne.

I.C - On souhaite tester la stratégie de façon plus efficace. Pour cela on 
utilise une
fonction «  » qui prend deux entiers i et j comme paramètres (i et j étant 
compris entre 1 et 2n) et dont le résultat est tr si et seulement si les deux 
propositions
suivantes sont vraies :
· (i 6 k 6 j)  (i 6 c[k] 6 j)
· les segments ayant leurs extrémités dans l'arc (fermé) [Pi Pj ] ne se 
croisent pas.
I.C.1) Donner la valeur de   dans les trois cas particuliers a, b et c
suivants :
c) j > i et c[i] > j.
a) j < i ; b) j > i et c[i] < i ; I.C.2) Pour i < c[i] < j, montrer que   se déduit de et de    . I.C.3) Écrire une fonction tsttrt qui prend en paramètre un vecteur (et en Pascal le nombre n de chasseurs) et renvoie un booléen dont la valeur est tr si la stratégie est admissible. Cette fonction devra être de complexité O(n). I.C.4) Démontrer avec soin que la fonction tsttrt est bien de complexité O(n). I.B.2) Écrire une fonction « rs » prenant les quatre entiers pour paramètres et renvoyant un booléen dont le résultat est tr si et seulement si les segments [Pi Pj ] et [Pk Pl ] se croisent. On suppose que les paramètres donnés à la fonction satisfont les conditions données en introduction du I.B. I.B.3) En utilisant la fonction rs, écrire une fonction « stss » qui prend en paramètre le vecteur (et en Pascal, le nombre n de chasseurs) et renvoie un booléen dont le résultat est tr si la stratégie est admissible. I.B.4) Donner, en la justifiant, la complexité de cette méthode, en terme de temps de calcul (on se contentera d'une évaluation du type O(n ), en précisant la valeur de ). INFORMATIQUE 2n Filière MP Un automate (fini) non déterministe est un quintuplet A = (Q, A, I, , F) avec cette fois I  Q l'ensemble des états initiaux et  : Q × A  P(Q) la fonction de transition : si p  Q et   A, (p, ) désigne l'ensemble (éventuellement vide) des q  Q tels qu'il existe une transition étiquetée par  de p vers q. Si on choisit de représenter les transitions par un ensemble inclus dans Q × A × Q, la condition (D) n'a plus à être vérifiée. Pour présenter un automate, les candidats pourront, bien entendu, les représenter par un schéma. Ils veilleront alors à bien identifier l'état initial (ou les états initiaux) et les états terminaux par une notation adaptée. Lorsque  est défini sur l'ensemble Q × A tout entier, on parle d'automate fini complet. Que l'automate soit complet, ou non, on peut choisir de représenter les transitions non par une fonction de transition , mais par un ensemble de transitions T  Q × A × Q (le graphe de ), avec la condition de déterminisme : (D) si (q, , q1 ), (q, , q2 )  T, alors q1 = q2 . Un automate (sous entendu fini) déterministe est un quintuplet A = (Q, A, i, , F) avec : · Q l'ensemble fini non vide des états ; · A l'alphabet c'est-à-dire l'ensemble fini non vide des lettres ; · i  Q l'état initial ; ·  : Q × A  Q la fonction de transition (éventuellement partielle) ; · F  Q l'ensemble des états terminaux. Définitions et notations On rappelle que les sections II.A, II.B, II.C sont indépendantes et peuvent être traitées dans un ordre quelconque. Partie II - Automates finis de fantômes que de chasseurs. Écrire une fonction s, qui prend en paramètre le vecteur p (et en Pascal, le nombre n de chasseurs) et qui renvoie la liste des indices (i, j) des couples (Pi , Pj ) (où Pi est un chasseur et Pj un fantôme), composant une stratégie admissible du problème. i=1 p[i] = 0 puisqu'il y a autant Un vecteur p contient la nature des points Pi : p[i] = 1 pour un chasseur, p[i] = -1 pour un fantôme (1 6 i 6 2n). On a donc I.D.4) Page 2/3 I.D - La méthode précédente teste si une stratégie est admissible. On souhaite maintenant, le statut (chasseur ou fantôme) des points étant donné, déterminer directement une stratégie admissible, de façon également efficace. I.D.1) Montrer que si Pi est un chasseur (1 6 i 6 2n), alors il existe j 6= i, avec 1 6 j 6 2n tel que Pj est un fantôme et tel que le nombre de chasseurs soit égal au nombre de fantômes de chaque côté de l'axe Pi Pj . I.D.2) En déduire un algorithme simple pour construire une stratégie admissible. I.D.3) On se propose d'évaluer la complexité de cette méthode. a) Déterminer la complexité dans le pire des cas. b) Évaluer, sans démonstration, la complexité moyenne. I.C - On souhaite tester la stratégie de façon plus efficace. Pour cela on utilise une fonction «  » qui prend deux entiers i et j comme paramètres (i et j étant compris entre 1 et 2n) et dont le résultat est tr si et seulement si les deux propositions suivantes sont vraies : · (i 6 k 6 j)  (i 6 c[k] 6 j) · les segments ayant leurs extrémités dans l'arc (fermé) [Pi Pj ] ne se croisent pas. I.C.1) Donner la valeur de   dans les trois cas particuliers a, b et c suivants : c) j > i et c[i] > j.
a) j < i ; b) j > i et c[i] < i ; I.C.2) Pour i < c[i] < j, montrer que   se déduit de et de    . I.C.3) Écrire une fonction tsttrt qui prend en paramètre un vecteur (et en Pascal le nombre n de chasseurs) et renvoie un booléen dont la valeur est tr si la stratégie est admissible. Cette fonction devra être de complexité O(n). I.C.4) Démontrer avec soin que la fonction tsttrt est bien de complexité O(n). I.B.2) Écrire une fonction « rs » prenant les quatre entiers pour paramètres et renvoyant un booléen dont le résultat est tr si et seulement si les segments [Pi Pj ] et [Pk Pl ] se croisent. On suppose que les paramètres donnés à la fonction satisfont les conditions données en introduction du I.B. I.B.3) En utilisant la fonction rs, écrire une fonction « stss » qui prend en paramètre le vecteur (et en Pascal, le nombre n de chasseurs) et renvoie un booléen dont le résultat est tr si la stratégie est admissible. I.B.4) Donner, en la justifiant, la complexité de cette méthode, en terme de temps de calcul (on se contentera d'une évaluation du type O(n ), en précisant la valeur de ). INFORMATIQUE bn,m m =1 bi, 2-1 pour tout 1 6 i 6 n. On appelle relation dans N n tout sous-ensemble de N n . On dit qu'une relation R  N n est rationnelle, lorsqu'il existe un automate fini A qui reconnaît exactement l'ensemble des mots de (Bn ) représentant les n-uplets de R. a) Donner une représentation des n-uplets suivants : (4); (2, 3, 0); (2, 3, 5). xi = représente le n-uplet d'entiers naturels (x1 , · · · , xn ) tel que bn,1 Pour les deux questions b) et c) suivantes, on demande de donner, pour chacune des relations Eg, In f et Add, un automate fini la reconnaissant effectivement. Filière MP · · · FIN · · · II.C.4) Déterminiser l'automate proposé dans la question C.2), lorsque N = 1. II.C.5) Démontrer qu'il n'existe pas d'automate déterministe complet reconnaissant D N et possédant strictement moins de 2 N+1 états. II.C.6) Démontrer qu'il n'existe pas d'automate fini (non-déterministe) reconnaissant D N et possédant strictement moins de N + 2 états. Même question pour le langage GN . On pourra raisonner par l'absurde et prouver que les états atteints en lisant ak depuis l'état initial sont distincts, pour certaines valeurs k. II.C - Automate minimal Soit A = {a, b}. Pour chaque entier N  N, on définit les langages GN et D N de la manière suivante : · GN = {uav | u  A N , v  A }. · D N = {uav | u  A , v  A N }. II.C.1) Donner un automate déterministe complet, à N + 3 états reconnaissant GN . II.C.2) Donner un automate non-déterministe, à N + 2 états reconnaissant D N . II.C.3) Démontrer qu'il n'existe pas d'automate déterministe complet reconnaissant GN et possédant strictement moins de N + 3 états. b) Montrer que les relations : et In f = (x, y)  N2 | x < y Eg = (x, y)  N2 | x = y sont rationnelles. c) Montrer que la relation : Add = (x, y, z)  N3 | x + y = z est rationnelle. d) On suppose la relation R  N n rationnelle et on définit les relations Q  N n-1 et S  N n-1 par : (x1 , . . . , xn-1 )  Q si, et seulement si, il existe x  N tel que (x1 , . . . , xn-1 , x)  R. (x1 , . . . , xn-1 )  S si, et seulement si, pour tout x  N, (x1 , . . . , xn-1 , x)  R. Montrer que les relations Q et S sont rationnelles. Page 3/3 II.B - Logique de Presburger Soit n un entier strictement positif et B = {0, 1}. On prend comme alphabet l'ensemble Bn . Un mot b1,1 b1,m u =  ...  · · ·  ...   (Bn ) L = {u | w  A , u 6= w2 }. a) On suppose que A est réduit à une lettre. Montrer alors que L est reconnaissable par automate fini et donner un automate reconnaissant effectivement L, ainsi qu'une expression rationnelle décrivant L. b) On suppose maintenant que A n'est pas réduit à une lettre. Montrer que L n'est pas reconnaissable. c) Soit p un entier strictement plus grand que 2. Reprendre les deux questions précédentes en remplaçant L par L p défini par : L p = {u | w  A , u 6= w p } II.A - Mots répétés II.A.1) Soit A un alphabet. On s'intéresse au langage L  A constitué des mots u qui ne sont de la forme w2 (c'est-à-dire ww) pour aucun w  A : On note A l'ensemble des mots écrits dans l'alphabet A (y compris le mot vide). Un langage sur l'alphabet A est un sous-ensemble de A . On note en particulier L(A ) le langage de A , c'est-à-dire l'ensemble des mots acceptés par A (permettant de passer d'un état initial à un état terminal). Étant donné un mot u  A , on note |u| la longueur de u, c'est-à-dire le nombre de ses lettres. INFORMATIQUE bn,m m =1 bi, 2-1 pour tout 1 6 i 6 n. On appelle relation dans N n tout sous-ensemble de N n . On dit qu'une relation R  N n est rationnelle, lorsqu'il existe un automate fini A qui reconnaît exactement l'ensemble des mots de (Bn ) représentant les n-uplets de R. a) Donner une représentation des n-uplets suivants : (4); (2, 3, 0); (2, 3, 5). xi = représente le n-uplet d'entiers naturels (x1 , · · · , xn ) tel que bn,1 Pour les deux questions b) et c) suivantes, on demande de donner, pour chacune des relations Eg, In f et Add, un automate fini la reconnaissant effectivement. Filière MP · · · FIN · · · II.C.4) Déterminiser l'automate proposé dans la question C.2), lorsque N = 1. II.C.5) Démontrer qu'il n'existe pas d'automate déterministe complet reconnaissant D N et possédant strictement moins de 2 N+1 états. II.C.6) Démontrer qu'il n'existe pas d'automate fini (non-déterministe) reconnaissant D N et possédant strictement moins de N + 2 états. Même question pour le langage GN . On pourra raisonner par l'absurde et prouver que les états atteints en lisant ak depuis l'état initial sont distincts, pour certaines valeurs k. II.C - Automate minimal Soit A = {a, b}. Pour chaque entier N  N, on définit les langages GN et D N de la manière suivante : · GN = {uav | u  A N , v  A }. · D N = {uav | u  A , v  A N }. II.C.1) Donner un automate déterministe complet, à N + 3 états reconnaissant GN . II.C.2) Donner un automate non-déterministe, à N + 2 états reconnaissant D N . II.C.3) Démontrer qu'il n'existe pas d'automate déterministe complet reconnaissant GN et possédant strictement moins de N + 3 états. b) Montrer que les relations : et In f = (x, y)  N2 | x < y Eg = (x, y)  N2 | x = y sont rationnelles. c) Montrer que la relation : Add = (x, y, z)  N3 | x + y = z est rationnelle. d) On suppose la relation R  N n rationnelle et on définit les relations Q  N n-1 et S  N n-1 par : (x1 , . . . , xn-1 )  Q si, et seulement si, il existe x  N tel que (x1 , . . . , xn-1 , x)  R. (x1 , . . . , xn-1 )  S si, et seulement si, pour tout x  N, (x1 , . . . , xn-1 , x)  R. Montrer que les relations Q et S sont rationnelles. Page 3/3 II.B - Logique de Presburger Soit n un entier strictement positif et B = {0, 1}. On prend comme alphabet l'ensemble Bn . Un mot b1,1 b1,m u =  ...  · · ·  ...   (Bn ) L = {u | w  A , u 6= w2 }. a) On suppose que A est réduit à une lettre. Montrer alors que L est reconnaissable par automate fini et donner un automate reconnaissant effectivement L, ainsi qu'une expression rationnelle décrivant L. b) On suppose maintenant que A n'est pas réduit à une lettre. Montrer que L n'est pas reconnaissable. c) Soit p un entier strictement plus grand que 2. Reprendre les deux questions précédentes en remplaçant L par L p défini par : L p = {u | w  A , u 6= w p } II.A - Mots répétés II.A.1) Soit A un alphabet. On s'intéresse au langage L  A constitué des mots u qui ne sont de la forme w2 (c'est-à-dire ww) pour aucun w  A : On note A l'ensemble des mots écrits dans l'alphabet A (y compris le mot vide). Un langage sur l'alphabet A est un sous-ensemble de A . On note en particulier L(A ) le langage de A , c'est-à-dire l'ensemble des mots acceptés par A (permettant de passer d'un état initial à un état terminal). Étant donné un mot u  A , on note |u| la longueur de u, c'est-à-dire le nombre de ses lettres. INFORMATIQUE