Automates à états finis et langages réguliers : rappels des notions essentielles et plus de 170 exercices corrigés

Auteur(s) :

Falcone, Yliès Découvrir l'auteur

Résumé

Un manuel sur la théorie des langages et leur reconnaissance par des automates. Ce domaine de l'informatique se situe à la croisée des mathématiques et de l'électronique et a de nombreuses applications : conception de processeurs, compilation de programmes, traduction automatique, intelligence artificielle, bio-informatique, cyber-sécurité. Avec des exercices pour s'entraîner. ©Electre 2020

Autre(s) auteur(s)
- Fernandez, Jean-Claude (1954-....)
Éditeur(s)
- Dunod
- Impr. Laballery
Date
- DL 2020
Notes
- Bibliogr. p.[311]-312. Index
Langues
- Français
Description matérielle
- 1 vol. (320 p.) : ill. ; 24 cm
Collections
- Info sup (Paris. 2015)
Sujet(s)
ISBN
- 978-2-10-080846-5
Indice
- 681.22(07) Langages. Environnements de développement. Manuels
Quatrième de couverture
- Automates à états finis et langages réguliers
  Rappels des notions essentielles et plus de 170 exercices corrigés
  La théorie des langages et des automates est un enseignement incontournable dans tout cursus d'informatique puisqu'on en retrouve des applications dans des domaines aussi divers que la conception des processeurs, la compilation de programmes, la traduction automatique des langues naturelles, l'intelligence artificielle, la bio-informatique, la vérification de programmes embarqués, la cybersécurité...
  Cet ouvrage s'adresse aux étudiants de premier cycle universitaire suivant un cursus incluant l'informatique, qu'ils soient étudiants en IUT, en licence ou en classes préparatoires aux grandes écoles.
  Chaque chapitre comporte un rappel des notions essentielles du cours, des exercices simples d'application pour l'appropriation des notions, et des exercices plus avancés pour la maîtrise des concepts.
  Une solution complète est fournie pour tous les exercices proposés.
Tables des matières
- - Automates à états finis et langages réguliers
  - Rappels des notions essentielles et plus de 170 exercices corrigés
  - Yliès Falcone
  - Jean-Claude Fernandez
  - Dunod
  - Avant-propos9
  - Introduction13
  - 1 Rappels et notations 19
  - 1.1 Notions de logique, assertions19
  - 1.2 Quantificateurs21
  - 1.3 Notions ensemblistes22
  - 1.4 Entiers naturels25
  - 1.5 Ensembles définis inductivement26
  - 1.6 Raisonnements, techniques de preuve26
  - 2 Notions préliminaires 29
  - 2.1 Résumé intuitif du chapitre29
  - 2.2 Les notions essentielles29
  - 2.3 Exercices32
  - 2.3.1 Mots et concaténation32
  - 2.3.2 Langages33
  - 2.3.3 Concaténation de langages34
  - 2.4 Indications pour résoudre les exercices35
  - 2.5 Solutions des exercices37
  - 2.5.1 Mots et concaténation37
  - 2.5.2 Langages41
  - 2.5.3 Concaténation de langages42
  - 3 Automates déterministes 45
  - 3.1 Résumé intuitif du chapitre45
  - 3.2 Les notions essentielles46
  - 3.2.1 Définition et langage reconnu46
  - 3.2.2 Accessibilité et coaccessibilité48
  - 3.3 Exercices49
  - 3.3.1 Automate et langage reconnu49
  - 3.3.2 Automate reconnaissant un langage50
  - 3.3.3 Fonction de transition d'un automate51
  - 3.3.4 Langage à états ou non53
  - 3.3.5 Accessibilité et coaccessibilité53
  - 3.3.6 Automates et langages particuliers53
  - 3.4 Indications pour résoudre les exercices54
  - 3.5 Solutions des exercices55
  - 3.5.1 Automate et langage reconnu55
  - 3.5.2 Automate reconnaissant un langage59
  - 3.5.3 Fonction de transition d'un automate66
  - 3.5.4 Accessibilité et coaccessibilité69
  - 3.5.5 Automates et langages particuliers70
  - 4 Opérations sur les automates déterministes 71
  - 4.1 Résumé intuitif du chapitre71
  - 4.2 Les notions essentielles72
  - 4.3 Exercices74
  - 4.3.1 Automate complet / complété74
  - 4.3.2 Automate complémentaire74
  - 4.3.3 Automate produit75
  - 4.4 Indications pour résoudre les exercices76
  - 4.5 Solutions des exercices77
  - 4.5.1 Automate complété77
  - 4.5.2 Automate complémentaire81
  - 4.5.3 Automate produit85
  - 5 Algorithmes sur les automates déterministes 89
  - 5.1 Résumé intuitif du chapitre89
  - 5.2 Les notions essentielles90
  - 5.2.1 Successeurs et prédécesseurs d'un état90
  - 5.2.2 Parcours90
  - 5.2.3 Notions d'accessibilité et de coaccessibilité93
  - 5.2.4 Détection de cycles97
  - 5.2.5 Quelques problèmes de décision98
  - 5.3 Exercices101
  - 5.3.1 Complétion, complémentation et produit101
  - 5.3.2 Émonder un automate102
  - 5.3.3 Inclusion et égalité des langages reconnus par des automates102
  - 5.3.4 Autour de la notion de préfixe103
  - 5.4 Indications pour résoudre les exercices103
  - 5.4.1 Compléter un automate103
  - 5.4.2 Émonder un automate104
  - 5.4.3 Inclusion et égalité des langages reconnus par des automates105
  - 5.4.4 Autour de la notion de préfixe105
  - 5.5 Solutions des exercices106
  - 5.5.1 Compléter un automate106
  - 5.5.2 Émonder un automate110
  - 5.5.3 Inclusion et égalité des langages reconnus par des automates112
  - 5.5.4 Autour de la notion de préfixe113
  - 6 Minimisation d'automates déterministes 119
  - 6.1 Résumé intuitif du chapitre119
  - 6.2 Les notions essentielles120
  - 6.2.1 Relation de distinguabilité entre états121
  - 6.2.2 Relation d'équivalence entre états d'un AFED123
  - 6.2.3 Minimisation125
  - 6.2.4 Tester l'équivalence entre deux AFED125
  - 6.3 Exercices126
  - 6.3.1 Équivalence et distinguabilité entre états126
  - 6.3.2 Minimisation127
  - 6.3.3 Équivalence et distinguabilité entre AFED129
  - 6.4 Indications pour résoudre les exercices129
  - 6.5 Solutions des exercices130
  - 6.5.1 Équivalence et distinguabilité entre états130
  - 6.5.2 Minimisation130
  - 6.5.3 Équivalence et distinguabilité135
  - 7 Automates non déterministes 143
  - 7.1 Résumé intuitif du chapitre143
  - 7.2 Les notions essentielles144
  - 7.2.1 Définition et langage reconnu144
  - 7.2.2 Déterminisation des automates non déterministes145
  - 7.3 Exercices146
  - 7.3.1 Langage et AFEND146
  - 7.3.2 Déterminiser un AFEND148
  - 7.3.3 Équivalence entre AFEND149
  - 7.3.4 Complexité150
  - 7.3.5 Algorithmes pour les AFEND151
  - 7.4 Indications pour résoudre les exercices151
  - 7.5 Solutions des exercices153
  - 7.5.1 Langage et AFEND153
  - 7.5.2 Déterminiser un AFEND158
  - 7.5.3 Déterminer l'équivalence entre deux AFEND161
  - 7.5.4 Complexité162
  - 7.5.5 Algorithmes pour les AFEND166
  - 8 Automates non déterministes avec e-transitions 167
  - 8.1 Résumé intuitif du chapitre167
  - 8.2 Les notions essentielles168
  - 8.2.1 Définition et langage reconnu168
  - 8.2.2 Élimination des e-transitions168
  - 8.2.3 Retour sur la fermeture de la classe des langages à états170
  - 8.3 Exercices172
  - 8.3.1 Trouver un automate173
  - 8.3.2 Fermeture de Kleene175
  - 8.3.3 Élimination des e-transitions et déterminisation175
  - 8.3.4 Composition et transformation d'e-AFEND177
  - 8.3.5 Algorithmes sur les e-AFEND179
  - 8.4 Indications pour résoudre les exercices179
  - 8.5 Solutions des exercices182
  - 8.5.1 Trouver un automate182
  - 8.5.2 Fermeture de Kleene186
  - 8.5.3 Élimination des e-transitions et déterminisation189
  - 8.5.4 Composition et transformation d'e-AFEND193
  - 8.5.5 Algorithmes sur les e-AFEND201
  - 9 Expressions régulières 205
  - 9.1 Résumé intuitif du chapitre205
  - 9.2 Les notions essentielles206
  - 9.2.1 Syntaxe des expressions régulières206
  - 9.2.2 Sémantique des expressions régulières206
  - 9.2.3 Conventions de notation et précédence des opérateurs207
  - 9.2.4 Quelques propriétés : équivalence et simplification207
  - 9.2.5 Quelques problèmes de décision : équivalence et inclusion de langages dénotés207
  - 9.3 Exercices208
  - 9.4 Indications pour résoudre les exercices210
  - 9.5 Solutions des exercices211
  - 10 Théorème de Kleene 219
  - 10.1 Résumé intuitif du chapitre219
  - 10.2 Les notions essentielles220
  - 10.2.1 Théorème de Kleene220
  - 10.2.2 Des automates vers les expressions régulières220
  - 10.2.3 Des expressions régulières vers les automates224
  - 10.3 Exercices228
  - 10.3.1 Calcul d'expressions régulières à partir d'automates229
  - 10.3.2 Calcul d'automates à partir d'expressions régulières231
  - 10.4 Indications pour résoudre les exercices232
  - 10.5 Solutions des exercices233
  - 10.5.1 Calcul d'expressions régulières à partir d'automates233
  - 10.5.2 Calcul d'automates à partir d'expressions régulières241
  - 11 Grammaires 247
  - 11.1 Résumé intuitif du chapitre247
  - 11.2 Les notions essentielles247
  - 11.2.1 Définition des grammaires247
  - 11.2.2 Dérivations en une et plusieurs étapes248
  - 11.2.3 Langage généré par une grammaire248
  - 11.2.4 Classification de Chomsky des grammaires248
  - 11.3 Exercices249
  - 11.3.1 Générer des mots avec les grammaires249
  - 11.3.2 Langages et grammaires250
  - 11.4 Indications pour résoudre les exercices251
  - 11.5 Solutions des exercices252
  - 11.5.1 Générer des mots avec les grammaires252
  - 11.5.2 Langages et grammaires252
  - 12 Grammaires régulières 257
  - 12.1 Résumé intuitif du chapitre257
  - 12.2 Les notions essentielles257
  - 12.2.1 Grammaires et automates257
  - 12.2.2 Grammaires et expressions régulières260
  - 12.3 Exercices261
  - 12.3.1 Des grammaires vers les automates261
  - 12.3.2 Des automates vers les grammaires261
  - 12.3.3 Des expressions régulières vers les automates et les grammaires262
  - 12.3.4 Grammaires non régulières262
  - 12.3.5 Composition de grammaires régulières263
  - 12.4 Solutions des exercices263
  - 12.4.1 Des grammaires vers les automates263
  - 12.4.2 Des automates vers les grammaires264
  - 12.4.3 Des expressions régulières vers les automates et les grammaires269
  - 12.4.4 Grammaires non régulières269
  - 12.4.5 Composition de grammaires régulières271
  - 13 Propriété de l'itération 273
  - 13.1 Résumé intuitif du chapitre273
  - 13.2 Les notions essentielles273
  - 13.2.1 Lemme de l'itération273
  - 13.2.2 Constante d'itération274
  - 13.3 Exercices275
  - 13.3.1 Lemme de l'itération275
  - 13.3.2 Constante d'itération275
  - 13.4 Indications pour résoudre les exercices275
  - 13.5 Solutions des exercices276
  - 13.5.1 Lemme de l'itération276
  - 13.5.2 Constante d'itération277
  - 14 Démontrer la non-régularité 281
  - 14.1 Résumé intuitif du chapitre281
  - 14.2 Les notions essentielles281
  - 14.2.1 Utilisation du lemme de l'itération281
  - 14.2.2 Utilisation des propriétés de fermeture282
  - 14.2.3 Une condition suffisante pour la non-régularité283
  - 14.3 Exercices283
  - 14.3.1 Lemme de l'itération283
  - 14.3.2 Fermeture des langages réguliers284
  - 14.3.3 Une condition suffisante pour la non-régularité286
  - 14.4 Indications pour résoudre les exercices286
  - 14.5 Solutions des exercices287
  - 14.5.1 Lemme de l'itération287
  - 14.5.2 Fermeture des langages réguliers291
  - 14.5.3 Une condition suffisante pour la non-régularité294
  - A Modélisation et résolution de problèmes avec les automates 295
  - A.1 Exercices295
  - A.2 Solutions des exercices299
  - Bibliographie311
  - Index313
Origine de la notice:
- FR-751131015 ;
- Electre