8
\$\begingroup\$

Convert NFA to DFA as quickly as possible.

Input

Your input will be an NFA. In order to be able to test your code, it needs to be able to handle an NFA in the following format. This is taken directly from GAP (and slightly simplified).

Automaton( Type, Size, Alphabet, TransitionTable, Initial, Accepting )

For the input, Type will always be "nondet". Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are lists of non-negative integers not greater than the size of the automaton are also allowed. Initial and Accepting are, respectively, the lists of initial and accepting states.

Example input:

Automaton("nondet", 4, 2, [[[], [2], [3], [1, 2, 3, 4], [2, 4]],
                                [[], [1, 3, 4], [1], [2, 4]]], [1], [2, 3])

This is slightly easier to read as a transition table.

   |  1    2             3                4
--------------------------------------------------
 a |      [ 2 ]         [ 1, 2, 3, 4 ]   [ 2, 4 ]   
 b |      [ 1, 3, 4 ]   [ 1 ]            [ 2, 4 ]   
Initial state:    [ 1 ]
Accepting states: [ 2, 3 ]

Output

Your output must be a DFA that is equivalent to the input NFA. There is no need for your DFA to be minimal. For the output, Type will always be "det". Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are non-negative integers not greater than the size of the automaton. The states should be labelled by consecutive integers. Initial and Accepting are, respectively, the lists of initial and accepting states. In the case of the example above, this would be:

Automaton("det", 2, 2, [[2, 2], [2, 2]], [1], [])

As a transition table this is:

   |  1  2  
-----------
 a |  2  2  
 b |  2  2  
Initial state:   [ 1 ]
Accepting state: [  ]

(It is now clear this is a DFA that will not accept any input strings.)

Test cases:

  1. Input:
Automaton("nondet",2,4,[[[1], [2]], [[2], []], [[2], []] , [[1], [2]]],[1],[1, 2])

As a transition matrix:

   |  1       2
-------------------
 a | [ 1 ]   [ 2 ]   
 b | [ 2 ]           
 c | [ 2 ]           
 d | [ 1 ]   [ 2 ]   
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]

Here is the diagram of the NFA.

enter image description here

Output:

Automaton("det",3, 4,[[1, 2, 3], [2, 3, 3], [2, 3, 3], [1, 2, 3]], [1],[1, 2])

As a transition matrix:

   |  1  2  3  
--------------
 a |  1  2  3  
 b |  2  3  3  
 c |  2  3  3  
 d |  1  2  3  
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]

Here is the diagram of the DFA.

enter image description here

  1. Input:
Automaton("nondet",7,4,[[[1, 3, 4, 5], [2], [3], [3, 4], [3, 5], [], []], [[2, 3, 4, 7], [3], [], [], [3, 7], [3, 4], []], [[2, 3, 5, 6], [3], [], [3, 6], [], [], [3, 5]], [[1, 3, 6, 7], [2], [3], [], [], [3, 6], [3, 7]]],[1],[1, 2, 3, 4, 5, 6, 7])

Output:

Automaton("det",16,4,[[1, 2, 15, 15, 5, 6, 7, 7, 6, 2, 16, 12, 12, 16, 15, 16], [1, 3, 1, 7, 9, 15, 1, 1, 15, 8, 7, 3, 8, 15, 1, 15], [1, 1, 2, 1, 13, 4, 4, 10, 10, 1, 15, 15, 15, 2, 1, 15], [1, 15, 3, 4, 5, 16, 15, 3, 14, 4, 11, 16, 11, 14, 15, 16]],[5],[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16])
  1. Input:
