bonjour,
juste une petite question au niveau des langages non rationnels pour les automates en Caml. Je connais bien évidemment le célébrissime a^n*b^n qui ne l'est pas et je sais le démontrer par le lemme de l'étoile et par les résiduels.
En fait, je voudrais savoir si dans un concours je dois redémontrer le lemme de l'étoile ou la propriété des résiduels : un langage est reconnaissable, donc rationnel, s'il a un nombre fini de langages résiduels, ou si je peux les utiliser directement juste en disant : par ... turlututu chapeau pointu (l'un ou l'autre en fait)..., on a que ce langage n'est pas rationnel
D'avance merci
langage non rationnel
Je ne suis pas trop au courant, mais les résiduels n'ont, dans ma classe, été vus qu'en suppléments au cours, durant un TD. Pour le lemme de l'étoile, il nous a été introduit comme un théorème au programme. Donc pour ta question, je répondrai: oui directement avec le lemme de l'étoile, et non pour les résiduels...
... maintenant il se peut que les résiduels soient au programme officiel, je répète que je n'en sais rien.
J'ai un question aussi qui va bien dans ce topic, donc j'en profite:
Pour définir un langages rationnel, notre prof nous a donné la définition inductive suivante:
(i)Tout langage fini est rationnel
(ii)Si L1 et L2 sont rationnels, L1UL2 et L1.L2 le sont
(iii)Si L est rationnel: L* l'est aussi
Or dans le rapport du sujet 2003 d'informatique de l'ENS, il y a une affirmation qui me pose problème (voir ici:
http://www.dptinfo.ens-cachan.fr/concou ... nfo-03.pdf)
A la page 3, tout en haut, le correcteur dit qu'il y a eu beaucoup de
malentendues sur les langages rationnels. Il dit notamment:
"Comme en 2001, cette question sur la rationalité est celle qui a donné lieu
au plus grand nombre de réponses aussi péremptoires que fantaisistes (...) un langage rationnel est stable par concaténation (vu plusieurs fois), . . ."
Ainsi, a-t-on ou non la stabilité par concaténation??? Est-ce que je
comprends mal ce qu'a voulu dire le correcteur, ou bien est-ce une erreur de
sa part?
... maintenant il se peut que les résiduels soient au programme officiel, je répète que je n'en sais rien.
J'ai un question aussi qui va bien dans ce topic, donc j'en profite:
Pour définir un langages rationnel, notre prof nous a donné la définition inductive suivante:
(i)Tout langage fini est rationnel
(ii)Si L1 et L2 sont rationnels, L1UL2 et L1.L2 le sont
(iii)Si L est rationnel: L* l'est aussi
Or dans le rapport du sujet 2003 d'informatique de l'ENS, il y a une affirmation qui me pose problème (voir ici:
http://www.dptinfo.ens-cachan.fr/concou ... nfo-03.pdf)
A la page 3, tout en haut, le correcteur dit qu'il y a eu beaucoup de
malentendues sur les langages rationnels. Il dit notamment:
"Comme en 2001, cette question sur la rationalité est celle qui a donné lieu
au plus grand nombre de réponses aussi péremptoires que fantaisistes (...) un langage rationnel est stable par concaténation (vu plusieurs fois), . . ."
Ainsi, a-t-on ou non la stabilité par concaténation??? Est-ce que je
comprends mal ce qu'a voulu dire le correcteur, ou bien est-ce une erreur de
sa part?
Ok, j'ai compris... mon dieu, j'ai failli devenir fou, je comprenais plus rien, je croyais que tu répétais les mots du correcteur 
En fait (dis moi si je ne me trompe pas cette fois), l'affirmation que j'avais compris était: "L.L n'est pas forcément rationel", alors qu'il fallait juste comprendre "L.L est inclus dans L".
(c'est bien ça?)
En fait (dis moi si je ne me trompe pas cette fois), l'affirmation que j'avais compris était: "L.L n'est pas forcément rationel", alors qu'il fallait juste comprendre "L.L est inclus dans L".
(c'est bien ça?)
Tout dépend du concours, mais à mon avis, tu ne devrais pas avoir besoin des résiduels en dehors de Polytechnique ou l'ENS, et dans ce cas il est tout à fait acceptable d'utiliser directement le fait qu'un langage est rationnel s'il a un nombre fini de résiduels. (affirmation que je justifierais rapidement si j'étais amené à l'employer à Centrale par contre...)
merci pour toutes ces réponses et désolé de ne pas avoir répondu plus tôt
Donc pour faire un petit compte-rendu de mes concours : je n'ai jamais eu à parler d'un langage non rationnel, d'ailleurs je n'ai parlé de langage qu'au CCP et c'était très rapide, plus un exercice qu'un problème avec la relation + pour les automates.
Sinon, comme ca : comment avez-trouvé le sujet d'info de centrale de cette annéee justement ? Perso j'ai pas très beaucoup compris le problème de programmation.
Donc pour faire un petit compte-rendu de mes concours : je n'ai jamais eu à parler d'un langage non rationnel, d'ailleurs je n'ai parlé de langage qu'au CCP et c'était très rapide, plus un exercice qu'un problème avec la relation + pour les automates.
Sinon, comme ca : comment avez-trouvé le sujet d'info de centrale de cette annéee justement ? Perso j'ai pas très beaucoup compris le problème de programmation.
Mon avis: Le rédacteur du sujet est un drogué...Genre s'il s'est dit "je vais écrire ça, et des gens vont comprendre", c'est qu'il n'était pas dans un état convenable lolNico a écrit :merci pour toutes ces réponses et désolé de ne pas avoir répondu plus tôt
Donc pour faire un petit compte-rendu de mes concours : je n'ai jamais eu à parler d'un langage non rationnel, d'ailleurs je n'ai parlé de langage qu'au CCP et c'était très rapide, plus un exercice qu'un problème avec la relation + pour les automates.
Sinon, comme ca : comment avez-trouvé le sujet d'info de centrale de cette annéee justement ? Perso j'ai pas très beaucoup compris le problème de programmation.
..M'enfin ça confirme ce que je pense de ce concours...