S4 - Mathématiques Théorie des langages notes de cours version du 21 mars 2014

S4 - Mathématiques Théorie des langages notes de cours version du 21 mars 2014 michel billaud département informatique iut de bordeaux Avant-Propos Ce document contient mes notes personnelles pour préparer un cours de Théorie des Langages de 16 heures (sur 4 semaines) destiné aux étudiants de 2ième année d'IUT Informatique, au printemps 2014. Il s'est trouvé que le programme pédagogique national (PPN) a changé récemment, et que ce cours donné traditionnellement au se- mestre 4 (seconde année) est maintenant fait au semestre 2. Pendant l'année de transition, il fallait faire ce cours en première année du nou- veau PPN et en deuxième année de l'ancien. Il se trouve qu'en plus il fallait remplacer le collègue mathématicien qui assurait jusque-là ce cours, c'était l'occasion de me remettre à la théorie des langages. Malgré le volume horaire restreint (16h), j'ai décidé de parler un peu des langages algébriques qui passent souvent à la trappe en DUT. Il me parait important de faire le lien avec la syntaxe (et la compilation) des langages de programmation, qui est quand même la motivation princi- pale pour faire ce cours en DUT, du point de vue des informaticiens... Dans ce cours, j'ai essayé de montrer un lien avec les applications re- lative traditionnelles à la programmation : automates de reconnaissance syntaxique, analyse des langages de programmation, ... tout en mon- trant des techniques mathématiques nouvelles (pour les étudiants) : tra- vailler dans un produit cartésien (intersection de langages rationnels), dans l'ensemble des parties d'un ensemble (déterminisation), principe des tiroirs et des chaussettes (pour montrer que {anbn} n'est pas ra- tionnel), etc. En tout cas j'ai eu plaisir à préparer ce cours, même pour une seule fois, et j'espère ne pas avoir trop traumatisé mes étudiants ! 2 Table des matières I Pour commencer 5 1 Motivations 5 1.1 Linguistique . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Langages informatiques . . . . . . . . . . . . . . . . . 5 1.3 Développements mathématiques . . . . . . . . . . . . 5 2 Langages formels 6 2.1 Alphabet, lettres, mots . . . . . . . . . . . . . . . . . 6 2.2 Concaténation, facteurs . . . . . . . . . . . . . . . . . 6 2.3 Langages . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Opérations sur les langages . . . . . . . . . . . . . . . 8 2.5 Comment dé nir un langage ? . . . . . . . . . . . . . . 9 2.6 Reconnaissance de motifs . . . . . . . . . . . . . . . . 10 2.6.1 Backtracking . . . . . . . . . . . . . . . . . . 10 2.6.2 Version récursive . . . . . . . . . . . . . . . . 12 2.6.3 Version itérative . . . . . . . . . . . . . . . . . 13 2.7 Eviter le backtracking . . . . . . . . . . . . . . . . . . 15 II Langages rationnels 16 3 Automates nis déterministes 16 3.1 Dé nition . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Quelques exemples . . . . . . . . . . . . . . . . . . . . 16 3.3 Comment coder un automate . . . . . . . . . . . . . . 16 3.4 Un exemple plus détaillé . . . . . . . . . . . . . . . . . 18 3.5 Applications . . . . . . . . . . . . . . . . . . . . . . . 19 3.6 Langages rationnels . . . . . . . . . . . . . . . . . . . 19 3.7 Un langage qui n'est pas rationnel . . . . . . . . . . . 20 3.8 Complément d'un langage rationnel . . . . . . . . . . 20 3.9 Intersection et Union, automate produit . . . . . . . . 21 3.10 Concaténation de langages . . . . . . . . . . . . . . . 22 3 4 Automates non deterministes 23 4.1 Un automate non-déterministe . . . . . . . . . . . . . 23 4.2 Retour sur l'union . . . . . . . . . . . . . . . . . . . . 24 4.3 Déterminisation . . . . . . . . . . . . . . . . . . . . . 24 4.4 Automates avec ϵ-transitions . . . . . . . . . . . . . . 25 4.5 Concaténation de langages . . . . . . . . . . . . . . . 26 4.6 Etoile . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.7 Elimination des ϵ-transitions . . . . . . . . . . . . . . 26 4.8 Conséquence : le théorème de Kleene . . . . . . . . . . 27 4.9 Quelques autres propriétés . . . . . . . . . . . . . . . 28 4.10 Cas pratiques . . . . . . . . . . . . . . . . . . . . . . 28 5 Expressions régulières 30 5.1 Notion . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2 De l'expression à l'automate . . . . . . . . . . . . . . 30 5.3 De l'automate à l'expression régulière . . . . . . . . . 30 5.4 Résultat : le lemme d'Arden . . . . . . . . . . . . . . . 31 III Langages algébriques 33 6 Grammaires algébriques 33 6.1 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . 33 7 Langages algébriques 34 8 Automates à pile 36 9 BNF 38 9.1 BNF de base . . . . . . . . . . . . . . . . . . . . . . . 38 9.2 Extensions . . . . . . . . . . . . . . . . . . . . . . . . 39 9.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . 39 10 Diagrammes syntaxiques 41 10.1 Déterministe ou pas ? . . . . . . . . . . . . . . . . . . 43 10.2 Un systeme d'inequations . . . . . . . . . . . . . . . . 44 10.3 Use the computer, Luke . . . . . . . . . . . . . . . . . 44 10.4 Compléments . . . . . . . . . . . . . . . . . . . . . . 45 11 Descente récursive, un exemple 46 4 Première partie Pour commencer 1 Motivations 1.1 Linguistique La théorie des langages est issue de problématiques de linguistique, pour l'étude de la structure des langues naturelles. Une problématique était d'indeti er des structures, comme par exemple la décomposition d'une phrase en groupe sujet/groupe verbal/complé- ment, structures qui peuvent être communes à des groupes de langues Remonter à une langue originelle et/ou identi er des mécanismes innés communs à l'espèce humaine, qui prédisposeraient à l'usage d'une langue. 1.2 Langages informatiques À la n des années 50 sont apparus les premiers langages de pro- grammation. Au début, la programmation consistait à établir des listes d'instructions machine, mais assez rapidement est apparu le besoin d'écrire des programmes sous une forme plus naturelle, dans laquelle les éléments (fonctions, instructions, déclarations, expressions, etc) sont combinés selon des règles précises. Avec cela, la dé uploads/s3/ notes-de-cours-langages.pdf

Tags
Administrationlangages langage chaine exemple automates
Documents similaires
  • 23
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager