Remerciez-le!

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

Notes de cours langages Théorie des langages notes de cours version du mars michel billaud département informatique iut de bordeaux S - Mathématiques CAvant-Propos Ce document contient mes notes personnelles pour préparer un cours de Théorie des Langages

Théorie des langages notes de cours version du mars michel billaud département informatique iut de bordeaux S - Mathématiques CAvant-Propos Ce document contient mes notes personnelles pour préparer un cours de Théorie des Langages de heures sur semaines destiné aux étudiants de ième année d'IUT Informatique au printemps Il s'est trouvé que le programme pédagogique national PPN a changé récemment et que ce cours donné traditionnellement au semestre seconde année est maintenant fait au semestre Pendant l'année de transition il fallait faire ce cours en première année du nouveau 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 h 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 principale 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 relative traditionnelles à la programmation automates de reconnaissance syntaxique analyse des langages de programmation tout en montrant des techniques mathématiques nouvelles pour les étudiants travailler 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 CTable des matières I Pour commencer Motivations Linguistique Langages informatiques Développements mathématiques Langages formels Alphabet lettres mots Concaténation facteurs Langages Opérations sur les langages C Comment dé nir un langage Reconnaissance de motifs Backtracking Version récursive Version itérative Eviter le backtracking II Langages rationnels C Automates nis déterministes C Dé nition Quelques exemples Comment coder un automate Un exemple plus détaillé Applications Langages rationnels Un langage qui n'est pas rationnel Complément d'un langage rationnel Intersection et Union automate produit Concaténation de langages C Automates non deterministes Un automate non-déterministe Retour sur l'union Déterminisation Automates avec -transitions Concaténation de langages Etoile Elimination des -transitions Conséquence le théorème de Kleene Quelques autres propriétés Cas pratiques Expressions régulières Notion De l'expression à l'automate De l'automate à l'expression régulière Résultat le lemme d'Arden III Langages algébriques Grammaires algébriques C Dé nitions Langages algébriques Automates à pile BNF BNF de base Extensions Exercices Diagrammes syntaxiques Déterministe ou pas Un systeme d'inequations Use the computer Luke Compléments Descente récursive un exemple CPremière partie Pour commencer Motivations Linguistique La théorie des langages est issue de problématiques de linguistique pour l'étude de la C 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 C groupes de langues Remonter à une langue originelle et