Méthodes de spécification et de conception PDF

10/10/2023 Méthodes de spécification et de conception Techniques de conception  Conception fonctionnelle  Conception orientée objet Méthodes de conception  Diagrammes de flux de données,  Machines à états finis,  Réseaux de Petri,  Relations entité,  Méthodes fo...

10/10/2023 Méthodes de spécification et de conception Techniques de conception  Conception fonctionnelle  Conception orientée objet Méthodes de conception  Diagrammes de flux de données,  Machines à états finis,  Réseaux de Petri,  Relations entité,  Méthodes formelles 61 Technique de conception Conception  Processus créatif qui consiste à représenter les diverses fonctions du système permettant d’obtenir rapidement un ou plusieurs programmes réalisant ses fonctions.  Une « bonne » conception se définit en termes de la satisfaction des besoins et des spécifications.  Une bonne Conception participe largement à la production d'un logiciel qui répond aux facteurs de qualité.  Elle se base sur la Modularité et se distingue principalement de trois de méthodes de conception: Méthodes fonctionnelles Méthodes systémiques Méthodes orientées objets 62 1  10/10/2023 Technique de conception Système de gestion  Approche cartésienne. Orientée traitements.  Approche systémique. Orientée données.  Approche Objet. Orientée données et traitements. 63 Conception fonctionnelle Méthodes Fonctionnelles  Les méthodes fonctionnelles ou cartésiennes consistent à décomposer hiérarchiquement une application en un ensemble de sous applications.  Ces méthodes utilisent les raffinements successifs pour produire des spécifications dont l’essentiel est sous forme de notation graphique en diagramme de flots de données.  Points forts Simplicité du processus de conception Capacité à répondre rapidement aux besoins ponctuels des utilisateurs  Points faibles: Fixer les limites pour les décompositions hiérarchiques Redondance (éventuelle) des données 64 2  10/10/2023 Conception fonctionnelle Méthode systématique  Les méthodes systématiques sont influencées par les systèmes de Gestion de bases de données en proposant une double démarche de modélisation: La modélisation des données La modélisation des traitements  Points forts : Approche globale prenant en compte la modélisation des données et des traitements Niveaux d’abstraction dans le processus de conception Bonne adaptation à la modélisation des données et à la conception des BDs  Points faibles Double démarche de conception : données et traitements 65 Pas de fusion possible des deux aspects (données et traitements) Conception fonctionnelle Méthodes fonctionnelle et systématique  Les méthodes fonctionnelles et systémiques sont de type descendant (approache TopDown).  Inconvénients Réutilisabilité : Modules non généraux mais adaptés aux sous problèmes pour lesquels ils ont été concus Extensibilité: L’architecture du logiciel est fondée sur les traitements qui sont moins stables que les données; par conséquent cette approche est inadaptée à la conception de gros logiciel. 66 3  10/10/2023 Conception fonctionnelle MERISE  Méthode d'Étude et de Réalisation Informatique des Systèmes d'Entreprise qui constitue une démarche de construction de SI  Pour les données: Elle sert à identifier les informations essentielles ainsi que les relations entre elles afin que l'ensemble soit le plus efficace et évolutif possible,  Pour les traitements: Elle sert à identifier les fonctionnalités principales selon une approche général/particulier en utilisant le principe de découpage.  Elle se caractérise par une double démarche : par niveau d’abstraction et par étape de construction. 67 Conception fonctionnelle Niveau d’abstraction 68 4  10/10/2023 Conception fonctionnelle Niveau d’abstraction 69 Conception fonctionnelle Etapes de construction  Schéma directeur: Approche globale du SI et analyse des besoins  Étude de faisabilité: Étude des différentes solutions possible puis choix de solution selon les contraintes matérielles et fonctionnelles  Étude détaillée: spécifications fonctionnelles et techniques et rédaction du cahier de charge.  Conception: Structures de données et modules de traitements  Production: implémentation des programmes et tests de validations  Livraison : Contrôle Qualité, déploiement et formation utilisateur  Maintenance: Corrections et adaptations du logiciel 70 5  10/10/2023 Conception fonctionnelle Cycle d’abstraction Système d’information manuel Recueil des informations Délimiter le système. Expression des Besoins … Construire les MCD, MCT, Modèle Conceptuel Construire les MOD, MOT, Modèle Organisationnel Construire (entre autres) les MLD,MPD, … Modèle Opérationnel Système d’information automatique 71 Conception Orientée Objet Méthodesorientéesobjets  Dans une approche Orientée Objet (OO), le logiciel est considéré comme une collection d’objets dissociés définis par des propriétés.  Une propriété est soit un attribut de l’objet ou une opération sur l’objet.  Un objet comprend donc à la fois une structure de données et une collection d’opérations (son comportement).  Contrairement aux méthodes fonctionnelles et systémiques, les méthodes orientées objets sont ascendantes. 72 6  10/10/2023 Conception Orientée Objet Technologie Orientée Objet  Guider la conception par un ensemble de concepts:Abstraction, modularité, Encapsulation, Polymorphisme  Utiliser des langages et outils qui supportent ces concepts Classification vs. prototype Héritage (Simple, Multiple) Typage (Fort, Faible)  Avantages: Reflète plus finement les objets du monde réel Code : facile à maintenir Stabilité: Isolation des changements Réutilisation des composantes facile prototypage 73 Conception Orientée Objet Méthodes Orientées Objets – Exemples Système de gestion d’un lycée Objets Fonctions Personnes  Calculer la moyenne  Etudiant, enseignant,  Calculer les taux d’encadrement principal, secrétaire  Calculer le nombre de redoublants Diplôme  Calculer le taux de réussite au  Année, matière, parcours baccalauréat Notes  Coefficients 74 7  10/10/2023 Conception Orientée Objet Objectifsdestechnologiesà objets  Utiliser le langage du domaine Modèle et vocabulaire métier  Construire des modèles faciles à: Etendre, modifier, valider, vérifier  Faciliter l’implantation Génération facilitée vers les langages à objets  Nécessite une méthode et des outils Rational Unified Process, Agile, … UML est seulement un langage 75 Conception Orientée Objet Concept d’objet  Entité cohérente rassemblant des données et du code travaillant sur ces données  Structure de données valuées qui répond à un ensemble de messages  Caractérisé par : son comportement : que peut-on faire avec cet objet?Méthodes son état : comment réagit l’objet quand on applique ces méthodes? Attributs (Champs) son identité : comment distinguer les objets qui ont le même état et le même comportement?Identifiant  A les mêmes réactions et la même modularité que le monde réel L’objet informatique est une projection de l’objet du monde réel 76 8  10/10/2023 Conception Orientée Objet Concept modèle 77 Conception Orientée Objet Motivations  Quatre objectifs à la modélisation Aider à visualiser le système Spécifier la structure et le comportement Servir de plan pour la construction effective Permettre de documenter les choix  Quatre avantages Abstraction : diviser pour régner Compréhension : mises au point avec le client L’énergie déployée pour modéliser révèle les difficultés Les erreurs sur les modèles coûtent bien moins cher 78 9  10/10/2023 Conception Orientée Objet importance des modèles moins Plus important important Avion Avion papier militaire Le développement logiciel nécessite des modèles bien structurés et puissant 79 Conception Orientée Objet Objets et classess (exemples) Classe Objet Figure longueur rectangle: Figure largeur longueur: 24 origine largeur: 20 périmètre Origine : (12, 20) surface transposer Figure rectangle= new Figure( ); rectangle.surface(); Instanciation 80 10  10/10/2023 Conception Orientée Objet Model Driven Architecture (MDA)  Développement orienté modèles Spécifier un modèle indépendant de la plateforme sur laquelle il sera déployé Spécifier la ou les plateformes Choisir une plateforme adaptée Transformer le modèle de spécification en un modèle spécifique pour la plateforme 81 Conception Orientée Objet Principes de création  Un modèle influence énormément la façon d’aborder le problème et la solution Vue du concepteur BD # vue du programmeur OO  Chaque modèle peut être exprimer à différents niveaux de précision Les meilleurs modèles permettent de choisir le niveau de détail en fonction de qui regarde et pourquoi il le regarde  Les meilleurs modèles sont liés à la réalité  Un seul modèle n’est jamais suffisant Tous les systèmes gagnent à être décrits avec plusieurs petits modèles relativement indépendant => comment assurer la cohérence entre les modèles 82 11  10/10/2023 Conception Orientée Objet Complémentarité des modèles Créer un ou plusieurs modèles différents mais avec un point commun Vue logique Vue d’implantation Analystes/Concepteurs Programmeurs Structure Software management Use-Cas e View Utilisate urfinal Fonctio nalité Vue procédé Vue Déploiement Ingénieursystème Intégrateursystème Topologie du système, livraison, Performance, scalabilité, débit installation, communication 83 Conception Orientée Objet Unified Modeling Language (UML)  Langage visuel unifié  Tout le monde doit parler le même langage  Langage pour spécifier  Executable-UML  Supposé précis et non ambigu  Des liens vers plusieurs langages de programmation  Java, C++, VB  RDMS ou OODMS  Génération de code et reverse engineering. 84 12  10/10/2023 Méthode de conception Modèle de flux, Machines à états finis, Réseaux de Petri, Relations entité, Méthodes formelles. 85 Flux de données Motivations  L’analyse systémique fournie une modélisation de l’organisation échangeant et transformant des flux  Cette modélisation du S.I. reste trop générale  Il faut découper l’organisation en domaines d’activité Pour réduire la complexité de modélisation d’une organisation, Obtenir des tailles de projet maîtrisables  Le découpage s’effectue sur la base des grandes fonctions ou activités de cet organisme: vendre, stocker, acheter, gérer du personnel,.. 86 13  10/10/2023 Flux de données Motivations Chaque domaine est considéré comme quasi-autonome avec son propre système opérant, son propre système de pilotage et son propre système d’information Le SI de l’organisation est alors défini comme la réunion des SI de chaque domaine Les SI résultant de ce découpage en domaines ne sont pas disjoints: ils entretiennent entre eux des flux, ils partagent des perceptions sur l’environnement Problème de Cohérence inter-domaine 87 Flux de données Présentation de modèle de flux Les modèles de flux représentent ce qui doit être étudié dans le cadre du projet à partir de l’analyse des flux échangés. Le Modèle des flux de données permet de déterminer le système à modéliser (champ de l’étude) en indiquant ses frontières et en le décomposant en sous-systèmes Définition: Le modèle est basé sur la notion de système et sa décomposition Un système réagit avec d’autres systèmes à partir de flux d’entrée pour produire des flux de sortie. Un système se décompose en sous-système 88 14  10/10/2023 Flux de données Concepts du modèle Concepts du modèle de flux de données le domaine fonctionnel l’activité l’acteur le flux Définition : le Diagramme de flux est une représentation graphique des acteurs et des flux échangés 89 Flux de données Domaine Un domaine fonctionnel est un découpage de l’organisation. Il correspond à une finalité majeure de l’organisation. Un domaine d’étude est un sous-ensemble de l’organisation dont on étudie séparément le SI. Le découpage en domaines fonctionnels est un quasi-invariant de l’organisation: il correspond aux grandes fonctions ou activités de l’organisation Ce découpage est fixé en entrée d’une étude MERISE et n’est pas de la responsabilité du concepteur Les différents domaines d’étude sont supposés indépendants les uns des autres  interactions limitées et un partage minimum des données 90 15  10/10/2023 Flux de données Domaine: Exemples Domaines fonctionnels crédits, titres, épargne, ressources humaines, comptabilité,... Domaines d’étude: instruction d’un prêt, remboursement anticipé Faible couplage entre les domaines fonctionnels: L’interaction entre le domaine crédit et le domaine comptabilité est limité aux seuls mouvements financiers 91 Flux de données Acteurs L’acteur représente une unité active intervenant dans le fonctionnement d’un système opérant Un acteur peut : être stimulé par des flux transformer des flux renvoyer des flux Un acteur fait quelque chose, il est actif On distingue des acteurs internes ou externes 92 16  10/10/2023 Flux de données Type d'acteurs Un acteur peut modéliser: Un partenaire extérieur à l’organisation: client, fournisseur,... Un domaine d’activité de l’organisation précédemment identifié: la comptabilité, la gestion du personnel,... Un ensemble d’activités: liquidation, contrôle,... Un élément structurel de l‘organisation: service, unité géographique, unité fonctionnelle,... Le système de pilotage, dans ses interactions avec le système opérant ou le SI 93 Flux de données Catégorie d'acteur Un acteur externe ou partenaire représente tout élément extérieur à l’organisation et échangeant des flux avec le domaine d’étude et peut être: Une personne physique (client, fournisseur), Une personne morale (la Banque de France), Une machine extérieure (service vidéotext par exemple) Un acteur interne peut être une personne physique ou morale appartenant au système, capable d’échanger des informations avec les autres acteurs ou partenaires L’acteur interne modélise un élément structurel du domaine d’étude reflète un choix d’organisation Exemple: Emile Zola (une personne), le comptable (une fonction), leposte de saisie (poste de travail) 94 17  10/10/2023 Flux de données Activité Une activité est un ensemble homogène de traitements qui transforme ou manipule des données Une activité est le concept sur lequel s’appuie la décomposition Règle de décomposition du domaine d’étude en activités: Le critère d’arrêt de la décomposition en activités est l’interruptabilité par un flux entrant Exemples: instruction d’un prêt déblocage des fonds remise de chéquier 95 Flux de données Propriété du flux Le flux représente un échange entre deux acteurs Un flux a toujours son origine ou sa destination dans le domaine d’étude Les flux peuvent être classés en 5 catégories: Matière (qui est transformée ou consommée) Finance Personnel Actif (matériel ou savoir-faire nécessaire pour exercer l’activité) Information 96 18  10/10/2023 Flux de données Caractéristique du flux Dans l’utilisation de l’analyse des flux par la méthode MERISE, on s’intéressera principalement aux flux d’informations. Les autres types de flux présentant un intérêt majeur devront être représentés par l’information qui les accompagne Pour chaque flux, on indiquera: Son émetteur Son récepteur Le lot d’informations transmis (le message) Et éventuellement, une justification ou une explication de l’événement (nécessité, réponse d’interviews,…) 97 Flux de données Exemple de flux Domaine d ’étude: Gestion de Prêt Flux entre 2 activités du domaine d’étude: prêt en gestion Flux entre une activité du domaine d’étude et un domaine connexe (comptabilité): opérations à comptabiliser Flux entre une activité du domaine d’étude et un acteur externe (client): proposition de prêt 98 19  10/10/2023 Flux de données Flux particulier Transformation des flux de nature différente en flux d’informations: Exemple: le flux de remise de chèque par un client est représenté par un flux d’information porteur des propriétés du bordereau de remise de chèques Validation des flux: Un flux entrant dans le domaine d’étude, en provenance d’un acteur externe, doit toujours donner lieu à un flux sortant Un flux sortant est en général consécutif à un flux entrant Exception: les flux réglementaires (déclaration fiscale) ou par exemple mailing envoyé à des clients ----> Flux tournants 99 Flux de données Types de Modèles de flux Les différents modèles diffèrent entre eux uniquement par leur niveau d’abstraction: Le modèle Conceptuel ou MFC Le modèle Organisationnel ou MOF Le modèle Physique ou MPF Ces modèles sont représentés par des graphes où: Les sommets sont des émetteurs d’informations ou des récepteurs d’informations Les flèches sont des messages 100 20  10/10/2023 Flux de données MOF: Représentation graphique Exemple: Le client passe commande. Le service commercial peut refuser la commande. Le magasin se charge de l’expédition des marchandises et réceptionne les retours client Commande Commande Acceptée Service Client Commercial Magasin Refus Marchandise + BL Retour Marchandise 101 Flux de données MOF: Représentation graphique Acteurs internes Ordre de livra ison Acteurs externes MAG ASIN B o n de livra ison TRANSPORTEUR Dde de f a ctura tio n Dema nde de li vraiso n CLIE NT FACTURATION Facture Chèque_ Bordereau Double facture CAISSE BANQUE Bordereau de remise de chèque 102 21  10/10/2023 Flux de données Matrice des flux organisés C’est un tableau carré qui représente le MOF En ligne: les acteurs émetteurs En colonne: les acteurs récepteurs Les flux: à l’intersection ligne/colonne Représentation sous forme matricielle: Visualiser l’inventaire exhaustif de la combinatoire des cas possibles Contrôler que les intersections vides le sont bien (ie- on a rien oublié) 103 Flux de données Exemple de MOF VERS Magasin Facturation Caisse Transporteur Client Banque DEPUIS Magasin Dde Ordre facturation livraison Facturation Dble facture Facture Caisse Remise chèque Transporteur Bon livraison Client Dde Chèque livraison Banque 104 22  10/10/2023 Flux de données Graphe acteurs-flux Un assuré demande à souscrire une police d’assurance. Sa demande est alors prise en charge par un rédacteur. Le service encaissement reçoit le règlement de l’assuré. Un assuré peut signaler ultérieurement, (au rédacteur) toute modification dans son statut (adresse, voiture, etc) Quand un accident survient, l’assuré le déclare auprès du secrétariat, lequel construit le dossier sinistre et le transmet à un inspecteur Si le dossier est grave, l’inspecteur se contente de le transmettre au siège, sinon, il charge un expert de la mission d’instruction du dossier L’expert transmet alors son rapport, et l’inspecteur entame les négociations avec la compagnie adverse Il transmet l’information au rédacteur pour la mise à jour du bonus-malus Le rédacteur demande la situation de l’assuré au service encaissement; À l’échéance, le rédacteur informe le service quittancement, le service envoie un avis à 105 l’assuré, lequel envoie son règlement et reçoit ensuite une quittance. Flux de données Découpage en domaines à l’aide des flux 106 23  10/10/2023 Flux de données Modèle de Conceptuel de Communication  Le MCC permet de compléter le diagramme de contexte (les flux d'informations entre l'organisation et les acteurs externes) en décomposant l'organisation en une série d'acteurs internes. Dans ce diagramme la représentation standard est la suivante: Les acteurs internes sont représentés par des ellipses les messages internes sont représentés par des flèches Acteur Référentiel interne 107 Flux de données Modèle de Conceptuel de traitements  Le MCT représente les activités du domaine d’étude en le décomposant les opérations en tâches et en décrivant son comportement suite à un évènement interne ou externe (Quoi faire)  Il modélise la dynamique du système en toute indépendance de considérations techniques et/ou organisationnelles.  Ressources à mettre en œuvre: Moyens techniques, humains, espace, temps, données  Ensemble homogène d’activités élémentaires, résultant de la décomposition d’une opération conceptuelle suivant un enchaînement chronologique 108 24  10/10/2023 Flux de données Fonctionnement du SI  Il est décrit par l’enchaînement d’opérations, déclenchées selon certaines conditions de synchronisation (et, ou, …), par des événements contributifs (internes ou externes), et produisant d’autres événements résultants (internes ou externes). Exemple 109 Flux de données Représentation générale 110 25  10/10/2023 Flux de données Opération  C’est une séquence continue d’actions non interruptible.  Déclenchée par un ou plusieurs événements internes ou externes.  Produit des événements résultats internes ou externes, conditionnés par des règles d’émission.  Les actions sont constituées : des traitements appliqués aux données en entrée selon certaines règles, des tâches de consultation et de mise à jour d’une base d’informations (base de données) implicitement accessible. 111 Flux de données TACHE Description d’une tâche : Actions effectuées sur les données mémorisées ; Sous schéma conceptuel/organisationnel des données  Création, Modification, Lecture, suppression  Règles de traitements ;  Conditions de production des résultats et/ou états ; Durée, Périodicité de la tâche ; 112 26  10/10/2023 Flux de données Condition d’émission des résultats  Une opération peut comporter plusieurs messages en sortie ou résultat  Le résultat de l’opération dépend de certaines conditions (suivant les informations du message reçu, mémorisées ou d ’une règle humaine non formalisée)  Ces conditions peuvent être traduites par des expressions logiques  Plusieurs résultats de nature et destination différentes peuvent être émis par une même condition  La présence d ’une condition (un test) dans le déroulement d ’activités consécutives à un ou plusieurs événements ne justifie pas, au niveau conceptuel, la segmentation en différentes opérations. 113 Flux de données Règle d’émission et anomalies Si A est négatif, il y a deux possibilités Pas de sortie prévue si A est négatif => Ambiguïté ! => Impasse ! 75 114 27  10/10/2023 Flux de données Synchronisation  Elle représente une pré-condition pour l’activation d’une opération à partir de plusieurs événements, permet le découpage d’un processus en plusieurs opérations, est spécifiée par: le nom des événements un prédicat qui précise leur participation  Si la condition est vérifiée, l’opération peut démarrer et les occurrences «déclencheuses» (et les messages associés) sont consommées par l’opération  Si la condition n’est pas vérifiée, la synchronisation et les occurrences d’événements présents restent en attente jusqu’à ce qu’elle soit vérifiée 115 Flux de données Typesd’événement  Evénements externes : proviennent de l’univers extérieur, sont traités par une opération conceptuelle (ex: arrivée d’un flux d’entrée, date de déclenchement), C’est un stimulus pour le SI qui provoque une réaction. Il doit être détectable par le SI. C’est un message c’est à dire un ensemble de données qui sont associés au fait nouveau.  Evénements internes: générés par une opération conceptuelle, contribuent au déclenchement d’une autre opération (état intermédiaire du SI ou état d’attente),  Evénements résultants : générés par une opération conceptuelle et destinés à l’univers extérieur (résultats externes) ou à d’autres opérations (résultats internes). 70 116 28  10/10/2023 Flux de données Construction du MCT LISTE DES ACTEURS ET DES FLUX GRAPHE DES FLUX LISTE DES EVENEMENTS REGLES DE GESTION EN ENTREE ET EN SORTIE MODELE CONCEPTUEL DES TRAITEMENTS 77 117 Flux de données 118 29  10/10/2023 Flux de données Modèle Organisationnel des Traitements (MOT) Ajouter la notion de temps et types d’opération Temps Extérieur Poste_1 Poste_2 Poste_3 Evt_1 Evt_2 Evt_6 Evt_7 Evt_9 Evt_10 Oper_2 Oper_1 Oper_3 Evt_5 Evt_8 Evt_12 Evt_4 Evt_3 Evt_11 119 Flux de données Le modèle Organisationnel Graphe qui modélise les flux en termes de site (le où?) et de poste de travail (le qui?) Montre les flux d’informations entre partenaires, sites et acteurs internes pour un domaine donné ou une activité donnée Éléments du modèle: Les partenaires ou acteur externe Les sites: lieu géographique dans lequel un epartie de l’activité est faite. Les acteurs internes/les activités Les messages qui circulent entres eux : devis, devis signé, bon de commande, facteur,… 120 30  10/10/2023 Flux de données Représentation 121 Machines à états finis Machine d’états  Simulation d'une machine très simple : mémorisation d'un état programme sous forme de graphe étiqueté indiquant les transitions possibles  Cette machine lit un mot en entrée.  Ce mot décrit une suite d'actions et progresse d'état en état jusqu'à la lecture complète du mot.  Lorsque le dernier état est distingué (état final) on dit que le mot est accepté.  Un automate permet de reconnaître un langage. 122 31  10/10/2023 Machines à états finis Automates finis déterministes ► Un automate déterministe fini a b c a b a a … est le quintuplet "fait" M = (Q, , , s, F) où : tête de lecture  Q : ensemble fini (non vide) d'états   : alphabet (ensemble non vide de q1 lettres) contrôle q0 q2   : fonction de transition : Q    fini … q3 Q (q, ) = q' (q' : état de l'automate après avoir lu la lettre  dans l'état q)  Un état dépend uniquement  s : état initial : s  Q  De l’état précédent  F : ensemble des états finaux : F  Q  Du symbole lu 123 Machines à états finis Automates finis déterministes  Exécution a b c a b a a … La machine lit a (qui est ensuite oublié), passe dans l'état 1(s, a) et avance la tête de lecture, répète cette étape jusqu'à ce que tout le mot soit lu.  La partie déjà lue du mot ne peut pas influencer le comportement à venir de l'automate. (d'où la notion de configuration)  Configuration: état dans lequel est l'automate mot qui lui reste à lire (partie droite du mot initial)  Formellement : une configuration est un élément quelconque de 𝑄 ×  ∗.  Exemple: sur l'exemple précédent, la configuration est (q2, cabaa). 124 32  10/10/2023 Machines à états finis Automates finis déterministes  Le fonctionnement d'un automate est décrit par le passage d'une configuration à une autre, cette dernière obtenue en lisant un caractère, et en appliquant la fonction de transition. Exemple (q2, cabaa)  (q3, abaa) si (q2, c) = q3  Un automate M détermine une relation binaire entre configurations qu'on note ├M définie par : ├M  (Q  *)2 (q, w) ├M (q', w') ssi  a   tel que w = aw' et (q, a) = q’  On dit alors que on passe de (q, w) à (q', w') en une étape. 125 Machines à états finis Automates finis déterministes  On note ├M* la fermeture transitive réflexive de ├M : (q, w) ├M* (q', w’) signifie qu'on passe de (q, w) à (q', w') en zéro, une ou plusieurs étapes  Un mot w est accepté par M ssi (s, w) ├M * (q, e), avec q  F.  Le langage accepté par M est l'ensemble de tous les mots acceptés par M.  Ce langage est noté L(M). 126 33  10/10/2023 Automates finis déterministes  Exemple M = (Q, , , s, F) – Q = {q0, q1}  q  (q, ) a b : q0 q0 q1 –  = {a, b} q0 a q0 q1 q1 q0 – s = q0 q b q1 – F = {q0} 0 a q b  1 q q 1 1 q 0 final a a start b b q0 q1 127 Automates finis non déterministes  Idée : remplacer la fonction ├M (ou ) par une relation.  Une relation est beaucoup plus général qu’une fonction. on a ainsi une classe plus large d’automates. Dans un état donné, on pourra avoir : a ou (pas de a-transition) a 128 34  10/10/2023 Machines à états finis Automates finis non déterministes  L = (ab  aba)* Automate déterministe : a a b a q0 q1 q2 b q3 b a b q4 a, b a q1 b Automate non déterministe : q0 b a q2 129 Machines à états finis Automates finis non déterministes  Dans le cas de l’automate non déterministe, un mot est accepté s’il existe un ou plusieurs chemins (au moins un) pour aller de l’état initial (ici q0) à l’état final (ici q0).  Autre différence par rapport aux automates déterministes : Il est possible d’étiqueter une flèche par le symbole e.  Autre formulation (encore plus intuitive) de l’automate précédent a q1 q0 e b a q2 130 35  10/10/2023 Machines à états finis Automates finis non déterministes Un automate non déterministe fini est le quintuplet M = (Q, , , s, F) où :  Q : ensemble fini (non vide) d'états   : alphabet (ensemble non vide de lettres)   : relation de transition : Q (  {e})  Q (q, , p)   : -transition (  )  s : état initial : s  Q  F : ensemble des états finaux : F  Q (hormis la relation, le reste est identique à la formulation déterministe) 131 131 Machines à états finis Automates finis non déterministes  Si (q, e, p)   : on a une -transition (transition spontanée)  On passe de q à p sans lire de symbole dans le mot courant.  ├M est une relation et non plus une fonction (automates déterministes) : (q, e) peut être en relation avec une autre configuration (après une -transition) pour une configuration (q, w), il peut y avoir plusieurs configurations (q’, w’) (ou aucune) tq (q, w) ├M (q’, w’) 132 132 132 36  10/10/2023 Machines à états finis Classification des langages 133 133 133 Machines à états finis Exemples Moutons et berger Addition de deux binaire de longueur non bornée 134 134 134 37