Automaton("nondet",12, 4,[[[1, 3, 5, 6], [2, 4, 7, 8], [3], [6], [3, 5], [3, 6], [4, 7], [4, 8], [4, 7], [4, 8], [], []], [[2, 3, 5, 10], [3, 4, 7, 12], [6], [], [4, 7], [3, 10], [], [4, 12], [3, 5], [4, 12], [4, 7], []], [[2, 3, 6, 9], [3, 4, 8, 11], [6], [], [3, 9], [4, 8], [4, 11], [], [4, 11], [3, 6], [], [4, 8 ]], [[1, 3, 9, 10], [2, 4, 11, 12], [3], [6], [4, 11], [4, 12], [], [], [3, 9], [3, 10], [4, 11], [4, 12]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])

Output:

Automaton("det",39,4,[ [ 1, 19, 8, 5, 10, 10, 9, 25, 10, 10, 25, 10, 13, 35, 15, 20, 15, 19, 19, 21, 21, 10, 13, 19, 25, 25, 25, 36, 35, 10, 35, 35, 10, 10, 35, 36, 25, 19, 25 ], [ 1, 23, 1, 3, 6, 39, 39, 7, 39, 12, 8, 12, 32, 23, 21, 36, 16, 36, 32, 36, 32, 12, 32, 13, 22, 29, 32, 23, 39, 32, 39, 12, 32, 31, 12, 22, 22, 23, 7 ], [ 1, 30, 4, 1, 4, 10, 25, 4, 8, 5, 5, 10, 14, 34, 2, 14, 38, 30, 30, 14, 14, 10, 14, 30, 5, 4, 5, 34, 27, 5, 30, 30, 10, 4, 34, 34, 5, 30, 4 ], [ 1, 2, 39, 8, 39, 12, 7, 3, 25, 37, 37, 12, 27, 28, 15, 18, 15, 19, 19, 19, 19, 6, 33, 2, 11, 26, 27, 28, 22, 27, 12, 12, 33, 26, 37, 37, 37, 24, 39 ] ],[ 17 ],[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39 ])
  1. Input:
Automaton("nondet",25,4,[[[1, 3, 6, 7], [2, 4, 8, 9], [3, 5, 10, 11], [4], [5], [3, 5, 6, 10, 18], [3, 5, 7, 11, 19], [4, 8], [4, 9], [5, 10], [5, 11], [4, 5, 8, 10, 22], [4, 5, 9, 11, 23], [5, 10], [5, 11], [], [], [5, 10, 18], [5, 11, 19], [5, 10, 22], [5, 11, 23], [], [], [], []], [[2, 3, 6, 13], [3, 4, 8, 15], [4, 5, 10, 17], [5], [], [4, 5, 8, 10, 18], [3, 5, 13, 17, 21], [5, 10], [4, 15], [], [5, 17], [3, 5, 6, 10, 22], [4, 5, 15, 17, 25], [4, 8], [5, 17], [5, 10], [], [], [5, 17, 21], [], [5, 17, 25], [5, 10, 18], [], [5, 10, 22], []], [[2, 3, 7, 12], [3, 4, 9, 14], [4, 5, 11, 16], [5], [], [3, 5, 12, 16, 20], [4, 5, 9, 11, 19], [4, 14], [5, 11], [5, 16], [], [4, 5, 14, 16, 24], [3, 5, 7, 11, 23], [5, 16], [4, 9], [], [5, 11], [5, 16, 20], [], [5, 16, 24], [], [], [5, 11, 19], [], [5, 11, 23]], [[1, 3, 12, 13], [2, 4, 14, 15], [3, 5, 16, 17], [4], [5], [4, 5, 14, 16, 20], [4, 5, 15, 17, 21], [5, 16], [5, 17], [], [], [3, 5, 12, 16, 24], [3, 5, 13, 17, 25], [4, 14], [4, 15], [5, 16], [5, 17], [], [], [], [], [5, 16, 20], [5, 17, 21], [5, 16, 24], [5, 17, 25]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 ])
  1. Input:
Automaton("nondet",38,4,[[[1, 3, 7, 8], [2, 4, 9, 10], [3, 5, 11, 12], [4, 6, 13, 14], [7], [8], [3, 5, 7, 11, 23], [3, 5, 8, 12, 24], [4, 6, 9, 13, 25], [4, 6, 10, 14, 26], [5, 11], [5, 12], [6, 13], [6, 14], [4, 5, 9, 11, 31], [4, 5, 10, 12, 32], [5, 6, 11, 13, 33], [5, 6, 12, 14, 34], [6, 13], [6, 14], [], [], [5, 11, 23], [5, 12, 24], [6, 13, 25], [6, 14, 26], [5, 11, 31], [5, 12, 32], [6, 13, 33], [6, 14, 34], [6, 13, 25], [6, 14, 26], [], [], [6, 13, 33], [6, 14, 34], [], []], [[2, 3, 7, 16], [3, 4, 9, 18], [4, 5, 11, 20], [5, 6, 13, 22], [8], [], [4, 5, 9, 11, 23], [3, 5, 16, 20, 28], [5, 6, 11, 13, 25], [4, 6, 18, 22, 30], [6, 13], [5, 20], [], [6, 22], [3, 5, 7, 11, 31], [4, 5, 18, 20, 36], [4, 6, 9, 13, 33], [5, 6, 20, 22, 38], [5, 11], [6, 22], [6, 13], [], [6, 13, 25], [5, 20, 28], [], [6, 22, 30], [6, 13, 33], [5, 20, 36], [], [6, 22, 38], [5, 11, 23], [6, 22, 30], [6, 13, 25], [], [5, 11, 31], [6, 22, 38], [6, 13, 33], []], [[2, 3, 8, 15], [3, 4, 10, 17], [4, 5, 12, 19], [5, 6, 14, 21], [8], [], [3, 5, 15, 19, 27], [4, 5, 10, 12, 24], [4, 6, 17, 21, 29], [5, 6, 12, 14, 26], [5, 19], [6, 14], [6, 21], [], [4, 5, 17, 19, 35], [3, 5, 8, 12, 32], [5, 6, 19, 21, 37], [4, 6, 10, 14, 34], [6, 21], [5, 12], [], [6, 14], [5, 19, 27], [6, 14, 26], [6, 21, 29], [], [5, 19, 35], [6, 14, 34], [6, 21, 37], [], [6, 21, 29], [5, 12, 24], [], [6, 14, 26 ], [6, 21, 37], [5, 12, 32], [], [6, 14, 34]], [[1, 3, 15, 16], [2, 4, 17, 18], [3, 5, 19, 20], [4, 6, 21, 22], [7], [8], [ 4, 5, 17, 19, 27], [4, 5, 18, 20, 28], [5, 6, 19, 21, 29], [5, 6, 20, 22, 30], [6, 21], [6, 22], [], [], [3, 5, 15, 19, 35], [3, 5, 16, 20, 36], [4, 6, 17, 21, 37], [4, 6, 18, 22, 38], [5, 19], [5, 20], [6, 21], [6, 22], [6, 21, 29], [6, 22, 30], [], [], [6, 21, 37], [6, 22, 38], [], [], [5, 19, 27], [5, 20, 28], [6, 21, 29], [6, 22, 30], [5, 19, 35], [5, 20, 36], [6, 21, 37], [6, 22, 38]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38])
  1. Input:
Automaton("nondet",67,4,[[[1, 3, 8, 9], [2, 4, 10, 11], [3, 5, 12, 13], [4, 6, 14, 15], [5, 7, 16, 17], [8], [8], [3, 5, 8, 12, 28], [3, 5, 9, 13, 29], [4, 6, 10, 14, 30], [4, 6, 11, 15, 31], [5, 7, 12, 16, 32], [5, 7, 13, 17, 33], [6, 14], [6, 15], [ 7, 16], [7, 17], [4, 5, 10, 12, 40], [4, 5, 11, 13, 41], [5, 6, 12, 14, 42], [5, 6, 13, 15, 43], [6, 7, 14, 16, 44], [6, 7, 15, 17, 45], [7, 16], [7, 17], [], [], [5, 7, 12, 16, 28, 32, 52], [5, 7, 13, 17, 29, 33, 53], [6, 14, 30], [6, 15, 31], [7, 16, 32], [7, 17, 33], [5, 7, 12, 16, 40, 44, 56], [5, 7, 13, 17, 41, 45, 57], [6, 14, 42], [6, 15, 43], [7, 16, 44], [7, 17, 45], [6, 7, 14, 16, 30, 32, 60], [6, 7, 15, 17, 31, 33, 61], [7, 16, 32], [7, 17, 33], [], [], [6, 7, 14, 16, 42, 44, 64], [6, 7, 15, 17, 43, 45, 65], [7, 16, 44], [7, 17, 45], [], [], [7, 16, 32, 52], [7, 17, 33, 53], [7, 16, 44, 56], [7, 17, 45, 57], [7, 16, 32, 60], [7, 17, 33, 61], [7, 16, 44, 64], [7, 17, 45, 65], [], [], [], [], [], [], [], []], [[2, 3, 8, 19], [3, 4, 10, 21], [4, 5, 12, 23], [5, 6, 14, 25], [6, 7, 16, 27], [8], [], [4, 5, 10, 12, 28], [3, 5, 19, 23, 35], [5, 6, 12, 14, 30], [4, 6, 21, 25, 37], [6, 7, 14, 16, 32], [5, 7, 23, 27, 39], [7, 16], [6, 25], [], [7, 27], [3, 5, 8, 12, 40], [4, 5, 21, 23, 47], [4, 6, 10, 14, 42], [5, 6, 23, 25, 49], [5, 7, 12, 16, 44], [6, 7, 25, 27, 51], [6, 14], [7, 27], [7, 16], [], [6, 7, 14, 16, 30, 32, 52], [5, 7, 23, 27, 35, 39, 55], [7, 16, 32], [6, 25, 37], [], [7, 27, 39], [6, 7, 14, 16, 42, 44, 56], [5, 7, 23, 27, 47, 51, 59], [7, 16, 44], [6, 25, 49], [], [7, 27, 51], [5, 7, 12, 16, 28, 32, 60], [6, 7, 25, 27, 37, 39, 63], [6, 14, 30], [7, 27, 39], [7, 16, 32], [], [5, 7, 12, 16, 40, 44, 64], [6, 7, 25, 27, 49, 51, 67], [6, 14, 42], [7, 27, 51], [7, 16, 44], [], [], [7, 27, 39, 55], [], [7, 27, 51, 59], [], [7, 27, 39, 63], [], [7, 27, 51, 67], [7, 16, 32, 52], [], [7, 16, 44, 56], [], [7, 16, 32, 60], [], [7, 16, 44, 64], []], [[2, 3, 9, 18], [3, 4, 11, 20], [4, 5, 13, 22], [5, 6, 15, 24], [6, 7, 17, 26], [8], [], [3, 5, 18, 22, 34], [4, 5, 11, 13, 29], [4, 6, 20, 24, 36], [5, 6, 13, 15, 31], [5, 7, 22, 26, 38], [6, 7, 15, 17, 33], [6, 24], [7, 17], [7, 26 ], [], [4, 5, 20, 22, 46], [3, 5, 9, 13, 41], [5, 6, 22, 24, 48], [4, 6, 11, 15, 43], [6, 7, 24, 26, 50], [5, 7, 13, 17, 45], [7, 26], [6, 15], [], [7, 17], [5, 7, 22, 26, 34, 38, 54], [6, 7, 15, 17, 31, 33, 53], [6, 24, 36], [7, 17, 33], [7, 26, 38], [], [ 5, 7, 22, 26, 46, 50, 58], [6, 7, 15, 17, 43, 45, 57], [6, 24, 48], [7, 17, 45], [7, 26, 50], [], [6, 7, 24, 26, 36, 38, 62], [5, 7, 13, 17, 29, 33, 61], [7, 26, 38], [6, 15, 31], [], [7, 17, 33], [6, 7, 24, 26, 48, 50, 66], [5, 7, 13, 17, 41, 45, 65], [7, 26, 50], [6, 15, 43], [], [7, 17, 45], [7, 26, 38, 54], [], [7, 26, 50, 58], [], [7, 26, 38, 62], [], [7, 26, 50, 66], [], [], [7, 17, 33, 53], [], [7, 17, 45, 57], [], [7, 17, 33, 61], [], [7, 17, 45, 65]], [[1, 3, 18, 19], [2, 4, 20, 21], [3, 5, 22, 23 ], [4, 6, 24, 25], [5, 7, 26, 27], [8], [8], [4, 5, 20, 22, 34], [4, 5, 21, 23, 35], [5, 6, 22, 24, 36], [5, 6, 23, 25, 37], [6, 7, 24, 26, 38], [6, 7, 25, 27, 39], [7, 26], [7, 27], [], [], [3, 5, 18, 22, 46], [3, 5, 19, 23, 47], [4, 6, 20, 24, 48], [4, 6, 21, 25, 49], [5, 7, 22, 26, 50], [5, 7, 23, 27, 51], [6, 24], [6, 25], [7, 26], [7, 27], [6, 7, 24, 26, 36, 38, 54], [6, 7, 25, 27, 37, 39, 55], [7, 26, 38], [7, 27, 39], [], [], [6, 7, 24, 26, 48, 50, 58], [6, 7, 25, 27, 49, 51, 59], [7, 26, 50], [7, 27, 51], [], [], [5, 7, 22, 26, 34, 38, 62], [5, 7, 23, 27, 35, 39, 63], [6, 24, 36], [6, 25, 37], [7, 26, 38], [7, 27, 39], [5, 7, 22, 26, 46, 50, 66], [5, 7, 23, 27, 47, 51, 67], [6, 24, 48], [6, 25, 49], [7, 26, 50], [7, 27, 51], [], [], [], [], [], [], [], [], [7, 26, 38, 54], [7, 27, 39, 55], [7, 26, 50, 58], [7, 27, 51, 59], [7, 26, 38, 62], [7, 27, 39, 63], [7, 26, 50, 66], [7, 27, 51, 67]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67])
  1. Input:
Automaton("nondet",96,4,[[[1, 3, 9, 10], [2, 4, 11, 12], [3, 5, 13, 14], [4, 6, 15, 16], [5, 7, 17, 18], [6, 8, 19, 20], [7 ], [8], [3, 5, 9, 13, 33], [3, 5, 10, 14, 34], [4, 6, 11, 15, 35], [4, 6, 12, 16, 36], [5, 7, 13, 17, 37], [5, 7, 14, 18, 38], [6, 8, 15, 19, 39], [6, 8, 16, 20, 40], [7, 17], [7, 18], [8, 19], [8, 20], [4, 5, 11, 13, 49], [4, 5, 12, 14, 50], [5, 6, 13, 15, 51], [5, 6, 14, 16, 52], [6, 7, 15, 17, 53], [6, 7, 16, 18, 54], [7, 8, 17, 19, 55], [7, 8, 18, 20, 56], [8, 19], [8, 20], [], [], [5, 7, 13, 17, 33, 37, 65], [5, 7, 14, 18, 34, 38, 66], [6, 8, 15, 19, 35, 39, 67], [6, 8, 16, 20, 36, 40, 68], [7, 17, 37], [7, 18, 38], [8, 19, 39], [8, 20, 40], [5, 7, 13, 17, 49, 53, 73], [5, 7, 14, 18, 50, 54, 74], [6, 8, 15, 19, 51, 55, 75], [6, 8, 16, 20, 52, 56, 76], [7, 17, 53], [7, 18, 54], [8, 19, 55], [8, 20, 56], [6, 7, 15, 17, 35, 37, 81], [6, 7, 16, 18, 36, 38, 82], [7, 8, 17, 19, 37, 39, 83], [7, 8, 18, 20, 38, 40, 84], [8, 19, 39], [8, 20, 40], [], [], [6, 7, 15, 17, 51, 53, 89], [6, 7, 16, 18, 52, 54, 90], [7, 8, 17, 19, 53, 55, 91], [7, 8, 18, 20, 54, 56, 92], [8, 19, 55], [8, 20, 56], [], [], [7, 17, 37, 65], [7, 18, 38, 66 ], [8, 19, 39, 67], [8, 20, 40, 68], [7, 17, 53, 73], [7, 18, 54, 74], [8, 19, 55, 75], [8, 20, 56, 76], [7, 17, 37, 81], [7, 18, 38, 82], [8, 19, 39, 83], [8, 20, 40, 84], [7, 17, 53, 89], [7, 18, 54, 90], [8, 19, 55, 91], [8, 20, 56, 92], [8, 19, 39, 67], [8, 20, 40, 68], [], [], [8, 19, 55, 75], [8, 20, 56, 76], [], [], [8, 19, 39, 83], [8, 20, 40, 84], [], [], [8, 19, 55, 91], [8, 20, 56, 92], [], []], [[2, 3, 9, 22], [3, 4, 11, 24], [4, 5, 13, 26], [5, 6, 15, 28], [6, 7, 17, 30], [7, 8, 19, 32], [8 ], [], [4, 5, 11, 13, 33], [3, 5, 22, 26, 42], [5, 6, 13, 15, 35], [4, 6, 24, 28, 44], [6, 7, 15, 17, 37], [5, 7, 26, 30, 46], [7, 8, 17, 19, 39], [6, 8, 28, 32, 48], [8, 19], [7, 30], [], [8, 32], [3, 5, 9, 13, 49], [4, 5, 24, 26, 58], [4, 6, 11, 15, 51], [ 5, 6, 26, 28, 60], [5, 7, 13, 17, 53], [6, 7, 28, 30, 62], [6, 8, 15, 19, 55], [7, 8, 30, 32, 64], [7, 17], [8, 32], [8, 19], [], [6, 7, 15, 17, 35, 37, 65], [5, 7, 26, 30, 42, 46, 70], [7, 8, 17, 19, 37, 39, 67], [6, 8, 28, 32, 44, 48, 72], [8, 19, 39], [7, 30, 46], [], [8, 32, 48], [6, 7, 15, 17, 51, 53, 73], [5, 7, 26, 30, 58, 62, 78], [7, 8, 17, 19, 53, 55, 75], [6, 8, 28, 32, 60, 64, 80], [8, 19, 55], [7, 30, 62], [], [8, 32, 64], [5, 7, 13, 17, 33, 37, 81], [6, 7, 28, 30, 44, 46, 86], [6, 8, 15, 19, 35, 39, 83], [7, 8, 30, 32, 46, 48, 88], [7, 17, 37], [8, 32, 48], [8, 19, 39], [], [5, 7, 13, 17, 49, 53, 89], [6, 7, 28, 30, 60, 62, 94], [6, 8, 15, 19, 51, 55, 91], [7, 8, 30, 32, 62, 64, 96], [7, 17, 53], [8, 32, 64], [8, 19, 55], [], [8, 19, 39, 67], [7, 30, 46, 70], [], [8, 32, 48, 72], [8, 19, 55, 75], [7, 30, 62, 78], [], [8, 32, 64, 80], [8, 19, 39, 83], [7, 30, 46, 86], [], [8, 32, 48, 88], [8, 19, 55, 91], [7, 30, 62, 94], [], [8, 32, 64, 96], [7, 17, 37, 65], [8, 32, 48, 72], [8, 19, 39, 67], [], [7, 17, 53, 73], [8, 32, 64, 80], [8, 19, 55, 75], [], [7, 17, 37, 81], [8, 32, 48, 88], [8, 19, 39, 83], [], [7, 17, 53, 89], [8, 32, 64, 96 ], [8, 19, 55, 91], []], [[2, 3, 10, 21], [3, 4, 12, 23], [4, 5, 14, 25], [5, 6, 16, 27], [6, 7, 18, 29], [7, 8, 20, 31], [8], [], [3, 5, 21, 25, 41], [4, 5, 12, 14, 34], [4, 6, 23, 27, 43], [5, 6, 14, 16, 36], [5, 7, 25, 29, 45], [6, 7, 16, 18, 38], [6, 8, 27, 31, 47], [7, 8, 18, 20, 40], [7, 29], [8, 20], [8, 31], [], [4, 5, 23, 25, 57], [3, 5, 10, 14, 50], [5, 6, 25, 27, 59], [ 4, 6, 12, 16, 52], [6, 7, 27, 29, 61], [5, 7, 14, 18, 54], [7, 8, 29, 31, 63], [6, 8, 16, 20, 56], [8, 31], [7, 18], [], [8, 20 ], [5, 7, 25, 29, 41, 45, 69], [6, 7, 16, 18, 36, 38, 66], [6, 8, 27, 31, 43, 47, 71], [7, 8, 18, 20, 38, 40, 68], [7, 29, 45], [8, 20, 40], [8, 31, 47], [], [5, 7, 25, 29, 57, 61, 77], [6, 7, 16, 18, 52, 54, 74], [6, 8, 27, 31, 59, 63, 79], [7, 8, 18, 20, 54, 56, 76], [7, 29, 61], [8, 20, 56], [8, 31, 63], [], [6, 7, 27, 29, 43, 45, 85], [5, 7, 14, 18, 34, 38, 82], [7, 8, 29, 31, 45, 47, 87], [6, 8, 16, 20, 36, 40, 84], [8, 31, 47], [7, 18, 38], [], [8, 20, 40], [6, 7, 27, 29, 59, 61, 93], [5, 7, 14, 18, 50, 54, 90], [7, 8, 29, 31, 61, 63, 95], [6, 8, 16, 20, 52, 56, 92], [8, 31, 63], [7, 18, 54], [], [8, 20, 56], [7, 29, 45, 69], [8, 20, 40, 68], [8, 31, 47, 71], [], [7, 29, 61, 77], [8, 20, 56, 76], [8, 31, 63, 79], [], [7, 29, 45, 85], [8, 20, 40, 84], [8, 31, 47, 87], [], [7, 29, 61, 93], [8, 20, 56, 92], [8, 31, 63, 95], [], [8, 31, 47, 71], [7, 18, 38, 66], [], [8, 20, 40, 68], [8, 31, 63, 79], [7, 18, 54, 74], [], [8, 20, 56, 76], [8, 31, 47, 87], [7, 18, 38, 82], [], [8, 20, 40, 84], [8, 31, 63, 95], [7, 18, 54, 90 ], [], [8, 20, 56, 92]], [[1, 3, 21, 22], [2, 4, 23, 24], [3, 5, 25, 26], [4, 6, 27, 28], [5, 7, 29, 30], [6, 8, 31, 32], [8], [8], [4, 5, 23, 25, 41], [4, 5, 24, 26, 42], [5, 6, 25, 27, 43], [5, 6, 26, 28, 44], [6, 7, 27, 29, 45], [6, 7, 28, 30, 46], [7, 8, 29, 31, 47], [7, 8, 30, 32, 48], [8, 31], [8, 32], [], [], [3, 5, 21, 25, 57], [3, 5, 22, 26, 58], [4, 6, 23, 27, 59], [4, 6, 24, 28, 60], [5, 7, 25, 29, 61], [5, 7, 26, 30, 62], [6, 8, 27, 31, 63], [6, 8, 28, 32, 64], [7, 29], [7, 30], [8, 31], [8, 32], [6, 7, 27, 29, 43, 45, 69], [6, 7, 28, 30, 44, 46, 70], [7, 8, 29, 31, 45, 47, 71], [7, 8, 30, 32, 46, 48, 72], [8, 31, 47], [8, 32, 48], [], [], [6, 7, 27, 29, 59, 61, 77], [6, 7, 28, 30, 60, 62, 78], [7, 8, 29, 31, 61, 63, 79], [7, 8, 30, 32, 62, 64, 80], [8, 31, 63], [8, 32, 64], [], [], [5, 7, 25, 29, 41, 45, 85], [5, 7, 26, 30, 42, 46, 86], [6, 8, 27, 31, 43, 47, 87], [6, 8, 28, 32, 44, 48, 88], [7, 29, 45], [7, 30, 46], [8, 31, 47], [8, 32, 48], [5, 7, 25, 29, 57, 61, 93], [5, 7, 26, 30, 58, 62, 94], [6, 8, 27, 31, 59, 63, 95], [6, 8, 28, 32, 60, 64, 96], [7, 29, 61], [7, 30, 62], [8, 31, 63], [8, 32, 64], [8, 31, 47, 71], [8, 32, 48, 72 ], [], [], [8, 31, 63, 79], [8, 32, 64, 80], [], [], [8, 31, 47, 87], [8, 32, 48, 88], [], [], [8, 31, 63, 95], [8, 32, 64, 96 ], [], [], [7, 29, 45, 69], [7, 30, 46, 70], [8, 31, 47, 71], [8, 32, 48, 72], [7, 29, 61, 77], [7, 30, 62, 78], [8, 31, 63, 79], [8, 32, 64, 80], [7, 29, 45, 85], [7, 30, 46, 86], [8, 31, 47, 87], [8, 32, 48, 88], [7, 29, 61, 93], [7, 30, 62, 94], [8, 31, 63, 95], [8, 32, 64, 96]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96])
  1. The NFAs for 8, 9, 10, 11, 12, 13, 14, 15, 16 are here.The files have names k7nfa, k8nfa etc. As an example, the input for problem 7 is k7nfa. Hopefully the rest of the names are clear. If your code is correct for problem sizes I can test, I am happy to believe it is correct in general.

Score

I will time your code on test cases 1..16 from above of increasing size. For each test \$n\$, the time limit is \$2^n\$ seconds. Your score will be the largest test case your code can process within its time limit. If two answers get to the same size then the one that is fastest on that largest test case wins. The test machine is an Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz. You can use at most 16 of its cores.

A possible solution method

One method for converting NFAs to DFAs is called subset construction. Because our NFAs will not have any \$\epsilon\$-moves it is slightly simpler than usual. Here is an overview of the algorithm:

Start at the initial state

  1. Perform the following for the new DFA state. For each possible input symbol: Apply move to the newly-created state and the input symbol; this will return a set of states. This set of NFA states will be a single state in the DFA.
  2. Each time we generate a new DFA state, we must apply step 1 to it. The process is complete when applying step 1 does not yield any new states.

The accepting states of the DFA are those which contain any of the finish states of the NFA.

How can this be sped up?

There are have been some attempts to parallelize subset construction. E.g.

Other work has focussed on making the data structures as fast as possible, amongst other things.

Testing

I will check your answers (for the smaller cases) using AreEquivAut .

[Thank you to Christian Sievers for the example NFAs.]

Results

  • 16 in \$33812 < 2^{16} = 65536\$ seconds in Rust by Anders Kaseorg.
\$\endgroup\$
  • \$\begingroup\$ Also, how much memory can we use? (I’m already using 6 GB for case 13…) \$\endgroup\$ – Anders Kaseorg Apr 28 at 8:01
  • \$\begingroup\$ @AndersKaseorg Thanks for the problem reports! I have fixed them all except for "it does not believe that for cases 3 through 6" which I am working on. I have fixed 3 and am working on the others. For RAM, I can handle up to 64GB of RAM. \$\endgroup\$ – user9207 Apr 28 at 11:12
  • \$\begingroup\$ @AndersKaseorg I removed most of the dfas as I am not sure what was wrong with them and it doesn't really help to have them. I look forward to testing your code! \$\endgroup\$ – user9207 Apr 28 at 13:15
  • \$\begingroup\$ @AndersKaseorg I don't know why it's proving so difficult to copy and paste. Hopefully fixed now. \$\endgroup\$ – user9207 Apr 28 at 18:42
8
\$\begingroup\$

Rust, score 15 in ≈ 6000 s

Most of my optimization effort has actually gone into memory usage rather than speed, for reasons you can see in this table of results on my system (AMD Ryzen 1800X):

case       time     memory   DFA size
   1     0.00 s      2 MiB          3
   2     0.00 s      2 MiB         18
   3     0.00 s      2 MiB         57
   4     0.00 s      2 MiB        207
   5     0.00 s      2 MiB        318
   6     0.00 s      2 MiB       1201
   7     0.01 s      3 MiB      12230
   8     0.14 s      9 MiB      66324
   9     0.47 s     18 MiB     179766
  10     3.16 s     68 MiB     879932
  11    11.40 s    241 MiB    2385052
  12   100.64 s    886 MiB   10750324
  13   333.82 s   2026 MiB   29158718
  14  1810.72 s   9073 MiB  123222354
  15  6008.30 s  20631 MiB  333765796

Build with cargo build --release and run with target/release/automaton < INPUT.

src/main.rs

use ahash::AHasher;
use hashbrown::hash_map::{HashMap, RawEntryMut};
use mimalloc::MiMalloc;
use nom::bytes::complete::tag;
use nom::character::complete::{char, digit1, multispace0};
use nom::combinator::{map, map_res};
use nom::multi::separated_list0;
use nom::sequence::{delimited, preceded};
use nom::IResult;
use std::collections::VecDeque;
use std::convert::TryInto;
use std::error::Error;
use std::hash::{Hash, Hasher};
use std::io;
use std::mem;
use std::str::FromStr;

#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;

#[derive(Debug)]
struct Automaton<Set> {
    size: u32,
    alphabet: usize,
    transitions: Vec<Vec<Set>>,
    initial: Set,
    accepting: Vec<u32>,
}

fn parse_vec<'a, T>(
    item: impl FnMut(&'a str) -> IResult<&'a str, T>,
    input: &'a str,
) -> IResult<&'a str, Vec<T>> {
    delimited(
        char('['),
        map(
            separated_list0(
                preceded(multispace0, char(',')),
                preceded(multispace0, item),
            ),
            |v| v.into_iter().collect(),
        ),
        preceded(multispace0, char(']')),
    )(input)
}

type Id = u32;
type Node = u128;
const ID_BITS: u32 = mem::size_of::<Id>() as u32 * 8;
const NODE_BITS: u32 = mem::size_of::<Node>() as u32 * 8;
const DEGREE: u32 = NODE_BITS / ID_BITS;

struct Trie {
    size: u32,
    nodes: Vec<Node>,
    ids: HashMap<Id, ()>,
}

fn pack(ids: [Id; DEGREE as usize]) -> Node {
    let mut node = 0;
    for k in 0..DEGREE {
        node |= (ids[k as usize] as Node) << ID_BITS * k;
    }
    node
}

fn unpack(node: Node) -> [Id; DEGREE as usize] {
    let mut ids = [0; DEGREE as usize];
    for k in 0..DEGREE {
        ids[k as usize] = (node >> ID_BITS * k) as Id;
    }
    ids
}

fn node_hash(node: Node) -> u64 {
    let mut hasher = AHasher::default();
    node.hash(&mut hasher);
    hasher.finish()
}

impl Trie {
    fn new(real_size: u32) -> Trie {
        let mut size = NODE_BITS;
        while size < real_size {
            size *= DEGREE;
        }
        let mut trie = Trie {
            size,
            nodes: vec![],
            ids: HashMap::new(),
        };
        let zero_id = trie.node_id(0);
        debug_assert_eq!(zero_id, 0);
        trie
    }

    fn node_id(&mut self, node: Node) -> Id {
        let hash = node_hash(node);
        let nodes = &mut self.nodes;
        match self
            .ids
            .raw_entry_mut()
            .from_hash(hash, |&id| nodes[id as usize] == node)
        {
            RawEntryMut::Occupied(e) => *e.key(),
            RawEntryMut::Vacant(e) => {
                let id: Id = nodes.len().try_into().unwrap();
                nodes.push(node);
                e.insert_with_hasher(hash, id, (), |&id| node_hash(nodes[id as usize]));
                id
            }
        }
    }

    fn vec_id(&mut self, low: u32, high: u32, vec: Vec<u32>) -> Id {
        if vec.is_empty() {
            0
        } else if high - low <= NODE_BITS {
            let mut node: Node = 0;
            for n in vec {
                node |= 1 << n - low;
            }
            self.node_id(node)
        } else {
            let step = (high - low) / DEGREE;
            let mut vecs: [Vec<u32>; DEGREE as usize] = Default::default();
            for n in vec {
                vecs[((n - low) / step) as usize].push(n);
            }
            let mut ids = [0; DEGREE as usize];
            for k in 0..DEGREE {
                ids[k as usize] = self.vec_id(
                    low + k * step,
                    low + (k + 1) * step,
                    mem::take(&mut vecs[k as usize]),
                );
            }
            self.node_id(pack(ids))
        }
    }

    fn parse_set<'a>(&mut self, input: &'a str) -> IResult<&'a str, Id> {
        let (input, vec) = parse_vec(map_res(digit1, u32::from_str), input)?;
        Ok((input, self.vec_id(0, self.size, vec)))
    }

    fn intersects(&self, size: u32, a: Id, b: Id) -> bool {
        if a == 0 || b == 0 {
            false
        } else {
            let a_node = self.nodes[a as usize];
            let b_node = self.nodes[b as usize];
            if size <= NODE_BITS {
                a_node & b_node != 0
            } else {
                let step = size / DEGREE;
                let a_ids = unpack(a_node);
                let b_ids = unpack(b_node);
                (0..DEGREE).any(|k| self.intersects(step, a_ids[k as usize], b_ids[k as usize]))
            }
        }
    }

    fn union(&mut self, size: u32, ids: &mut Vec<Id>) -> Id {
        ids.retain(|&id| id != 0);
        if ids.len() < 2 {
            ids.drain(..).next().unwrap_or(0)
        } else {
            let mut node;
            if size <= NODE_BITS {
                node = 0;
                for id in ids.drain(..) {
                    node |= self.nodes[id as usize];
                }
            } else {
                let step = size / DEGREE;
                let mut vecs: [Vec<Id>; DEGREE as usize] = Default::default();
                for vec in &mut vecs {
                    vec.reserve(ids.len());
                }
                for id in ids.drain(..) {
                    let ids1 = unpack(self.nodes[id as usize]);
                    for k in 0..DEGREE {
                        vecs[k as usize].push(ids1[k as usize]);
                    }
                }
                let mut ids = [0; DEGREE as usize];
                for k in 0..DEGREE {
                    ids[k as usize] = self.union(step, &mut vecs[k as usize]);
                }
                node = pack(ids)
            };
            self.node_id(node)
        }
    }

    fn for_each(&self, low: u32, high: u32, id: Id, f: &mut impl FnMut(u32)) {
        if id != 0 {
            let mut node = self.nodes[id as usize];
            if high - low <= NODE_BITS {
                while node != 0 {
                    let k = node.trailing_zeros();
                    f(low + k);
                    node &= !(1 << k);
                }
            } else {
                let step = (high - low) / DEGREE;
                let ids = unpack(node);
                for k in 0..DEGREE {
                    self.for_each(low + k * step, low + (k + 1) * step, ids[k as usize], f);
                }
            }
        }
    }
}

fn parse_nfa(input: &str) -> IResult<&str, (Trie, Automaton<Id>)> {
    let (input, _) = tag("Automaton")(input)?;
    let (input, _) = preceded(multispace0, char('('))(input)?;
    let (input, _) = preceded(multispace0, tag("\"nondet\""))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, size) = preceded(multispace0, map_res(digit1, u32::from_str))(input)?;
    let mut trie = Trie::new(size);
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, alphabet) = preceded(multispace0, map_res(digit1, usize::from_str))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, transitions) = preceded(multispace0, |input| {
        parse_vec(
            |input| parse_vec(|input| trie.parse_set(input), input),
            input,
        )
    })(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, initial) = preceded(multispace0, |input| trie.parse_set(input))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, accepting) = preceded(multispace0, |input| {
        parse_vec(|input| map_res(digit1, u32::from_str)(input), input)
    })(input)?;
    let (input, _) = preceded(multispace0, char(')'))(input)?;

    Ok((
        input,
        (
            trie,
            Automaton {
                size,
                alphabet,
                transitions,
                initial,
                accepting,
            },
        ),
    ))
}

