10
\$\begingroup\$

Two Deterministic Finite Automata or DFAs can be checked to see if they accept same set of strings in polynomial time. See section 3.3 of this for a long list of methods and this SO question/answer for a much shorter list.

Input

Your input will be two DFAs. In order to be able to test your code, I have provided DFAs 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 "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. We may write a 0 to mean that no transition is present. Initial and Accepting are, respectively, the lists of initial and accepting states. You can assume there will be exactly one initial state.

For example:

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

This has transition table:

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

And diagram:

enter image description here

It is equivalent to:

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

which has diagram:

enter image description here

In order to remove parsing as a significant part of this challenge, you are free to perform trivial parsing of the input format before giving it to your code. This means you can delete any part or parts, reorder and change one type of bracket to another before passing the input to your code. For example, the previous example can be given as

3,2,[ [ 1, 3, 1 ], [ 1, 2, 3 ] ],[ 2 ],[ 2, 3 ]

if that helps.

Here is a more complicated example,

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

has diagram:

enter image description here

It is equivalent to:

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

with diagram:

enter image description here

More examples of equivalent DFAs

1.

Automaton("det",18,4,[ [ 2, 2, 6, 10, 2, 6, 7, 16, 14, 10, 18, 14, 7, 14, 15, 16, 7, 18 ], [ 3, 3, 7, 11, 3, 7, 15, 11, 7, 17, 15, 18\
, 18, 7, 15, 17, 15, 15 ], [ 4, 4, 8, 7, 4, 13, 15, 15, 16, 7, 8, 7, 15, 7, 15, 15, 16, 13 ], [ 5, 5, 9, 12, 5, 14, 7, 13, 9, 14, 17, 12, \
13, 14, 15, 7, 17, 7 ] ],[ 1 ],[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18 ])
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 ])
    2.
