1

I have 2 DFA's, the transitions of which look as follows:

DFA1 
{('q0', 'a'): 'q1', ...}

DFA2
{('q0', 'a'): 'q3',...}

As I understand, the delta of the unified DFA is supposed to look something like this:

{(('q0', 'a'): 'q1'), (('q0', 'a'): 'q3')),...and so on}

How can I merge these 2 dictionaries to create the tuples for the unified delta dictionary?

if I do DFA2.update(DFA1), the result is {('q0', 'a'): 'q1'}. Why doesn't this work and how do I make it work?

nanachan
  • 1,051
  • 1
  • 15
  • 26
  • What's this notation: `(('q0', 'a'): 'q1')`? And is the "delta" simply all keys whose values are different in the 2 dictionaries? – slider Nov 21 '18 at 18:30
  • 'q0' is the start state, 'a' is the character on the arc, 'q1' is the state that 'q0' transitions to if 'a' is seen. – nanachan Nov 21 '18 at 18:32
  • When DFA's are closed under union, the states of DFA1 and DFA2 make up tuples (product), i.e. (state1 of DFA1, state1 of DFA2), (state2 of DFA1, state2 of DFA2) and so forth. Delta is the transition function from state to state in a DFA. The union of DFA1 and DFA2 will have its delta as tuples such as (transition1 of DFA1, transition1 of DFA2) and so forth. – nanachan Nov 21 '18 at 18:37
  • I simplified the question. The problem I am having is updating the transition dictionaries. – nanachan Nov 21 '18 at 19:07

1 Answers1

0

I will suggest you to represent a DFA transition as a set of tuples instead of a key-value pair of dictionary. It's good as you will work on set operation in many algorithms related to DFA.

Example:

t1 = {('q0', 'a', 'q1'), ('q1', 'a', 'q2'), ...}
t2 = {('q0', 'a', 'q2'), ('q1', 'b', 'q2'), ...}

By t1.union(t2), you will get:

{('q0', 'a', 'q1'), ('q0', 'a', 'q2'), ('q1', 'a', 'q2'), ('q1', 'b', 'q2'), ...}

However if you insist to use dictionary, then you can refer to this thread.

ipramusinto
  • 2,310
  • 2
  • 14
  • 24