{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# `automaton`.`pair`(`keep_initials` = `False`)\n",
"\n",
"The pair automaton, or $2$-subset automaton, is an intermediate representation used by the heuristics.\n",
"It is defined by:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"Q' &= \\{q_0\\} \\cup \\{\\{p, q\\} \\mid p, q \\in Q, p \\neq q\\}\n",
"\\\\\n",
"\\delta'(\\{p, q\\}, l) &=\n",
" \\begin{cases}\n",
" q_0 & \\text{if}~\\delta(p, l) = \\delta(q, l),\\\\\n",
" \\{\\delta(p, l), \\delta(q, l)\\} & \\text{otherwise}.\n",
" \\end{cases}\n",
"\\end{align}\n",
"$$\n",
"\n",
"See also:\n",
"- [automaton.synchronizing_word](automaton.synchronizing_word.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Examples"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import vcsn"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"name_automaton, b>>>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%automaton a daut\n",
"0 -> 0 a\n",
"0 -> 1 b\n",
"1 -> 0 a\n",
"1 -> 1 b\n",
"2 -> 0 b\n",
"2 -> 1 a"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"pair_automaton, b>>>>"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.pair()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You also can keep the initial singleton states instead of merging them in a $q_0$ state:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"pair_automaton, b>>>>"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.pair(True)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.4.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}