struct DFABuilder {
    nfa_accepting: Id,
    trie: Trie,
    set_dstate: HashMap<Id, u32>,
    queue: VecDeque<Id>,
    dfa: Automaton<u32>,
}

impl DFABuilder {
    fn visit(&mut self, set: Id) -> u32 {
        let DFABuilder {
            nfa_accepting,
            trie,
            set_dstate,
            queue,
            dfa,
        } = self;
        *set_dstate.entry(set).or_insert_with(|| {
            dfa.size += 1;
            if trie.intersects(trie.size, *nfa_accepting, set) {
                dfa.accepting.push(dfa.size);
            }
            queue.push_back(set);
            dfa.size
        })
    }
}

fn nfa_to_dfa(mut trie: Trie, nfa: Automaton<Id>) -> Automaton<u32> {
    let mut builder = DFABuilder {
        nfa_accepting: trie.vec_id(0, trie.size, nfa.accepting.clone()),
        trie,
        set_dstate: HashMap::new(),
        queue: VecDeque::new(),
        dfa: Automaton {
            size: 0,
            alphabet: nfa.alphabet,
            transitions: vec![vec![]; nfa.alphabet],
            initial: !0,
            accepting: vec![],
        },
    };
    builder.dfa.initial = builder.visit(nfa.initial);

    let mut sets = Vec::new();
    while let Some(set) = builder.queue.pop_front() {
        for (letter, transition) in nfa.transitions.iter().enumerate() {
            builder
                .trie
                .for_each(0, builder.trie.size, set, &mut |nstate| {
                    sets.push(transition[nstate as usize - 1])
                });
            let set1 = builder.trie.union(builder.trie.size, &mut sets);
            debug_assert!(sets.is_empty());
            let dstate = builder.visit(set1);
            builder.dfa.transitions[letter].push(dstate);
        }
    }

    builder.dfa
}

