context.cerny.ipynb

Kernel: Python 3

context.cerny(n)

Create the Černý automaton with $n$ states.

Preconditions:

• the labelset is free

• the labelset has at least two generators

The Černý automata are $n$-states DFA defined by the following transition function:

$$\delta(s, l) = \begin{cases} (q + 1)~\text{mod}~n & \text{if}~l = a\\ q & \text{if}~l = b \wedge q \neq n - 1\\ 0 & \text{if}~l = b \wedge q = n - 1\\ \end{cases}$$

where $a$ and $b$ denote two letters of the labelsets.

See also:

• automaton.synchronizing_word

Examples

import vcsn
b = vcsn.context('lal_char(ab), b')

b.cerny(4)