Création d'un ou exclusif de deux finis déterministes Automatons (déterministes Machines à états finis)

Question

Deux DFA (déterministes Finite Automaton ou déterministes Machines Fininte-État - qui sera appelé DFA à partir d'ici) définies sur l'ensemble DFA 1: L1 = {Q1, E, D1, s1, F} DFA2: L2 = {Q2, E, D2, s2, F}

Q est la liste des états. Ex 1, 2, 3, 4 ou a, b, c, d

E est la langue Ex. 0, 1

D est l'ensemble de transition Ex. {(A, 0, b)} un Etat va à b sur 0

s est l'état de départ

F est l'état final

Comment prendriez-vous et exclusif ou de deux DFA L1 et L2

Answer 1

Q = Q1 X Q2;

E = E; D est l'ensemble des transitions qui correspondent aux deux systèmes;

s = S1 croisent S2;

F = F1 XOR F2

Answer 2

Voici quelques conseils généraux pour vous aider à démarrer ...

vous aurez probablement envie de construire un autre DFA dont les états Q3 sont identifiés avec éléments du produit cartésien de Q1 et Q2. De s1 et s2, il devrait être assez évident quel élément de Q3 devrait être désigné comme l'état de départ.
Ensuite, étant donné un nœud (n1 dans Q1, n2 dans Q2) dans Q3, il devrait être assez facile à comprendre où les bords doivent aller pour chaque entrée. Et F3 sera un ensemble d'états (n1, n2) où (n1 dans F1 XOR n2 dans F2) tient.