Search code examples
mathfinite-automatastate-machinedfa

Creating an Exclusive Or from two Deterministic Finite Automatons (Deterministic Finite-State Machines)

Two DFAs (Deterministic Finite Automaton or Deterministic Fininte-State Machines - Which will be called DFAs from here on) Defined over the set DFA 1: L1 = {Q1, E, D1, s1, F} DFA 2: L2 = {Q2, E, D2, s2, F}

Q is the list of states. Ex 1, 2, 3, 4 or a, b, c, d

E is the the language Ex. 0, 1

D is the transition set Ex. {(a,0,b)} state a goes to b on a 0

s is the starting state

F is the final state

How would you take and exclusive-or of two DFAs L1 and L2

Solution

  • Q = Q1 X Q2;

    E = E;

    D is all transitions that agree from both systems;

    s = S1 intersect S2;

    F = F1 XOR F2