% INF7541 — Théorie des langages et des automates % UQAM — Département d'informatique % Plan de cours — Hiver 2021 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Brlek, Srecko PK-4715 Groupes: 020 Description du cours ==================== Langages, grammaires et automates. Familles de langages: propriété de clôture, formes normales, propriétés d'itération. Transformations de langages. Propriétés décidables des langages et leur complexité; propriétés indécidables. Objectif du cours ================= On se propose d'exposer le cadre théorique pour l'étude des langages formels : le monoïde libre. On étudiera en détail les langages rationnels et algébriques, ainsi que les transductions rationnelles. Les utilisations des automates dans divers domaines d'applications seront également abordées. Contenu du cours ================ - Introduction : le monoïde libre. - Les langages reconnaissables. - Les langages rationnels (ou réguliers). - Les langages algébriques. - Les transductions rationnelles. - Applications diverses : théorie des nombres, les compilateurs, théorie du contrôle, systèmes de transitions, synthèse de processus communicants, compression d'images, etc. Modalités d'évaluation ====================== L'évaluation est à déterminer lors de notre première rencontre Les règlements concernant le plagiat seront strictement appliqués. Pour plus de renseignements, consultez le site suivant : HTTP//WWW.SCIENCES.UQAM.CA/ETUDIANTS/INTEGRITE-ACADEMIQUE.HTML Médiagraphie ============ vr A.V. AHO, J.D. ULLMAN - Foundations of Computer Science - COMPUTER SCIENCE PRESS. 1992. vr J. M. AUTEBERT - Langages algébriques - MASSON. 1987. vr J. BERSTEL - Transductions and Context-free Languages - TEUBNER STUDIENBÜCHER. 1979. vr J. BERSTEL, C. REUTENAUER - Les séries rationnelles et leurs langages - MASSON. 1984. vr S. EILENBERG - Automata, Languages and Machines, vol. A - ACADEMIC PRESS. 1974. vr S. GINSBURG - The mathematical Theory of Context-free Languages - MCGRAW-HILL. 1966. vr J.E. HOPCROFT, J.D. ULLMAN - Formal Languages and their Relation to Automata - ADDISON-WESLEY. 1969. vr J.E. HOPCROFT, J.D. ULLMAN - Introduction to Automata Theory, Languages and Computation - ADDISON-WESLEY. 1969. vr M. LOTHAIRE - Combinatorics on Words - ADDISON-WESLEY. 1983. vr J.E. PIN - Variétés de langages formels - MASSON. 1984. vr J. SAKAROVITCH - léments de théorie des automates - VUIVERT. 2003. Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press, 2009. vr J. VAN LEEUWEN, ED. - Gandbook of Computer Science - VOL. B, MIT PRESS, ELSEVIER. 1990. vr D. WOOD - Theory of Computation - WILEY. 1987.