Remerciez-le!

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

Institut supérieur de gestion Avril 2010 Notions de base de la théorie des lang

Institut supérieur de gestion Avril 2010 Notions de base de la théorie des langages Elaboré par : Habiba Bouzidi Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 Objectifs du cours 1 • Connaître les concepts issus de la théorie des langages. 2 • Générer des mots d’un langage précis. 3 • Reconnaître l’appartenance d’un mot à un langage. 2 Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 Plan du cours • Définitions – Alphabet – Mot – Langage • Système générateur (Grammaire) • Système reconnaisseur (Automate) • Types des langages • Langage algébrique (Type2) • Récapitulatif 3 Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 Références Notes du cours de Mme Lamia El Abed (ISG Tunis) Daniel HERMAN, Théorie des langages et compilation, Octobre 2005, http://perso.univ-rennes1.fr/daniel.herman/ Editions-des-noisettes-et-des-sentiers/noisettes.html 4 Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 •| | • Alphabet : Ensemble fini de symboles (ou caractères), noté X • Mot (ou phrase) : Suite finie d’éléments de X • Notations: • X*: L’ensemble des mots formés à partir de X • | | : X+ → IN : Nombre d’occurrences de symboles de X x → |x| (ou Longueur d’un mot) Exemple: X={a, b}; Soit m1= abbab ; |a|=2, |m1|=5 • X+: X* /{ε} :Ensemble de tous les mots, sauf le mot vide • an : Le mot composé de n occurrences de a (a0 est le mot vide). Définitions Grammaire Automate Types des langages Langage algébrique 5 Vocabulaire • {a, b} • { il, ballon, ,joue, au, je} • {if, then, else, C, X,=,0} Mots • aab, bba, ababa • je joue ballon, il joue • if C then X=0, C if else ● ● ● ● ● ● ● ● ● ● ● Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 • Langage : Un langage L sur X est une partie de X*  Un langage est un ensemble de mots Exemple: X={a,b} • L1:{aa, abba, bba }: langage fini • L2 = = {ab, aaaab, a…….b}: langage infini Comment décrire un langage d’une manière formelle pour faciliter son traitement par un ordinateur? Définitions Grammaire Automates Types des langages Langage algébrique 6   * ' ' * / X w et b aw w X w    ● ● ● ● ● ● ● ● ● ● ● Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 • Formalisme général permettant de décrire un langage. • Repose sur l’utilisation d’un mécanisme génératif capable de produire tous les mots d’un langage donné. • Définition Une grammaire est un quadruplet G = (VT, VN, S, P) où: VT : vocabulaire terminal qui est le vocabulaire du langage VN : vocabulaire non-terminal, (VN ∩ VT = ∅) S : axiome: Є VN P : un ensemble de règles de la forme A → B, A ≠ ε, où A et B Є (VN ∪ VT)* Une règle α → β : α peut être réécrit en β permet de réécrire des mots sur VN ∪ VT Exemple : Définitions Grammaire Automates Types des langages Langage algébrique 7 ● ● ● ● ● ● ● ● ● ● ● α β ω2 β ω1 ω2 α ω1 G Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 • Exemple G=({a}, {S,S1}, S, P) VT : {a} VN : {S,S1} P : (SaS1, S1aS1 , S1  ε) • Notation Etant donné une grammaire G, le langage L(G) est défini par : L(G) = { m ∈ X* | S ⇒G* m} Définitions Grammaire Automates Types des langages Langage algébrique 8 ● ● ● ● ● ● ● ● ● ● ● L(G)={an/ n ≥1} SaS1 S1aS1| ε 1). G = <S>::a<S1> <S1>::a<S1>| ε 2). G = Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 • Un automate permet de caractériser un langage (les mots acceptés). • Définition Un automate à état fini est le cinquplet A = (Q, VT, δ, q0, F) avec Q: Ensemble fini d’états F : Ensemble des états finaux δ : Fonction de transition , δ: Q X VTQ q0 : Etat initial Définitions Grammaire Automates Types des langages Langage algébrique 9 ● ● ● ● ● ● ● ● ● ● ● Automate G Un mot m Oui : si m ∈ L(G) Non :sinon Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 • Exemple: Reconnaître les mot du langage L={ac*b}={ab, acb,accb,acccb,…} A = ({q0,q1,q2}, {a,b,c}, δ, q0, {q2}) δ: Q X VTQ (q0,a) q1 (q1,b)q2 (q1,c)q1 Définitions Grammaire Automates Types des langages Langage algébrique 10 ● ● ● ● ● ● ● ● ● ● ● q1 q2 q0 a b c Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 • Type 3:langage régulier Toutes les règles sont sous la forme: α → x ou α → xβ Avec x Є VT ; α et β Є VN • Type 2: Langage algébrique Toutes les règles sont sous la forme: α → β avec α Є VN ; et β Є (VN U VT ) * • Type 1:langage à contexte lié Toutes les règles sont sous la forme: α → β avec α Є (VN U VT )+ , β Є (VN U VT )* et | α |<=| β | • Type 0: Aucune restriction sur la forme des règles Définitions Grammaire Automates Types des langages Langage algébrique ● ● ● ● ● ● ● ● ● ● ● 11 Exemple 1: pour un langage L={a*} G= SaS Sε SSa Sε ou Exemple 3: Soit L={an bn cn/n ≥0} G= Sε SaRbc|abc RaRTb R aTb TbbT Tccc Exemple 2: Soit L={an bn /n ≥1} G= SaSb|ab Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 * Langage naturel * | α | ≤ | β | * {anbncn/n≥1} * A → β * {anbn/n≥0}, Langages de programmation * Automate à pile * A → a ou A → aB * {Ac*b}, langage de commandes * Automate à états finis Type 0 Type 1 Type 2 Type 3 Définitions Grammaire Automates Types des langages Langage algébrique • Hiérarchie de Chomsky 12 ● ● ● ● ● ● ● ● ● ● ● Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 • Définitions – Grammaire ambigüe : Un mot est ambigüe s’il dispose de plus qu’une suite de dérivation gauche(ou droite) Une grammaire est ambigüe si elle génère au moins un mot ambigüe – Factorisation à gauche : AaB|aC  Exemple: soit G= E →E+E | E*E G’= Définitions Grammaire Automates Types des langages Langage algébrique 13 ● ● ● ● ● ● ● ● ● ● ● A → aD D → B |C E →E E’ E’ →+E|*E Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 – Récursivité à gauche : A → Aα| β  Exemple : soit G = S →Sa|a • m=aaa , dérivation de m= S=>Sa=>Saa=>Saaa…. boucle infinie • Soit G’= • G’G • Dérivation de m: S=>aS’=>aaS’=>aaaS’aaa ε=>aaa = m est accepté Définitions Grammaire Automates Types des langages Langage algébrique 14 ● ● ● ● ● ● ● ● ● ● ● S → aS’ S’ →aS’| ε A → α A’ A’ → β A’ | ε Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 Définitions Grammaire Automates Types des langages Langage algébrique 15 • Soit un alphabet X={a,b}, 1. écrire la grammaire du langage formé sur X et constitué des palindromes. 2. Quel est le type de cette grammaire ? 3. Donner un exemple de dérivation d’un mot. Solution: 1. S → a S a S → b S b S → a S → b S → ε 2. Cette grammaire est de Type 2 car S Є VN , a S a Є (VN U VT ) * (α Є VN et β Є (VN U VT ) * ) 3. SaSaabSbaabaSaba abaεaba Le mot est abaaba ● ● ● ● ● ● ● ● ● ● ● Habiba Bouzidi Notions de base de la théorie des langages ISG Tunis - Avril 2010 Récapitulatif ¤ La théorie des langages = Comprendre le fonctionnement des langages. ¤ Un langage = Ensemble de mots ¤ Un mot (ou lexème) = Une combinaison de symboles ¤ L'ensemble des symboles élémentaires  alphabet ¤ La fonction associant l'alphabet au langage  grammaire ¤ On peut associer à une grammaire un automate Déterminer si un mot fait partie d'un langage. ¤ Domaines d’application : les compilateurs… 16 Merci pour votre uploads/Philosophie/ theorie-des-langages.pdf