Remerciez-le!

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

Cours de theorie des langages

Cours de théorie des langages Responsable du cours et des TDs Mr BESSAOUD Le Objectifs de la matière ? La théorie des langages a pour objectif de décrire les langages formels ? L ? objectif de cette matière est de ma? triser les types de langages existants ainsi que les automates qui permettent de les reconna? tre ? Ce cours est une base pour le cours de compilation Un Langage ? Qu'est-ce qu ? un langage Tout système permettant de s ? exprimer Exemple Langage linguistique Langage mathématique Langage informatique ? La théorie des langages étudie les aspects purement syntaxiques de tels langages c'est-à-dire leurs structures internes formelles ? Syntaxe des langages Mots Symboles Un alphabet ? Un ensemble de symboles ?ni permettant de construire les mots d ? un langage ? Exemple if then else x y z - a b Un mot ? Un mot sur un alphabet est une séquence ?nie et ordonnée éventuellement vide de symboles de l ? alphabet ? Exemple est un mot de l ? alphabet a b est un mot de l ? alphabet - a b ? Le mot vide est noté F E F E Propriétés ? La longueur d ? un mot m est noté m ? La concaténation Soient deux mots u et v dé ?nis sur un alphabet A La concaténation de u avec v notée u v ou simplement uv est le mot formé en faisant suivre les symboles de u par les symboles de v C La puissance ? On note A l ? ensemble des mots de longueur supérieure ou égale à que l ? on peut construire à partir de l ? alphabet A ? On note A ? l ? ensemble des mots que l ? on peut construire à partir de A y compris le mot vide A ? ?? A ? Etant donnée u et v deux mots on note uv pour uvuv u v pour uuuv u v pour uuuvuuuv Un langage ? Un langage dé ?ni sur un alphabet A est un ensemble de mots dé ?nis sur A Autrement dit un langage est un sous-ensemble de A ? ? Description d ? un langage Un langage ?ni peut être décrit par l ? énumération des mots qui le composent Certains langages in ?nis peuvent être décrits par l ? application d ? opérations à des langages plus simples Certains langages in ?nis peuvent être décrits par un ensemble de règles appelé grammaire En ?n certains langages in ?nis ne peuvent pas être décrits ni par l ? application d ? opérations ni par un ensemble de règles On parle alors de langage indécidable On peut noter que si un langage est indécidable alors il n ? existe pas d ? algorithme permettant de déterminer si un mot donné appartient à ce langage Une grammaire ? Un langage peut être décrit par un certain nombre de règles Pour les langages naturels le but étant de donner une description