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:

Examples

In [1]:
import vcsn
In [2]:
%%automaton a daut
0 -> 0 a
0 -> 1 b
1 -> 0 a
1 -> 1 b
2 -> 0 b
2 -> 1 a
%3 0 0 0->0 a 1 1 0->1 b 1->0 a 1->1 b 2 2 2->0 b 2->1 a
In [3]:
a = a.strip()
a.pair()
Out[3]:
%3 0 0 0->0 a, b 1 0, 1 1->0 a, b 2 0, 2 2->1 a, b 3 1, 2 3->1 a, b

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

In [4]:
a.pair(True)
Out[4]:
%3 0 0 0->0 a 1 1 0->1 b 1->0 a 1->1 b 2 2 2->0 b 2->1 a 3 0, 1 3->0 a 3->1 b 4 0, 2 4->3 a, b 5 1, 2 5->3 a, b