21
\$\begingroup\$

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:

enter image description here

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

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

enter image description here

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.
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Note: If I'm understanding the Wikipedia article correctly, "The best upper bound known [for the length of the synchronizing word] is \$(n^3 - n)/6\$". \$\endgroup\$ Sep 5 at 18:34
  • \$\begingroup\$ How to read the input? What does [[2, 1], [3, 4], [0, 4], [2, 1], [0, 3]] mean? The second element in the tuples seem to be more than 2 unique characters? \$\endgroup\$
    – justhalf
    Sep 6 at 8:15
  • \$\begingroup\$ @justhalf an arrow of tuples a means: if the state is s and you read c, go to state a[s][c] \$\endgroup\$ Sep 6 at 8:50
  • 1
    \$\begingroup\$ Ooh, ok, I got it. So the first element is for the first char, the second element is for the second char. \$\endgroup\$
    – justhalf
    Sep 6 at 9:06

5 Answers 5

4
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Could you explain your algorithm? \$\endgroup\$ Sep 6 at 4:24
0
\$\begingroup\$

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Ƈ 
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ You can just use map &:uniq instead of map(&:uniq), and any?{|x|!x[1]} can be any?{|_,x|!x} \$\endgroup\$
    – Steffan
    Sep 10 at 19:06

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.