Deterministic Rabin-Automaton according to improved Muller/Schupp: 13 states: k 0: [1|0]- k 1: 1 [1|0,1]- k 2: 10 [1|0,2]- k 3: 100 [1|0,4]- k 4: 101 [1|0,1,3]- +-> [2|3]+ +-> [3|0,1]- k 5: 1010 [1|0,2,4]- +-> [2|4]0 +-> [3|0,2]- k 6: 10100 [1|0,4]- +-> [2|4]0 +-> [3|0]- k 7: 10101 [1|0,1,3]- +-> [2|1]0 +-> [3|0,3]- +-> [4|3]+ +-> [5|0]- k 8: 101001 [1|0,1]- +-> [2|1]0 +-> [3|0]- k 9: 101010 [1|0,2,4]- +-> [2|2]0 +-> [3|0,4]- +-> [4|4]0 +-> [5|0]- k10: 1010010 [1|0,2]- +-> [2|2]0 +-> [3|0]- k11: 1010101 [1|0,1,3]- +-> [2|3]+ +-> [3|0,1]- +-> [4|1]0 +-> [5|0]- k12: 10101010 [1|0,2,4]- +-> [2|4]0 +-> [3|0,2]- +-> [4|2]0 +-> [5|0]- Transition table: 0 1 k 0 k 0 k 1 k 1 k 2 k 1 k 2 k 3 k 4 k 3 k 3 k 1 k 4 k 5 k 1 k 5 k 6 k 7 k 6 k 6 k 8 k 7 k 9 k 1 k 8 k10 k 1 k 9 k 6 k11 k10 k 6 k 4 k11 k12 k 1 k12 k 6 k 7 Acceptance pairs: Pair for vertex 2 (sizes: 4, 2): ({k0,k1,k2,k3}, {k4,k11}) Pair for vertex 4 (sizes: 9, 1): ({k0,k1,k2,k3,k4,k5,k6,k8,k10}, {k7}) Overall: 2 pair(s) with non-empty accepting set