fn main() -> Result<(), Box<dyn Error>> {
    let mut line = String::new();
    io::stdin().read_line(&mut line)?;
    let (rest, (trie, nfa)) =
        delimited(multispace0, parse_nfa, multispace0)(&line).map_err(|e| e.to_owned())?;
    if rest != "" {
        return Err("expected end of input".into());
    }

    let dfa = nfa_to_dfa(trie, nfa);
    println!(
        "Automaton(\"det\", {}, {}, {:?}, [{}], {:?})",
        dfa.size, dfa.alphabet, dfa.transitions, dfa.initial, dfa.accepting
    );

    Ok(())
}

Cargo.toml

[package]
name = "automaton"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[dependencies]
nom = "6.0.0-alpha1"
mimalloc = { version = "0.1.19", default-features = false }
hashbrown = { version = "0.7.2", features = ["raw"] }
ahash = "0.3.3"
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is great. I think it can be parallelised by a factor equal to the number of symbols at least. For each row, I think we can do the operations for each symbol separately. Would that work with your code? (Did you write the code in 2018?) \$\endgroup\$ – user9207 Apr 28 at 13:29
  • \$\begingroup\$ @Anush Parallelizing this is a challenge because there’s so much shared mutable state at every step. edition = 2018 selects the current Rust 2018 edition of Rust. \$\endgroup\$ – Anders Kaseorg Apr 28 at 17:35
  • \$\begingroup\$ I added some links to the question in any case they are helpful. \$\endgroup\$ – user9207 Apr 28 at 19:05
  • 2
    \$\begingroup\$ That’s approaching the size where overflowing the 32-bit Id might be a concern (the Id tends to grow a bit larger than the number of states). It’ll probably be fine as long as you aren’t crazy enough to devise even larger test cases 😛, but I’ve added an overflow check to be safe. \$\endgroup\$ – Anders Kaseorg Apr 29 at 8:25
  • 1
    \$\begingroup\$ @Anush You could try (also node.trailing_zeros()node.trailing_zeros() as u64), but it’d be slower and even more RAM-hungry, and I suspect the program as written is already using nearly all of your 64 GB for case 16. The number of Ids is only 0.4% more than the number of states for case 15, so maaybe the 32-bit Id might be enough for case 17, even if your RAM still isn’t. \$\endgroup\$ – Anders Kaseorg Apr 29 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy