Fonction generatrice d'un langage

Modérateur : Michel Quercia

Répondre
Leo11
Messages : 145
Enregistré le : lun. déc. 09, 2013 6:48 pm

Fonction generatrice d'un langage

Message par Leo11 » ven. mars 10, 2017 7:18 pm

Bonjour, jai rencontré dans un exo la notion de fonction generatrice d'un langage sans plus d'explications. Quelqu'un pour m'éclairer svp ? Merci

Avatar du membre
U46406
Messages : 6226
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: Fonction génératrice d'un langage ?

Message par U46406 » ven. mars 10, 2017 7:46 pm

Ce langage, c'était au sens de langage naturel humain ? Ou langage informatique, comme en langage Lisp ??
https://fr.wikipedia.org/wiki/Lisp

Ton exercice, c'est un exercice de classe prépa (tiré d'un concours ?),
ou d'école d'ingénieur ?
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait) :mrgreen:

darklol
Messages : 744
Enregistré le : dim. avr. 19, 2015 12:08 am

Re: Fonction generatrice d'un langage

Message par darklol » ven. mars 10, 2017 11:56 pm

Salut, je ne connaissais pas non plus, mais j'ai fait une recherche rapide et j'ai trouvé ça:
https://www.irif.fr/~carton/Enseignement/Complexite/ENS/Redaction/2007-2008/sary.drapeau.pdf

(C'est un tout petit peu relevé mais tu devrais pouvoir comprendre l'essentiel, en particulier la définition de série génératrice d'un langage)

Sinon il y a aussi ce sujet d'info-maths ULC 2012: https://banques-ecoles.fr/cms/wp-content/data/filiere-mp/annales-de-la-banque-i/session-2012/mp2012_sujet_infomath_ulc.pdf

Bizarre que ça apparaisse tel quel sans explications supplémentaires par contre...
ENS Lyon

Leo11
Messages : 145
Enregistré le : lun. déc. 09, 2013 6:48 pm

Re: Fonction generatrice d'un langage

Message par Leo11 » sam. mars 11, 2017 1:18 am

C'etait au sens des langages qu'on pourrait appeler théoriques je pense ? Genre les langages définis sur un alphabet sigma, reconnus ou pas par des automates,etc.. Les langages vus en option quoi
Merci darklol, je vais voir ca. Javais fait une recherche rapide aussi depuis mon portable mais javais pas trouvé
Et cette question est posée dans l'exercice 11 du chapitre automates du Vuibert option info mp si ca vous intéresse. J'ai feuilleté le cours mais j'ai rien trouvé y référant, ni dans l'index ..

Leo11
Messages : 145
Enregistré le : lun. déc. 09, 2013 6:48 pm

Re: Fonction generatrice d'un langage

Message par Leo11 » sam. mars 11, 2017 1:33 am

Ok je mets la réponse ici au cas où ca intéresserait d'autres qui ne veulent pas aller lire les docs:
la série génératrice d'un langage L est la série formelle (en gros c'est un polynôme de degré infini, presque comme une série entière, sauf qu'on s'en fiche de savoir si c'est défini en tel ou tel point puisqu'on remplace les x complexes par des X indéterminées des polynômes) de terme général l_n ou l_n est le nombre de mots de longueur n appartenant à L.
En clair, ca sert à facilement avoir accès au nombre de mots de longueur donnée d'un langage si j'ai bien compris

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités