Fondamentaux de la théorie des automates : de l'intuition aux méthodes formelles en 400 exercices corrigés : classes préparatoires, licence, master, agrégation

Auteur(s) :

Séébold, Patrice Découvrir l'auteur

Résumé

401 exercices ou problèmes accompagnés de leurs corrigés et de rappels de cours pour appréhender la théorie des automates. Avec un accent mis sur la compréhension des méthodes de résolution et leur adéquation avec la nature des objets étudiés. ©Electre 2020

Éditeur(s)
- Ellipses
Date
- DL 2020
Langues
- Français
Description matérielle
- 1 vol. (IX-400 p.) : ill. ; 24 cm
Collections
- Références sciences
Sujet(s)
ISBN
- 978-2-340-03668-0
Indice
- 681.0 Mathématiques pour l'informatique
Quatrième de couverture
- Fondamentaux de la théorie des automates
  De l'intuition aux méthodes formelles en 400 exercices corrigés
  Cet ouvrage est dédié à la partie de la théorie des langages formels qui concerne les automates finis. Il regroupe 401 exercices ou problèmes avec leurs corrections détaillées ainsi que des rappels de cours étoffés.
  L'accent est mis sur la compréhension des méthodes de résolution et leur adéquation avec la nature des objets étudiés. À cette fin, des techniques de résolution intuitives accompagnent systématiquement la mise en oeuvre d'algorithmes rigoureusement prouvés.
  Cet ouvrage s'adresse prioritairement aux étudiants et aux enseignants de licences et de masters universitaires d'informatique, aux élèves des classes préparatoires et aux agrégatifs.
  Il est organisé, selon un découpage classique du domaine, en sept chapitres (Notions de mots et de langages, Automates finis et langages reconnus. Langages reconnaissables, Déterminisme, Minimalité, Langages non reconnaissables, Compléments) accompagnés d'un huitième chapitre regroupant plusieurs problèmes, et d'un index.
Tables des matières
- - Fondamentaux de la théorie des automates
  - De l'intuition aux méthodes formelles en 400 exercices corrigés
  - Patrice Séébold
  - Ellipses
  - 1 Notions de mots et de langages1
  - 1.1 Définitions et notations1
  - 1.2 Exercices4
  - 1.3 Solutions8
  - 2 Automates finis et langages reconnus23
  - 2.1 Définitions et propriétés23
  - 2.1.1 Graphe d'états de l'automate23
  - 2.1.2 Table de transitions25
  - 2.1.3 Langages reconnaissables25
  - 2.2 Langage reconnu par un automate fini26
  - 2.2.1 Méthode intuitive26
  - 2.2.2 L'algorithme de Mac Naughton et Yamada27
  - 2.3 Exercices33
  - 2.3.1 Produits d'automates33
  - 2.3.2 Boucles35
  - 2.3.3 Simplifications37
  - 2.3.4 Automates généraux39
  - 2.4 Solutions42
  - 2.4.1 Produits d'automates42
  - 2.4.2 Boucles54
  - 2.4.3 Simplifications65
  - 2.4.4 Automates généraux71
  - 3 Langages reconnaissables83
  - 3.1 Simplification des automates83
  - 3.1.1 Standardisation84
  - 3.1.2 Émondage85
  - 3.2 Propriétés de fermeture88
  - 3.2.1 Langages finis88
  - 3.2.2 Facteurs90
  - 3.2.3 Union91
  - 3.2.4 Produit93
  - 3.2.5 Étoile95
  - 3.3 Associer un automate fini à un langage97
  - 3.3.1 À partir d'une expression rationnelle98
  - 3.3.2 À partir d'une propriété spécifique104
  - 3.4 Exercices106
  - 3.4.1 Propriétés de fermeture106
  - 3.4.2 Expressions rationnelles107
  - 3.4.3 Propriétés spécifiques108
  - 3.5 Solutions109
  - 3.5.1 Propriétés de fermeture109
  - 3.5.2 Expressions rationnelles111
  - 3.5.3 Propriétés spécifiques129
  - 4 Déterminisme143
  - 4.1 Déterminisation d'un automate144
  - 4.1.1 Algorithme de déterminisation146
  - 4.1.2 Retour sur l'algorithme de Glushkov148
  - 4.2 D'autres propriétés de fermeture149
  - 4.2.1 Complétion149
  - 4.2.2 Complémentation151
  - 4.2.3 Intersection et union153
  - 4.3 Exercices158
  - 4.3.1 Automates déterministes, déterminisation d'automates158
  - 4.3.2 Utilisation des propriétés de fermeture159
  - 4.4 Solutions160
  - 4.4.1 Automates déterministes, déterminisation d'automates160
  - 4.4.2 Utilisation des propriétés de fermeture191
  - 5 Minimalité209
  - 5.1 L'automate minimal209
  - 5.2 Minimalisation d'un automate211
  - 5.2.1 L'équivalence de Nérode212
  - 5.2.2 L'algorithme de Moore213
  - 5.2.3 Un automate minimal pour le langage vide218
  - 5.2.4 Vérifier qu'un automate est minimal219
  - 5.3 Construction d'un automate minimal223
  - 5.3.1 Méthode intuitive223
  - 5.3.2 Calcul des résiduels224
  - 5.4 Exercices227
  - 5.4.1 Automates minimaux227
  - 5.4.2 Construction d'automates minimaux228
  - 5.5 Solutions229
  - 5.5.1 Automates minimaux229
  - 5.5.2 Construction d'automates minimaux267
  - 6 Langages non reconnaissables285
  - 6.1 Le théorème de l'étoile285
  - 6.2 Utilisation des propriétés de fermeture290
  - 6.3 Retour sur les résiduels291
  - 6.4 Exercices292
  - 6.5 Solutions294
  - 7 Compléments305
  - 7.1 Le théorème de Kleene305
  - 7.2 Le monoïde syntaxique307
  - 7.3 Vérifier l'égalité de deux langages311
  - 7.3.1 Méthodes intuitives311
  - 7.3.2 Construction d'automates minimaux313
  - 7.3.3 Calcul des résiduels314
  - 7.3.4 Et si les langages sont différents315
  - 7.4 Automates avec e-transitions315
  - 7.5 Exercices319
  - 7.5.1 Le théorème de Kleene319
  - 7.5.2 Le monoïde syntaxique319
  - 7.5.3 Vérifier l'égalité de langages320
  - 7.5.4 Automates avec e-transitions325
  - 7.6 Solutions326
  - 7.6.1 Le théorème de Kleene326
  - 7.6.2 Le monoïde syntaxique331
  - 7.6.3 Vérifier l'égalité de langages342
  - 7.6.4 Automates avec e-transitions370
  - 8 Problèmes375
  - 8.1 Énoncés375
  - 8.2 Solutions378
  - Bibliographie397
  - Index398
Origine de la notice:
- Electre