Annuler
connectez vous
logique en post-bac
- Description de mathématique formelle-termes et relations
- Théorèmes
- Théories logiques
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Espaces vectoriels et Applications linéaires - supérieur
- Un best-of d'exos de probabilités (après le bac)
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre LogiqueTopics traitant de logique [tout]Lister tous les topics de mathématiques
Niveau autre
union et intersection d'automates
Posté par lary19549 (invité)
Bonjour,
Comment effetuer l'union de 2 automates ?
Et qu'en est-t-il pour l'intersection de 2 automates ?
Merci pour vos réponses.
Bonjour à tous
Je vais essayer de faire remonter mes souvenirs lointains de prépa.
lary19549 > pour les deux, l'idée est la même : passer par ce que l'on appelle l'automate produit (si je ne me trompe pas)
Par la suite, je suppose que les deux automates sont déterministes, possède le même alphabet A et pour chacun d'entre eux, que la fonction de transition est définie partout (à partir de n'importe quel état, on peut lire n'importe quel lettre), sinon, on peut toujours rajouter un état puits : ça coûte pas cher et le langage reconnaissable par l'automate reste le même.
Soient donc et
deux tels automates.
On construit alors un nouvel automate qui possède les caractéristiques suivantes :
1) on garde le même alphabet A
2) les états de cet automate sont les couples où
est un
(pour i=1,2).
3) les états initiaux sont les couples où
est un état initial de
(pour i=1,2)
4) les états finals de cet automate seront du type avec
est un état final de
(pour i=1,2). Les caractéristiques de ces états dépendent de ce que l'on veut
i) si on veut construire l'union des deux automates,
est un état final de
ou
est un état final de
(le "ou" est ici inclusif)
ii) si on veut construire l'intersection des deux automates, est un état final de
et
est un état final de
On voit ensuite que cette construction marche bien (il faut le vérifier quand même, mais bon, c'est pas trop méchant)
Kaiser