automaton.pair.ipynb

Kernel: Python 3

automaton.pair(keep_initials = False)

The pair automaton, or $2$-subset automaton, is an intermediate representation used by the heuristics. It is defined by:

$$\begin{align} Q' &= \{q_0\} \cup \{\{p, q\} \mid p, q \in Q, p \neq q\} \\ \delta'(\{p, q\}, l) &= \begin{cases} q_0 & \text{if}~\delta(p, l) = \delta(q, l),\\ \{\delta(p, l), \delta(q, l)\} & \text{otherwise}. \end{cases} \end{align}$$

See also:

• automaton.synchronizing_word

Examples

import vcsn

%%automaton a daut
0 -> 0 a
0 -> 1 b
1 -> 0 a
1 -> 1 b
2 -> 0 b
2 -> 1 a

a = a.strip()
a.pair()

You also can keep the initial singleton states instead of merging them in a $q_0$ state:

a.pair(True)