Automaton("det",50,4,[ [ 2, 2, 9, 13, 17, 9, 13, 17, 9, 24, 28, 30, 13, 33, 36, 30, 17, 9, 13, 9, 13, 39, 30, 24, 25, 44, 42, 28, 24, 30, 47, 39, 33, 50, 36, 36, 42, 46, 39, 25, 24, 42, 43, 44, 36, 46, 47, 42, 25, 50 ], [ 3, 6, 10, 14, 18, 10, 14, 20, 10, 25, 14, 10, 32, 34, 34, 38, 20, 10, 14, 10, 14, 38, 10, 25, 43, 34, 25, 45, 46, 10, 32, 49, 34, 43, 34, 49, 50, 50, 49, 50, 46, 25, 43, 49, 49, 50, 45, 50, 43, 43 ], [ 4, 7, 11, 15, 19, 11, 15, 21, 22, 26, 26, 31, 15, 11, 25, 15, 21, 11, 15, 11, 15, 40, 15, 40, 43, 43, 44, 26, 26, 15, 44, 31, 41, 26, 47, 25, 25, 22, 40, 43, 40, 25, 43, 43, 47, 41, 44, 44, 44, 40 ], [ 5, 8, 12, 16, 5, 12, 16, 8, 23, 27, 29, 12, 23, 35, 37, 16, 8, 12, 16, 12, 16, 41, 23, 42, 25, 40, 27, 27, 29, 23, 48, 45, 37, 49, 35, 42, 37, 48, 42, 40, 41, 42, 43, 25, 45, 37, 27, 48, 49, 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, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 50 ])
Automaton("det",39,4,[ [ 1, 2, 3, 3, 5, 24, 7, 8, 22, 20, 8, 32, 18, 18, 3, 19, 25, 18, 19, 20, 25, 22, 23, 24, 25, 25, 24, 23, 5, 2, 35, 32, 19, 19, 35, 36, 36, 36, 36 ], [ 1, 38, 1, 23, 15, 9, 11, 26, 23, 28, 26, 10, 9, 26, 1, 3, 22, 26, 3, 28, 22, 23, 1, 15, 3, 3, 15, 1, 28, 27, 10, 27, 23, 23, 38, 15, 28, 15, 28 ], [ 1, 5, 1, 1, 1, 4, 12, 6, 6, 31, 31, 37, 37, 30, 5, 5, 29, 37, 3, 21, 4, 21, 4, 4, 4, 29, 30, 29, 1, 5, 29, 37, 5, 3, 29, 3, 3, 2, 2 ], [ 1, 16, 3, 4, 3, 21, 7, 18, 33, 39, 14, 13, 13, 14, 15, 16, 17, 18, 19, 34, 21, 34, 3, 19, 19, 16, 38, 15, 4, 33, 17, 18, 33, 34, 16, 19, 34, 38, 39 ] ],[ 7 ],[ 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 ])

3.

Automaton("det",288,4,[[2, 6, 10, 14, 18, 6, 10, 14, 18, 25, 29, 33, 36, 40, 43, 46, 36, 53, 10, 14, 18, 10, 14, 18, 25, 29, 60, 36, 29, 67, 71, 75, 77, 81, 83, 87, 88, 90, 94, 40, 98, 46, 104, 108, 111, 46, 116, 120, 75, 123, 127, 129, 53, 10, 14, 131, 129, 71, 75, 136, 140, 143, 146, 87, 149, 75, 67, 68, 155, 153, 156, 159, 161, 163, 75, 165, 77, 170, 81, 172, 81, 67, 88, 123, 156, 146, 87, 88, 156, 90, 183, 186, 188, 87, 90, 183, 94, 192, 143, 197, 199, 116, 75, 104, 108, 204, 172, 108, 208, 120, 127, 159, 90, 199, 163, 159, 215, 156, 149, 120, 153, 217, 123, 218, 131, 221, 127, 159, 87, 123, 225, 88, 155, 67, 165, 136, 227, 143, 221, 123, 218, 221, 143, 68, 67, 88, 123, 127, 143, 217, 68, 67, 153, 154, 155, 156, 234, 235, 159, 120, 161, 237, 143, 217, 165, 143, 241, 199, 188, 242, 197, 75, 67, 165, 241, 217, 248, 250, 172, 146, 221, 161, 225, 234, 111, 186, 153, 75, 217, 75, 188, 192, 257, 188, 68, 120, 90, 186, 127, 90, 208, 146, 221, 259, 140, 120, 235, 208, 165, 262, 199, 188, 68, 120, 215, 267, 217, 218, 250, 83, 75, 165, 75, 215, 225, 208, 234, 71, 149, 153, 75, 235, 208, 234, 67, 265, 272, 233, 241, 143, 120, 242, 257, 155, 153, 143, 153, 248, 267, 250, 116, 120, 75, 237, 71, 235, 250, 163, 259, 227, 153, 262, 67, 75, 155, 233, 272, 265, 116, 241, 281, 272, 68, 149, 120, 155, 283, 163, 67, 208, 285, 265, 287, 233, 285, 68, 287, 68], [3, 7, 11, 15, 19, 7, 11, 15, 22, 26, 30, 15, 37, 41, 44, 47, 50, 54, 11, 15, 19, 11, 15, 22, 26, 30, 61, 37, 30, 68, 72, 30, 78, 47, 84, 26, 30, 91, 37, 96, 99, 102, 105, 109, 112, 115, 117, 109, 122, 124, 128, 130, 54, 11, 15, 130, 132, 72, 30, 137, 141, 122, 147, 132, 150, 30, 68, 154, 109, 68, 157, 109, 162, 164, 30, 166, 168, 99, 102, 173, 175, 176, 177, 124, 128, 147, 132, 30, 72, 168, 184, 115, 189, 132, 96, 99, 37, 166, 195, 96, 99, 201, 150, 105, 109, 205, 164, 109, 154, 109, 157, 109, 211, 112, 213, 109, 154, 72, 109, 195, 208, 215, 124, 208, 130, 150, 166, 224, 26, 124, 157, 30, 226, 217, 166, 115, 213, 150, 30, 124, 208, 150, 195, 208, 176, 177, 124, 72, 224, 208, 233, 217, 68, 154, 195, 214, 195, 208, 109, 109, 236, 117, 195, 208, 214, 195, 201, 99, 173, 166, 168, 177, 68, 246, 213, 215, 68, 251, 173, 147, 150, 254, 166, 195, 99, 175, 208, 30, 215, 122, 164, 166, 251, 173, 154, 195, 78, 258, 166, 168, 154, 147, 150, 260, 141, 226, 217, 154, 214, 254, 184, 263, 154, 195, 154, 109, 208, 208, 269, 84, 177, 246, 150, 154, 166, 215, 195, 166, 150, 208, 150, 208, 215, 195, 215, 213, 195, 208, 213, 150, 195, 166, 254, 109, 68, 224, 233, 68, 109, 236, 201, 226, 150, 213, 166, 208, 277, 117, 278, 213, 233, 236, 215, 279, 195, 208, 224, 201, 117, 280, 254, 195, 208, 109, 109, 226, 213, 213, 215, 215, 277, 280, 195, 208, 236, 233, 195, 208], [4, 8, 12, 16, 20, 8, 12, 16, 23, 27, 31, 34, 38, 42, 12, 48, 51, 55, 12, 16, 20, 12, 16, 23, 56, 58, 62, 51, 65, 69, 73, 76, 79, 69, 85, 42, 89, 92, 95, 42, 100, 48, 106, 31, 113, 48, 118, 68, 48, 125, 48, 51, 55, 12, 16, 62, 51, 133, 135, 138, 56, 144, 62, 148, 151, 48, 144, 154, 154, 155, 69, 118, 154, 69, 48, 161, 79, 171, 69, 174, 69, 69, 178, 180, 69, 85, 148, 138, 182, 92, 95, 155, 135, 42, 92, 95, 148, 193, 76, 198, 200, 118, 48, 202, 58, 62, 206, 207, 69, 209, 210, 89, 92, 200, 135, 178, 216, 69, 174, 68, 68, 138, 202, 65, 219, 222, 48, 118, 148, 56, 138, 118, 154, 69, 155, 138, 228, 144, 206, 106, 229, 174, 144, 154, 144, 138, 202, 48, 144, 138, 154, 144, 68, 154, 154, 69, 228, 133, 152, 165, 154, 69, 182, 240, 155, 135, 155, 200, 135, 243, 198, 210, 244, 155, 165, 152, 249, 144, 206, 219, 252, 154, 178, 255, 113, 155, 155, 210, 240, 135, 135, 65, 151, 48, 155, 209, 92, 155, 210, 92, 244, 62, 206, 138, 202, 68, 151, 144, 161, 68, 200, 135, 265, 165, 266, 73, 152, 207, 144, 62, 48, 161, 76, 249, 138, 69, 271, 133, 73, 265, 135, 151, 144, 266, 144, 155, 182, 133, 155, 182, 161, 274, 151, 161, 265, 135, 155, 266, 151, 144, 138, 161, 275, 69, 73, 276, 144, 135, 138, 249, 68, 68, 244, 135, 161, 151, 144, 155, 138, 155, 151, 144, 155, 151, 161, 161, 249, 69, 69, 244, 144, 155, 271, 276, 144, 155, 266, 265], [5, 9, 13, 17, 21, 9, 13, 17, 24, 28, 32, 35, 39, 28, 45, 49, 52, 9, 13, 17, 21, 13, 17, 24, 57, 59, 63, 64, 66, 70, 74, 32, 80, 82, 86, 28, 32, 93, 39, 97, 101, 103, 107, 110, 114, 66, 119, 121, 49, 126, 49, 52, 9, 13, 17, 63, 64, 134, 59, 139, 142, 145, 63, 64, 152, 66, 153, 68, 144, 70, 158, 160, 151, 134, 66, 167, 169, 101, 134, 59, 70, 82, 179, 181, 82, 86, 64, 66, 74, 169, 185, 187, 190, 97, 191, 101, 64, 194, 196, 191, 101, 160, 103, 203, 160, 63, 103, 121, 195, 110, 179, 110, 212, 114, 214, 167, 213, 134, 160, 153, 121, 158, 203, 187, 220, 223, 66, 119, 57, 142, 139, 59, 151, 134, 187, 66, 214, 152, 66, 107, 230, 231, 153, 144, 145, 139, 203, 103, 232, 187, 151, 152, 153, 154, 68, 70, 214, 187, 121, 160, 68, 238, 239, 230, 70, 214, 187, 101, 59, 194, 169, 179, 245, 247, 214, 232, 70, 152, 66, 220, 253, 144, 194, 196, 101, 70, 187, 194, 256, 190, 231, 66, 152, 66, 195, 196, 80, 247, 194, 169, 213, 63, 103, 139, 203, 261, 152, 68, 239, 121, 185, 264, 213, 214, 68, 268, 121, 121, 145, 63, 139, 270, 223, 195, 66, 238, 239, 187, 74, 230, 231, 121, 266, 153, 232, 195, 236, 273, 70, 74, 239, 66, 121, 268, 245, 119, 247, 153, 144, 153, 187, 270, 253, 195, 167, 230, 232, 119, 66, 70, 261, 153, 256, 264, 236, 144, 266, 273, 158, 247, 144, 68, 273, 121, 167, 282, 195, 70, 158, 284, 266, 286, 236, 288, 68, 286, 68, 288]],[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, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288])
Automaton("det",266,4,[[1, 127, 50, 50, 115, 249, 50, 8, 257, 10, 151, 12, 13, 14, 81, 78, 34, 106, 137, 107, 21, 22, 82, 89, 71, 43, 43, 62, 63, 63, 44, 10, 179, 171, 214, 265, 206, 38, 137, 152, 21, 151, 71, 22, 41, 41, 47, 13, 49, 50, 50, 210, 50, 210, 116, 90, 64, 49, 207, 207, 207, 62, 232, 64, 64, 89, 151, 236, 236, 70, 71, 236, 116, 260, 128, 75, 13, 38, 77, 133, 14, 82, 13, 13, 77, 235, 64, 64, 231, 206, 138, 91, 91, 206, 90, 264, 137, 169, 10, 10, 41, 71, 232, 228, 232, 21, 21, 107, 106, 110, 111, 266, 256, 114, 114, 116, 251, 251, 116, 114, 114, 111, 266, 260, 122, 182, 127, 128, 129, 213, 132, 132, 129, 49, 49, 138, 138, 138, 249, 71, 43, 43, 210, 235, 183, 214, 132, 265, 206, 138, 232, 64, 64, 153, 153, 64, 152, 152, 82, 236, 236, 82, 116, 116, 64, 207, 266, 64, 231, 169, 171, 250, 227, 70, 175, 175, 176, 10, 47, 178, 178, 110, 111, 266, 260, 122, 266, 127, 213, 49, 49, 152, 257, 153, 257, 90, 90, 183, 250, 264, 62, 228, 229, 82, 82, 206, 64, 266, 249, 249, 249, 242, 213, 214, 64, 116, 114, 114, 50, 50, 236, 236, 261, 115, 152, 251, 8, 228, 229, 229, 231, 232, 237, 235, 235, 236, 237, 235, 235, 235, 235, 235, 235, 242, 242, 242, 115, 251, 249, 250, 116, 116, 116, 207, 64, 265, 266, 257, 256, 266, 264, 261, 260, 264, 265, 266], [1, 125, 1, 114, 114, 121, 115, 3, 23, 19, 13, 15, 230, 28, 201, 202, 16, 84, 123, 103, 105, 208, 114, 84, 172, 199, 199, 119, 83, 83, 123, 170, 16, 31, 27, 26, 25, 104, 102, 23, 28, 13, 120, 208, 48, 103, 19, 230, 239, 1, 114, 218, 115, 219, 82, 140, 23, 208, 204, 216, 216, 119, 174, 119, 119, 84, 13, 115, 115, 50, 120, 50, 82, 204, 262, 79, 230, 104, 203, 85, 28, 114, 230, 230, 203, 3, 23, 119, 96, 96, 96, 123, 102, 140, 208, 3, 200, 200, 98, 97, 103, 120, 119, 120, 119, 28, 105, 103, 105, 54, 3, 23, 141, 1, 250, 50, 82, 114, 50, 1, 250, 3, 3, 219, 219, 125, 54, 263, 124, 124, 27, 124, 223, 208, 239, 25, 208, 208, 120, 120, 217, 217, 217, 120, 120, 142, 142, 141, 140, 140, 174, 174, 174, 204, 216, 23, 119, 23, 250, 114, 114, 250, 162, 162, 159, 205, 159, 159, 208, 123, 170, 1, 219, 50, 208, 208, 123, 177, 177, 19, 170, 173, 172, 172, 199, 199, 23, 186, 185, 184, 184, 23, 120, 216, 23, 140, 208, 120, 1, 3, 119, 120, 114, 114, 250, 239, 119, 3, 121, 3, 120, 219, 212, 212, 23, 50, 1, 250, 1, 114, 50, 114, 219, 114, 23, 114, 3, 120, 114, 114, 208, 119, 125, 121, 3, 50, 54, 120, 3, 120, 121, 3, 120, 218, 219, 217, 114, 114, 3, 1, 250, 250, 250, 253, 252, 173, 172, 120, 125, 3, 3, 219, 219, 3, 54, 3], [1, 1, 249, 249, 6, 1, 1, 247, 7, 130, 167, 17, 11, 66, 33, 33, 131, 136, 10, 32, 150, 9, 112, 36, 149, 112, 149, 56, 167, 37, 181, 130, 35, 147, 139, 51, 139, 11, 10, 234, 147, 37, 148, 113, 136, 136, 146, 24, 249, 1, 1, 249, 249, 249, 139, 6, 238, 127, 134, 238, 134, 9, 148, 238, 134, 167, 36, 50, 249, 247, 73, 249, 51, 139, 112, 167, 76, 76, 11, 167, 80, 73, 67, 66, 66, 135, 58, 58, 112, 139, 233, 100, 100, 2, 6, 95, 10, 32, 130, 130, 99, 94, 94, 56, 149, 150, 147, 150, 136, 51, 51, 51, 7, 51, 51, 51, 7, 6, 139, 139, 139, 2, 58, 134, 139, 7, 1, 112, 112, 249, 238, 238, 112, 249, 127, 238, 233, 238, 1, 149, 112, 149, 249, 135, 7, 139, 238, 51, 139, 238, 112, 238, 233, 234, 234, 134, 234, 190, 112, 50, 249, 73, 139, 51, 238, 134, 51, 134, 148, 32, 147, 145, 145, 145, 258, 259, 180, 130, 146, 189, 189, 51, 51, 134, 134, 139, 2, 1, 249, 127, 249, 191, 191, 191, 188, 188, 188, 188, 198, 197, 196, 196, 195, 187, 187, 139, 233, 134, 127, 127, 127, 49, 249, 139, 243, 211, 211, 211, 210, 210, 210, 210, 95, 209, 241, 209, 126, 117, 117, 9, 112, 112, 50, 50, 50, 50, 50, 50, 49, 49, 127, 127, 127, 249, 249, 249, 7, 7, 1, 247, 51, 139, 211, 134, 134, 51, 51, 7, 7, 2, 126, 145, 139, 247, 51, 51], [1, 51, 3, 4, 4, 7, 7, 50, 73, 61, 11, 12, 40, 109, 101, 93, 45, 18, 19, 20, 21, 64, 161, 29, 193, 118, 193, 65, 11, 42, 19, 59, 30, 46, 163, 164, 163, 40, 39, 57, 46, 42, 246, 60, 18, 21, 61, 158, 72, 50, 51, 53, 53, 3, 55, 55, 57, 246, 156, 64, 65, 64, 155, 64, 65, 11, 29, 68, 69, 236, 160, 72, 73, 55, 157, 11, 154, 154, 40, 11, 46, 160, 225, 192, 192, 86, 87, 88, 157, 118, 155, 19, 39, 74, 161, 239, 92, 92, 166, 254, 20, 144, 88, 240, 65, 109, 108, 21, 21, 50, 50, 73, 73, 50, 247, 236, 73, 161, 72, 3, 5, 54, 86, 239, 3, 51, 50, 64, 64, 161, 165, 64, 157, 161, 245, 165, 60, 64, 51, 240, 161, 240, 4, 144, 51, 55, 57, 73, 55, 57, 157, 157, 155, 57, 64, 156, 64, 87, 118, 160, 161, 248, 163, 164, 165, 168, 164, 168, 60, 19, 108, 3, 3, 72, 64, 60, 19, 194, 194, 61, 59, 247, 247, 193, 193, 5, 74, 7, 69, 244, 69, 156, 240, 65, 74, 74, 246, 143, 219, 86, 88, 144, 222, 222, 226, 72, 60, 239, 52, 54, 143, 239, 72, 72, 215, 221, 219, 224, 219, 220, 221, 222, 239, 220, 215, 222, 54, 160, 160, 161, 64, 64, 160, 68, 236, 236, 236, 160, 239, 240, 244, 245, 246, 69, 72, 161, 51, 160, 50, 50, 248, 118, 226, 255, 255, 248, 248, 160, 160, 245, 245, 72, 72, 236, 236, 236]],[12],[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, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266])

4.

Automaton("det",9,4,[[1, 1, 2, 3, 1, 1, 2, 5, 2], [1, 1, 2, 8, 2, 2, 1, 6, 2], [1, 1, 2, 7, 2, 1, 2, 2, 2], [1, 1, 2, 9, 1, 1, 1, 1, 1]],[4],[2, 6])
Automaton("det",100,4,[[0, 1, 3, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 34, 36, 37, 40, 41, 42, 43, 44, 45, 46, 47, 48, 52, 53, 54, 55, 56, 57, 58, 59, 60, 62, 63, 64, 65, 66, 68, 69, 71, 72, 73, 78, 79, 81, 84, 85, 86, 90, 93, 94, 95, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 2, 4, 6, 7, 9, 10, 11, 12, 13, 15, 16, 19, 20, 21, 22, 23, 24, 25, 27, 28, 30, 31, 32, 35, 36, 37, 38, 40, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 59, 60, 61, 64, 66, 67, 69, 70, 71, 75, 76, 78, 80, 81, 84, 85, 86, 87, 89, 92, 93, 95, 96, 97, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 15, 17, 19, 20, 22, 23, 26, 28, 29, 30, 32, 34, 35, 38, 40, 41, 45, 47, 49, 50, 53, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 76, 77, 79, 81, 82, 83, 85, 86, 87, 88, 89, 91, 92, 93, 94, 95, 96, 97, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [ 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14, 15, 19, 21, 22, 23, 24, 26, 27, 28, 32, 33, 34, 35, 39, 40, 42, 43, 46, 47, 51, 54, 55, 59, 60, 61, 63, 64, 67, 71, 72, 73, 74, 75, 76, 77, 78, 79, 82, 84, 85, 89, 90, 91, 92, 93, 94, 96, 97, 98, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[39],[1, 2, 5, 8, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 24, 25, 28, 30, 31, 33, 35, 37, 41, 42, 43, 44, 49, 50, 52, 53, 57, 61, 63, 65, 66, 67, 69, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 85, 86, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 100])

5.

A pair of equivalent DFAs

Non-equivalent DFAs


Automaton("det",100,4,[[0, 1, 2, 3, 5, 7, 9, 12, 13, 15, 20, 21, 23, 24, 25, 27, 29, 30, 31, 33, 34, 35, 36, 37, 40, 41, 42, 45, 46, 47, 48, 56, 57, 60, 62, 64, 65, 69, 70, 73, 74, 76, 80, 81, 82, 84, 86, 87, 88, 89, 90, 92, 93, 94, 95, 97, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 9, 11, 12, 13, 16, 19, 20, 21, 22, 23, 24, 25, 26, 27, 30, 36, 37, 38, 39, 40, 42, 47, 49, 52, 53, 54, 59, 60, 61, 62, 63, 64, 65, 68, 69, 71, 72, 75, 76, 78, 81, 82, 84, 86, 87, 88, 89, 90, 91, 92, 95, 96, 97, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 3, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 21, 24, 25, 26, 27, 28, 29, 30, 33, 35, 36, 37, 38, 39, 41, 43, 46, 50, 51, 53, 55, 56, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68, 70, 73, 74, 76, 77, 78, 80, 83, 86, 87, 89, 91, 92, 93, 95, 98, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 6, 8, 13, 14, 15, 17, 19, 21, 22, 23, 25, 27, 28, 29, 30, 31, 32, 35, 36, 37, 40, 42, 46, 47, 48, 50, 51, 53, 54, 56, 58, 60, 61, 63, 64, 65, 66, 68, 70, 71, 72, 74, 75, 76, 79, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 93, 94, 95, 96, 97, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[52],[1, 5, 6, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 23, 24, 25, 26, 27, 28, 29, 30, 32, 34, 35, 36, 37, 39, 40, 41, 42, 44, 46, 47, 49, 51, 52, 53, 54, 55, 60, 61, 62, 66, 67, 70, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 84, 86, 87, 89, 90, 92, 94, 96, 97, 98, 99, 100])
Automaton("det",100,4,[[0, 2, 3, 4, 6, 7, 10, 11, 14, 15, 16, 17, 19, 20, 21, 22, 24, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38, 40, 42, 43, 44, 46, 48, 49, 51, 55, 56, 57, 58, 59, 61, 62, 63, 64, 69, 71, 72, 73, 76, 78, 79, 80, 83, 86, 87, 88, 89, 90, 91, 95, 96, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 17, 18, 19, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 34, 35, 36, 37, 40, 41, 42, 43, 45, 47, 48, 50, 51, 53, 56, 57, 59, 60, 62, 63, 64, 71, 72, 73, 75, 76, 77, 79, 80, 83, 85, 86, 87, 89, 90, 91, 92, 93, 96, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [ 0, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 16, 18, 21, 23, 24, 26, 27, 28, 29, 30, 32, 34, 35, 36, 37, 39, 40, 41, 42, 45, 47, 48, 50, 51, 52, 53, 56, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 75, 76, 78, 79, 80, 82, 84, 85, 86, 89, 90, 93, 94, 97, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 2, 6, 7, 8, 9, 10, 11, 12, 13, 16, 18, 21, 22, 23, 24, 28, 30, 31, 32, 34, 36, 37, 38, 39, 40, 42, 44, 45, 47, 48, 51, 52, 53, 56, 57, 59, 60, 61, 62, 63, 64, 65, 67, 70, 74, 76, 83, 84, 86, 88, 90, 91, 93, 94, 95, 96, 97, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[17],[1, 6, 7, 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 23, 27, 28, 29, 30, 32, 35, 36, 38, 40, 41, 42, 44, 46, 47, 48, 50, 51, 53, 54, 55, 62, 64, 66, 71, 72, 74, 75, 76, 79, 83, 86, 88, 89, 90, 91, 92, 94, 95, 96, 97, 98, 99, 100])
Automaton("det",100,4,[[2, 3, 6, 7, 8, 9, 10, 12, 14, 15, 16, 20, 21, 25, 26, 28, 29, 30, 32, 35, 36, 37, 40, 42, 43, 44, 46, 47, 48, 50, 53, 54, 55, 57, 58, 59, 62, 63, 64, 65, 67, 68, 69, 72, 73, 75, 77, 79, 81, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 4, 5, 8, 13, 14, 15, 17, 18, 19, 20, 22, 23, 29, 30, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 54, 55, 56, 58, 59, 60, 63, 64, 65, 66, 67, 68, 70, 71, 72, 74, 75, 77, 78, 79, 82, 83, 84, 85, 86, 87, 93, 95, 96, 97, 98, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 3, 6, 7, 9, 10, 12, 13, 14, 15, 16, 17, 19, 20, 21, 23, 25, 27, 28, 30, 31, 32, 37, 38, 40, 41, 42, 45, 47, 49, 50, 51, 52, 56, 59, 61, 63, 64, 65, 68, 70, 72, 73, 74, 76, 77, 78, 80, 81, 85, 86, 87, 88, 92, 93, 94, 96, 98, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 20, 21, 22, 23, 24, 26, 27, 28, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 42, 43, 44, 45, 48, 50, 51, 52, 53, 54, 55, 56, 58, 59, 60, 62, 64, 65, 66, 68, 69, 70, 71, 72, 74, 75, 76, 77, 79, 84, 86, 91, 92, 93, 96, 97, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[46],[1, 2, 7, 8, 10, 12, 13, 15, 17, 18, 20, 22, 23, 24, 25, 27, 28, 29, 30, 32, 33, 35, 36, 37, 39, 41, 42, 44, 45, 47, 49, 50, 51, 52, 54, 55, 57, 59, 61, 63, 65, 66, 67, 68, 69, 70, 71, 73, 75, 76, 77, 79, 80, 81, 82, 85, 86, 88, 91, 92, 93, 94, 95, 96, 97, 98])
Automaton("det",100,4,[[0, 1, 4, 5, 7, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 33, 35, 36, 37, 39, 43, 44, 45, 46, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 62, 63, 67, 68, 70, 72, 73, 74, 76, 77, 78, 81, 82, 83, 85, 87, 93, 94, 95, 96, 97, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 3, 4, 5, 8, 10, 12, 15, 16, 17, 18, 19, 20, 21, 27, 29, 30, 31, 32, 34, 35, 36, 39, 40, 42, 45, 46, 47, 49, 50, 51, 52, 55, 58, 59, 60, 61, 62, 63, 64, 66, 67, 70, 71, 72, 73, 74, 75, 77, 79, 80, 81, 82, 83, 84, 86, 87, 88, 89, 92, 94, 96, 98, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 3, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 20, 21, 23, 30, 31, 33, 34, 35, 37, 38, 39, 42, 43, 44, 46, 47, 48, 50, 52, 53, 54, 55, 56, 58, 59, 60, 61, 63, 64, 65, 66, 67, 70, 71, 75, 76, 77, 80, 82, 83, 84, 85, 86, 87, 88, 89, 91, 92, 94, 98, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 3, 4, 7, 8, 9, 10, 11, 12, 14, 16, 17, 18, 19, 20, 21, 22, 24, 26, 27, 28, 29, 31, 33, 34, 35, 37, 38, 40, 41, 43, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 62, 64, 65, 66, 67, 68, 69, 71, 72, 75, 76, 77, 80, 81, 82, 83, 86, 87, 88, 91, 93, 94, 95, 96, 97, 98, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[45],[2, 4, 6, 7, 11, 12, 14, 15, 16, 17, 19, 20, 24, 25, 27, 28, 29, 30, 37, 39, 41, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 67, 71, 72, 76, 81, 82, 83, 84, 85, 86, 87, 88, 91, 92, 94, 95, 99, 100])

Score

This question is and . Your code must be able to run all the test cases in less than a minute on TIO. Your code only needs to output something Truthy or Falsey depending on whether the two DFAs are equivalent or not.

[GAP has a library function for this but I am not aware of any other languages that do. Please feel free to use whatever your language does provide however.]

\$\endgroup\$
  • 1
    \$\begingroup\$ "list of initial states"? There's usually exactly one initial state, and all examples have one initial state. \$\endgroup\$ – aschepler Apr 23 at 22:34
  • \$\begingroup\$ @aschepler Yes . I have added a comment to make it clear you can assume there will be exactly one initial state. \$\endgroup\$ – Anush Apr 24 at 7:46
  • \$\begingroup\$ Wait, it's currently a two-part code golf: (parse the GAP syntax) + (test if the two DFAs are equivalent). I don't think it's a good idea. \$\endgroup\$ – Bubbler Apr 24 at 8:29
  • 2
    \$\begingroup\$ @Bubbler I updated the question to hopefully remove the parsing issue. \$\endgroup\$ – Anush Apr 24 at 11:14
  • 1
    \$\begingroup\$ @ngn I changed my mind. You can assume the alphabets are of the same size. It's not an interesting detail of the challenge. \$\endgroup\$ – Anush Apr 25 at 9:31
7
+50
\$\begingroup\$

K (ngn/k), 101 bytes

{a:&,/~=\:/+/'x[2]=\:'!'#'*'*x:+@[;0;0,']'x;n:#**|*x;~#a^a^{?y@<y:y,/x@\:y}[,/'+\:'/(n;1)**x]/,n/x 1}

Try it online!

the argument x is a pair of dfa-s.

a dfa is (TransitionTable;InitialState;FinalStates).

we prepend 0 to all rows in both transition tables. this way we can use 0-indexing, and state0 can act as a tarpit state to handle "no transition" transitions.

consider a new dfa whose states are the cartesian product of those of dfa0 and dfa1. when state i from dfa0 is paired with state j from dfa1, the resulting state is labelled (i*n)+j where n is the number of states in dfa1. a is the list of states in the new dfa for which one of the original states was final and the other was not.

we combine the initial states of dfa0 and dfa1 using the formula (i*n)+j. starting there, we compute the set of states in the new automaton that are reachable through its transitions. we test if that set is disjoint from a and return a boolean result.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ah ok. On my phone I just see `ok 8 times in the output section of TIO. Which part is too hard in that case? \$\endgroup\$ – Anush Apr 25 at 13:09
  • \$\begingroup\$ @Anush `ok in my output means that the actual result matches the expected result \$\endgroup\$ – ngn Apr 25 at 13:26
  • \$\begingroup\$ ok....:). What did your mean by "too hard"? \$\endgroup\$ – Anush Apr 25 at 14:32
  • \$\begingroup\$ @Anush it was a mistake of mine. i thought you were talking about different alphabet sizes. \$\endgroup\$ – ngn Apr 25 at 14:39
1
\$\begingroup\$

Prolog (SWI), 431 program + 5 interpreter = 436 bytes

m-->member.
g(A):-read_string(user_input,"\n",[],_,S),term_string(A,S).
f(I,T,S,R):-select(S,T,R),m(I,S),!;S=[I],R=T.
x(S,R)-->[N],{nth1(S,R,N);S=0,N=0}.
x(A,B,C,D)-->x(A,C),x(B,D).
c(_,_,[]).
c(M,E,[A,B|R]):-M=[S,T,C,D],(m(A,C)->m(B,D);\+m(B,D)),f(A,E,X,F),plus(B,N,0),(m(N,X)->c(M,E,R);f(N,F,Y,G),union(X,Y,Z),(P=..[x,A,B]),foldl(P,S,T,Q,R),c(M,[Z|G],Q)).
r:-g(a(A,[B],C)),g(a(D,[E],F)),(c([A,D,C,F],[],[B,E])->R=y;R=n),print(R).

Try it online!

Pass arguments -t r to the interpreter to make r the top-level goal.

Expects the DFAs on standard input, one per line, but with the initial 'Automaton("det", Size, Alphabet' shortened to just 'a('. Outputs a single character to standard output: y if the DFAs are equivalent, or n if they are not.

A more legible version, with comments:

/* Parse a line from stdin as the term A.
   For this program, the term is expected to be a
   Deterministic Finite Automaton in the form
     a(TransitionTable, [Initial], Accepting). */
get(A) :- read_string(user_input, "\n", [], _, S), term_string(A,S).

/* Find the Set in SetOfSets which contains I, and remove it from the
   larger SetOfSets.
   Or if no such Set exists, use the one-element Set [I] instead, and
   leave SetOfSets unchanged. */
find(I, SetOfSets, Set, Rest) :-
  select(Set, SetOfSets, Rest), member(I, Set), !.
find(I, SetOfSets, [I], SetOfSets).

/* Look up the next state from a row of a transition table, or
   two next states from corresponding rows.
   A zero is the failure state and always stays at zero without lookup. */
next_state(0,_) --> [0].
next_state(State,Row) --> [Next], {nth1(State,Row,Next)}.
next_state(State1,State2,Row1,Row2) -->
    next_state(State1,Row1), next_state(State2,Row2).

/* Check if two DFAs are equivalent!

   Equiv is a set of sets of positive state indices from DFA1, negative
   state indices from DFA2, and 0 for a common failure state. After the
   algorithm has examined a pair of states, it makes sure one element
   in Equiv contains both those states for future iterations. All such
   states in one set are tentatively presumed to be equivalent.

   Require is an even-length list. Every pair of elements is a state from
   DFA1 followed by a state from DFA2, and it must be shown that the pair
   of states is equivalent:
     1. If one state is an accept state and the other is not, the DFAs
        are NOT equivalent.
     2. Otherwise, if both states are in the same member of Equiv, no
        further processing is needed for the current pair, since those
        states or related states were already seen.
     3. Otherwise, for each letter in the common alphabet, for equivalent
        DFAs it is necessary that the next states for the two DFAs are
        equivalent.
        3a. Add these pairs of next states to Require for the next iteration.
        3b. Merge sets containing the current states into a common set
            within Equiv for the next iteration.
     4. Repeat until an Accept mismatch is found or until Require is empty.
        If Require is empty, the DFAs are equivalent.
*/
check(_,_,[]).
check(Params,Equiv,[State1,State2|Require]) :-
  /* format("Equiv: ~p~nRequire: ~p~n", [Equiv, [State1,State2|Require]]), */
  Params = [Trans1, Trans2, Accept1, Accept2],
  (member(State1,Accept1) -> member(State2,Accept2) ; \+member(State2,Accept2)),
  find(State1, Equiv, Set1, Equiv2), plus(State2, NegState2, 0),
  (member(NegState2,Set1) -> check(Params, Equiv, Require);
   find(NegState2, Equiv2, Set2, Equiv3), union(Set1, Set2, SetU),
   (P =.. [next_state, State1, State2]),
    foldl(P, Trans1, Trans2, RequireMore, Require),
   check(Params, [SetU|Equiv3], RequireMore)).

/* Top-level goal. Parse two DFAs from standard input, and check
   for equivalence. */
run :- get(a(Transitions1, [Init1], Accept1)), get(a(Transitions2, [Init2], Accept2)),
  (check([Transitions1, Transitions2, Accept1, Accept2], [], [Init1, Init2])
   -> R=y; R=n), print(R).

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Very nice to see a Prolog solution. \$\endgroup\$ – Anush Apr 28 at 15:14
  • 1
    \$\begingroup\$ Though it's yet another case of "seems like Prolog's built-in backtracking support might be useful" then "okay, didn't actually rely much on backtracking after all". \$\endgroup\$ – aschepler Apr 28 at 15:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.