symbolic_dynamics.graphs.cernys_automata¶
-
symbolic_dynamics.graphs.
cernys_automata
(n)[source]¶ Returns the nth Cerny automata.
The nth Cerny automata is a fully deterministic graph C_n with states over {0, 1, …, n-1} with alphabet {a, b} with the following transition action:
sd.dot(C_n, i, "b") == i
fori in range(n)
sd.dot(C_n, 0, "a") == 1
sd.dot(C_n, i, "a") == i
fori in range(1, n)
The shortest synchronizing word for C_n is the word
("a"+"b"*(n-1))*(n-2)+"a"
, which has length of(n-1)**2
.- Parameters
- nint
Examples
>>> n = 5 >>> C_n = cernys_automata(n) >>> w = ("a"+"b"*(n-1))*(n-2)+"a" >>> len(sd.idot(C_n, C_n, w)) 1