Cours de Mathematique a télécharger gratuitement en ligne Mathematique cours et leçon

---

Nous avons vu que les automates reconnaissent les langages qui peuvent être engendrés par les grammaires régulières. Le problème : peut-on décrire un dispositif plus général, associé de manière naturelle aux grammaires algébriques ? Rappelons un exemple simple, sur l’alphabet S = {a, b}. Il est très facile d’écrire une grammaire algébrique qui engendre le langage L = {an bn : n ³ 0 } ; il suffit pour cela de considérer la grammaire S ? aSb | ? . Néanmoins, le Lemme de l’Etoile (cf. [1] ) nous permet de prouver que L ne peut pas être engendré par une grammaire régulière. L’idée intuitive est qu’avec une grammaire régulière, les symboles sont écrits consécutivement (de gauche à droite), et qu’il faut donc compter les symboles a au fur et à mesure qu’on les écrit, pour pouvoir ensuite les faire suivre d’autant de symboles b . Un dispositif qui reconnaît L doit être capable de mémoriser. En fait, il suffira de coupler un automate à une mémoire rudimentaire (une pile, supposée de capacité illimitée). Voici un tel exemple. L’automate représenté ci-dessous est assorti d’une pile, vide au départ. En parcourant l’automate, on empile un jeton à chaque passage par la transition d’étiquette a , et on dépile un jeton – on doit pouvoir le dépiler – en passant par une transition d’étiquette b . On laisse la pile inchangée par la transition d’étiquette ? (vide) de s0 à l’état 1 . Pour qu’une chaîne testée wÎ{a, b}* soit acceptée, on convient que la pile doit être de nouveau vide lorsque w est entièrement lue, en arrivant à l’état final. Il est facile de se convaincre que le langage reconnu est L = {an bn : n ³ 0 }.

Télécharger gratuitement le cours

On suppose connus les r´esultats basiques de la th´eorie des ensembles ZFC qui correspondent aux 2 premiers chapitres du livre de J-L Krivine comme la trichotomie des cardinaux, `a savoir, pour les cardinaux de 2 ensembles A et B quelconques on a soit card(A) < card(B), soit card(A) = card(B), soit card(A) > card(B) o`u card(A) 6 card(B) veut dire qu’il existe une injection de A dans B. La relation 6 dans la collection des cardinaux (ce n’est pas un ensemble) est trivialement r´eflexive,transitive et elle est antisym´etrique grˆace au th´eor`eme de Cantor-Bernstein (voir la preuve dans la banque d’exercices du site) ; on dira que c’est une relation d’ordre dans la collection des cardinaux et cet ordre est total en vertu de la trichotomie. Un autre r´esultat basique (difficile) sera utilis´e fr´equemment `a savoir card(En) = card(E) si E est INFINI et n un entier non nul. Penser aux cas particuliers NxN qui est ´equipotent `a N ou RxR qui est ´equipotent `a R que l’on peut prouver directement ou `a la courbe de Peano. On rappelle que l’addition et la multiplication de 2 cardinaux sont ainsi d´efinies : card(A) + card(B) =le cardinal de la r´eunion de 2 ensembles disjoints ´equipotents respectivement `a A et B par exemple card({0}xA S {1}xB) et card(A)xcard(B) = card(AxB).

Télécharger gratuitement le cours

Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les mathématiques désignent aussi le domaine de recherche visant à développer ces connaissances, ainsi que la discipline qui les enseigne. Les mathématiques se distinguent des autres sciences par un rapport particulier au réel. Elles sont de nature purement intellectuelles, basées sur des axiomes déclarés vrais (c'est-à-dire que les axiomes ne sont pas soumis à l'expérience mais ils en sont souvent inspirés notamment dans le cas des mathématiques classiques) ou sur des postulats provisoirement admis.

Télécharger gratuitement le cours