Remerciez-le!

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

Mathématiques IUT INFO1 / 2011-2012 Licence Creative Commons MAJ: 9 janvier 201

Mathématiques IUT INFO1 / 2011-2012 Licence Creative Commons MAJ: 9 janvier 2012 Machines de TURING Langages Automates Grammaires Guillaume CONNAN TA B L E D E S M AT I È R E S 1 Machines de Turing 132 1.1 Approche historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 1.2 Les machines de TURING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 1.2.1 Description sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 1.2.2 Un exemple pour découvrir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 1.2.3 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 1.2.4 Fonctions MT-calculables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 1.2.5 Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 1.3 EXERCICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 1.3.1 Machines de TURING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 1.3.2 Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 2 Langages et automates 143 2.1 Langages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 2.1.1 Un exemple pour découvrir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 2.1.2 Déﬁnitions et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 2.1.3 Langages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 2.1.4 Langages et expressions rationnels (ou réguliers) . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 2.2 Automates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 2.2.1 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 2.2.2 Langage reconnaissable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 2.2.3 Langage reconnu par un automate ﬁni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 2.2.4 Automates équivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 2.2.5 Automates standards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 2.2.6 Automates déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 2.2.7 Automates émondés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 2.2.8 Automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 2.2.9 Opérations rationnelles sur les automates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 2.2.10 Théorème de KLEENE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 2.2.11 Automate associé à un langage déﬁni par une expression rationnelle . . . . . . . . . . . . . . . 163 2.2.12 Automates séquentiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 2.2.13 Automates à pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 2.2.14 Machines de TURING : le retour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 2.3 Grammaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . uploads/Industriel/ poly-automates-info1.pdf