Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université de Batna SUPPORT DE COURS MODULE : THEORIE DES LANGAGES Département

Université de Batna SUPPORT DE COURS MODULE : THEORIE DES LANGAGES Département : INFORMATIQUE Niveau : 2ème année LICENCE Version janvier 2016 Module : La théorie des langages Niveau : 2ème année licence Préparé par Mohamed TOUMI Page : 2 Janvier 2016 ce cours se trouve sur http://fac-sciences.univ-batna.dz/cs/enseignants/mohamed_toumi_site/ Chapitre N° 1 : Rappel mathématique Introduction : La théorie des langages définit les langages de programmation par contre la compilation transforme les programmes écrits dans ces langages en langage machine. La structure de base de la théorie des langages est le monoïde, mais avant de définir cette nation on a besoin d’avoir un rappel mathématique. 1. Ensemble et relation : a) l’ensemble : un ensemble est une collection d’objets appelés éléments. Exemple : E = {1,2 ,3} est un ensemble de 3 éléments. Ce nombre là est appelé la cardinal de l’ensemble E Remarques :  L’ensemble vide noté par { } ou par, c’est un ensemble dont le cardinal = 0  Soit E un ensemble. L’ensemble des parties de E noté P(E) contient tous les sous ensembles de E Exemple : P({1,2,3})={,{1},{2},{3} ,{1,2} ,{1,3} ,{2,3} , {1,2,3} } Opérations sur les ensembles : soient E et F deux ensembles  L’inclusion : EF x (xExF)  L’union (U) (+) : EF= {x / xE ou x F  }  L’intersection : E F  = {x / xE et x F  }  Le complémentaire de F dans E (avec F E  ) = {x / xE et x F}  Le produit cartésien : EXF=  F y et E x / ) y , x (   b) la relation : Soient E et F deux ensembles  Une relation R de E dans F est un sous ensemble des couples (x,y) du E x F tel que x R y.  Une relation R sur un ensemble E est un sous ensemble des couples (x,y) du produit cartésien E x E tel que x R y. ExF =   ) 6 , 0 ( ), 3 , 0 ( ), 2 , 0 ( ), 6 , 2 ( ), 3 , 2 ( ), 2 , 2 ( ), 6 , 1 ( ), 3 , 1 ( ), 2 , 1 ( Soit R est définie comme suit : x est strictement inférieur à y et x ≠ 0. Le sous ensemble du produit cartésien E x F qui vérifie cette relation est   ) 6 , 2 )( 3 , 2 ( ), 6 , 1 ( ), 3 , 1 ( ), 2 , 1 ( L’ensemble des antécédents de R est appelé le Domaine de R. On écrit : DR=  R ) y , x /( x (  Module : La théorie des langages Niveau : 2ème année licence Préparé par Mohamed TOUMI Page : 3 Janvier 2016 ce cours se trouve sur http://fac-sciences.univ-batna.dz/cs/enseignants/mohamed_toumi_site/ L’ensemble des images de R est appelé le Codomaine de R. On écrit : CR=  R y x y  ) , /( ( c) la fonction : Soient E et F deux ensembles  Une fonction f de E dans F est une relation particulière telle que chaque antécédent de cette relation a exactement une seule image. On peut dire que chaque élément de E a au plus une image avec la fonction. Et avec la relation, chaque élément peut avoir 0,1 ou plusieurs images. d) l’application : une application de E dans F est une fonction f telle que le domaine de f = E Exemple : f : x x 1 est une fonction de IR dans IR mais n’est pas une application puisque l’élément « 0 » n’a pas une image. 2. lois de composition internes Définition : une loi de composition interne sur un ensemble E est une application qui associe à chaque couple (x,y)ExE un élément appartient aussi à E . Si on note cette loi par * On écrit : * : ExE E * est commutative si : E y x  , : x*y=y*x * est association si : E z y x   , , :   z y x z y x z y x * * ) * ( * * *   * a un élément neutre «e » si : E x  x x e e x   * * 3. le monoïde : Un monoïde E est un ensemble muni d’une loi de composition interne * associative et possédant un élément neutre « e » On écrit : < e E,*, > Exemple : < 0 , , IN > 0 : l’élément neutre pour + < 1 , , IN > 1 : l’élément neutre pour x 4. le morphisme : Soient E et F deux ensembles munis respectivement des lois de composition internes * et .  On dit que la fonction f est un morphisme de E dans F si et seulement si ) ( ). ( ) * ( y f x f y x f  Soient < e E,*, > et < ` ,.,e F > deux Monoïdes ou « e », « e` » sont les éléments neutres respectivement pour * et .  On dit que f est un morphisme de monoïde de E dans F si et seulement si :  f est un morphisme  f (e) = e` Module : La théorie des langages Niveau : 2ème année licence Préparé par Mohamed TOUMI Page : 4 Janvier 2016 ce cours se trouve sur http://fac-sciences.univ-batna.dz/cs/enseignants/mohamed_toumi_site/ Chapitre N° 2 : Les langages 1. Notion de l’alphabet : Un alphabet noté X est un ensemble fini non vide des éléments appelés les symboles ou lettres. Exemples : L’alphabet binaire : X = {0,1}. L’alphabet du langage PASCAL : X = {begin, if, then, else,….end}. L’alphabet de la langue française : X= {a, b,…, A, B, …, é, è,.. ï}. X= {bonjour, ali, $ , 1, w} c’est un alphabet de 5 lettres 2. Notion de mot (chaîne) Un mot sur un alphabet X est une suite d’éléments de l’alphabet X. Cette suite est finie et ordonnée. Exemples : L’ensemble des mots construits sur X= {0,1} est {0,1,01,10,111,00000,……………}. L’ensemble des mots construits sur L’alphabet PASCAL est {tous les programmes (corrects, incorrects) écrits en PASCAL}. bonjourali : c’est un mot de l’alphabet X= {bonjour, ali, $, 1, w} Remarques :  L’ensemble des mots construits sur un alphabet X est un ensemble infini noté X*  Le mot vide, noté par, c’est un mot qui ne contient aucun élément. * : X X    Exemple : soit X= {a,b} X*= {, a, b, aa, ab, bb, ba, aaa, aab, aba, baa,….}. X* = {} + {a, b} + {aa, ab, bb, ba} + {aaa,…} +…………. Si on note: Xi l’ensemble des mots de longueur i construits sur l’alphabet X Donc: X*= X0+                X 2 1 X + … … … … … … + X + X =  0 i i X 2.1. Opération sur les mots : a) La concaténation : soient deux mots w, w’ X*, la concaténation de w et w’ est définie comme la juxtaposition de w et w’. Elle est notée par w.w’ on bien ww’ Exemple X= {0,1} w=10, w’=00 w.w’=1000 ≠ w’w=0010 Remarque : la concaténation, c’est une loi de composition interne sur X* qui n’est pas commutative mais elle est associative et elle possède un élément neutre qui est   Donc X* le monoïde libre engendré par X et on écrit : < X*, .  , > Exercice : quand est ce qu’on dit qu’un monoïde est libre ? b) La puissance d’un mot : Soit un alphabet X et w  X*  n w            1 n si w w ww 1 n si w 0 n si 1 n 1 n  Exemple : soit X= {a, b} et w = abb   0 w abb w w w     . 1 abbabb ww ww w 1 2    abbabbabb www ww w 2 3    Module : La théorie des langages Niveau : 2ème année licence Préparé par Mohamed TOUMI Page : 5 Janvier 2016 ce cours se trouve sur http://fac-sciences.univ-batna.dz/cs/enseignants/mohamed_toumi_site/ c) Factorisation d’un mot : soit un alphabet X et w, u * X   u est un facteur gauche (préfixe) de w uv w que tel X v *      u est un facteur droit (suffixe) de w vu w que tel X v *      u est un préfixe propre de w uv w que tel X v       u est un suffixe propre de uploads/Marketing/ cour-thl-theorie-des-langage.pdf