Does there exist a synchronizing word?

Question

A complete deterministic finite automaton is a machine, with some states. Each state in the automaton has, for each character in the alphabet, a pointer to a state (not necessarily a different one). The automaton starts at some state, and then reads a string, character by character. For each character, the automaton moves to the pointer of its current state for the character.

For a given automaton, a synchronizing word is a string which will bring the automaton to the same state, regardless of which state it started in.

For example, the following automaton:

Has 0100 as a synchronizing word, which synchronizes all states to 2.

Not all automata have a synchronizing word. For example, the following automaton:

Doesn't have any synchronizing word - if the length of the string is even then 0 will stay in 0 and 1 will stay in 1, and if it's odd they will swap - in any case, they won't go into the same state.

Your challenge is to write the shortest program you can that checks, given a complete automaton over an alphabet with two characters, if there exists a synchronizing word for it.

Test cases

Using a 0-indexed, 2Xn array.

[[0, 1], [0, 1]] -> true
[[1, 1], [0, 0]] -> false
[[0, 0], [1, 1]] -> false
[[4, 1], [0, 3], [0, 0], [0, 1], [4, 3]] -> true
[[2, 1], [3, 4], [0, 4], [2, 1], [0, 3]] -> true
[[4, 4], [0, 4], [2, 1], [0, 3], [0, 0]] -> false
[[8, 5], [0, 8], [0, 0], [8, 2], [2, 6], [5, 2], [3, 8], [7, 3], [8, 4], [3, 0]] -> true
[[9, 2], [8, 4], [2, 5], [6, 9], [8, 9], [9, 5], [4, 0], [4, 2], [0, 7], [2, 1]] -> true
[[5, 0], [3, 7], [9, 2], [9, 0], [1, 8], [8, 4], [6, 5], [7, 1], [2, 4], [3, 6]] -> true
[[5, 1], [4, 9], [8, 1], [8, 6], [2, 3], [7, 0], [2, 3], [5, 6], [4, 9], [7, 0]] -> false
[[6, 3], [1, 1], [7, 5], [7, 1], [4, 5], [6, 6], [4, 6], [5, 1], [3, 4], [2, 4]] -> false

Rules

• You can use any reasonable I/O format. In particular, any of the following input methods are allowed:
  • A map, multidimensional array, or array of maps, denoting, for each state and character, to which state the automaton transitions. The states can be either 0-indexed or 1-indexed.
  • Any builtin directed graph object which can support multiedges, self-loops, and labeled edges.
  • Any builtin DFA object.
  • You can choose any two characters to be the alphabet.
• You can output any two distinct values, or a truthy/falsey (or reversed) value in your language.
• You may not assume Černý's conjecture (which states that if there exists a synchronizing word, there must be one of length \$(n-1)^2\$).
• Standard loopholes are disallowed.

Answer 1

Python, 92 91 bytes

f=lambda a,s,n=0:n<len(s)**3and any(f(a,[a[t][d]for t in s],n+1)for d in"01")or len({*s})<2

Attempt This Online!

Takes in an automaton a which is a dictionary of dictionaries where a[x][c] describes the state to travel to from state x given character c, and an array s which contains all of the states of the automaton. The characters in the alphabet are the strings 0 and 1.

This code does a very inefficient brute force iteration over all possible words with length less than \$n^3\$ (where \$n\$ is number of states).

---

-1 byte from @Steffan

Python, 87 bytes

f=lambda a,s,q,n=0:n<q**3and any(f(a,{a[t][d]for t in s},q,n+1)for d in"01")or len(s)<2

Attempt This Online!

Same as above, except it also takes in a parameter q which describes the number of states in the automaton.

Answer 2

Haskell, 73 bytes

r!w|let[_]%_=1>0;s%y=all(/=s)y&&or[[u|u<-w,elem u$k<$>s]%(s:y)|k<-r]=w%[]

Try it online!

Takes input as a list of states, and a list of transitions as functions between states.

Not complicated, does a depth first search.

Answer 3

Python3, 471 bytes:

E=enumerate
def f(n,m,c=[]):
 yield c,n
 for i,(I,a)in E(m[n]):M=eval(str(m));del M[n][i];yield from f(a,M,c+[(a,I)])
def M(m,B,p):
 if''==p:return B
 return M(m,dict(m[B])[int(p[0])],p[1:])
def F(m):
 r={}
 for i,_ in E(m):
  for c,n in f(i,m,[(i,-1)]):
   if c[-1][-1]!=-1 or c[-1][1]:r[n]=r.get(n,[])+[(i,c)]
 for n in r:
  if not(V:={i for i,_ in E(m)})-{a for a,_ in r[n]}:
   if any(all(M(m,B,''.join(str(K)for _,K in c[1:]))==n for B in V)for _,c in r[n]):return 1

Try it online!

A little longer than the other solutions, but solves all the test cases pretty quickly. Returns 1 when a synchronizing word exists and None when one does not exist.

Answer 4

Jelly, 21 bytes

WZ€ị®ẎƊ⁸©L*3¤Ð¡ẎZ€ẎEƇ

A monadic Link that accepts a 1-indexed list of nodes, each of which is a pair of positive integers identifying the nodes pointed to by each of the two transition characters (i.e. like the test cases in the question but incremented by one) and yields an empty list (falsey) if no synchronising word exists or a non-empty list (truthy) if one does.

Try it online!
...Too slow for the length 5 and greater tests, but since all of those that do have synchronising words are much shorter this, which searches only up to length \$n+2\$ gives the correct output for all test cases.

How?

Full brute force - generates the list of nodes (by starting node) pointed to by all words from length one up to length \$n^3+1\$ (more than the current known upper bound) and keeps any that are all equal.

WZ€ị®ẎƊ⁸©L*3¤Ð¡ẎZ€ẎEƇ - Link: list of pairs of integers, A
W                     - wrap A in a list
             С       - collect and repeat... (includes the original wrapped A)
            ¤         - ...number of times: nilad followed by links as a nilad:
       ⁸              -                       chain's left argument = A
        ©             -                       (copy to the register)
         L            -                       length
          *3          -                       to the third power
      Ɗ               - ...action: last three links as a monad:
 Z€                   -              transpose each
   ị®                 -              index into the register
     Ẏ                -              tighten
               Ẏ      - tighten
                Z€    - transpose each
                  Ẏ   - tighten
                    Ƈ - keep those for which:
                   E  -   all equal? (i.e. all point to the same node)

---

20 bytes if a full program can output nothing if no synchronising word exists or a (not consistent) list representation if one does - uses the same method:

WZ€ị³ẎƊ³L*3¤Ð¡ẎZ€ẎEƇ 

Answer 5

Ruby, 100 91 bytes

->s{a,*k=r=s.transpose;r|=k|=a.map{|i|s[i]}.transpose-r while a=k.pop;r.any?{|x|!(x|x)[1]}}

Try it online!