{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# _automaton_.minimize(algo=\"auto\")\n",
"\n",
"Minimize an automaton.\n",
"\n",
"The algorithm can be: \n",
"- `\"auto\"`: same as `\"signature\"` for Boolean automata on free labelsets, otherwise `\"weighted\"`.\n",
"- `\"brzozowski\"`: run determinization and codeterminization.\n",
"- `\"hopcroft\"`: requires free labelset and Boolean automaton.\n",
"- `\"moore\"`: requires a deterministic automaton.\n",
"- `\"signature\"`\n",
"- `\"weighted\"`: same as `\"signature\"` but accept non Boolean weightsets.\n",
"\n",
"Preconditions:\n",
"- the automaton is trim\n",
"- `\"brzozowski\"`\n",
" - the labelset is free\n",
" - the weightset is $\\mathbb{B}$\n",
"- `\"hopcroft\"`\n",
" - the labelset is free\n",
" - the weightset is $\\mathbb{B}$\n",
"- `\"moore\"`\n",
" - the automaton is deterministic\n",
" - the weightset is $\\mathbb{B}$\n",
"- `\"signature\"`\n",
" - the weightset is $\\mathbb{B}$\n",
"\n",
"Postconditions:\n",
"- the result is equivalent to the input automaton\n",
"\n",
"Caveat:\n",
"- the resulting automaton might not be minimal if the input automaton is not deterministic.\n",
"\n",
"See also:\n",
"- [automaton.is_deterministic](automaton.is_deterministic.ipynb)\n",
"- [automaton.cominimize](automaton.cominimize.ipynb)\n",
"- [automaton.reduce](automaton.reduce.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Examples"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import vcsn"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Weighted\n",
"\n",
"Using `minimize` or `minimize(\"weighted\")`."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, z>>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%automaton -s a1\n",
"context = \"lal_char(abc), z\"\n",
"$ -> 0\n",
"0 -> 1 <2>a\n",
"0 -> 2 <3>a\n",
"1 -> 1 a\n",
"1 -> 3 <4>a\n",
"2 -> 2 a\n",
"2 -> 4 a\n",
"3 -> $\n",
"4 -> $"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"partition_automaton, z>>>"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a1.minimize()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following example is taken from [lombardy.2005.tcs](References.ipynb#lombardy.2005.tcs), Fig. 4."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, z>>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%automaton -s a\n",
"context = \"lal_char, z\"\n",
"$ -> 0\n",
"$ -> 1 <2>\n",
"0 -> 0 a\n",
"0 -> 1 b\n",
"0 -> 2 <3>a,b\n",
"0 -> 3 b\n",
"1 -> 1 a, b\n",
"1 -> 2 a, <2>b\n",
"1 -> 3 <2>a\n",
"2 -> $ <2>\n",
"3 -> $ <2>"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"partition_automaton, z>>>"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.minimize()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Signature"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, b>>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%automaton -s a2\n",
"context = \"lal_char(abcde), b\"\n",
"$ -> 0\n",
"0 -> 1 a\n",
"0 -> 3 b\n",
"1 -> 1 a\n",
"1 -> 2 b\n",
"2 -> 2 a\n",
"2 -> 5 b\n",
"3 -> 3 a\n",
"3 -> 4 b\n",
"4 -> 4 a\n",
"4 -> 5 b\n",
"5 -> 5 a, b\n",
"5 -> $"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"partition_automaton, b>>>"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a2.minimize(\"signature\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Moore"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a2.is_deterministic()"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"partition_automaton, b>>>"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a2.minimize(\"moore\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Brzozowski"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"determinized_automaton, b>>>, vcsn::wet_kind_t::bitset, false>>, vcsn::wet_kind_t::bitset, false>"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a2.minimize(\"brzozowski\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Hopcroft"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"partition_automaton, b>>>"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a2.minimize(\"hopcroft\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Minimization of transposed automaton\n",
"For minimization and cominimization to produce automata of the same implementation types, the minimization of a transposed automaton produces a transposed partition automaton, instead of the converse."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'transpose_automaton, b>>>'"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = vcsn.b.expression('ab+ab').standard()\n",
"a.transpose().type()"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'transpose_automaton, b>>>>'"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.transpose().minimize().type()"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'transpose_automaton, b>>>>'"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.minimize().transpose().type()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Repeated Minimization/Cominimization\n",
"The minimizations algorithms other than Brzozowski build decorated automata (whose type is `partition_automaton`). Repeated minimizarion and/or cominization does not stack these decorations, they are collapsed into a single layer.\n",
"\n",
"For instance:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, z>>"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"z = vcsn.context('lal_char, z')\n",
"a1 = z.expression('<2>abc', 'trivial').standard()\n",
"a2 = z.expression('ab<2>c', 'trivial').standard()\n",
"a = a1.add(a2, 'general')\n",
"a"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"partition_automaton, z>>>"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.minimize()"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"partition_automaton, z>>>"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"m = a.minimize().cominimize()\n",
"m"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that the initial and final states are labeled `0,4` and `3,7` , not `{0}, {4}` and `{3,7}` as would have been the case if the two levels of decorations had been kept. Indeed, the type of `m` is simple:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'partition_automaton, z>>>'"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"m.type()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We obtain the exact same result (including decorations) even with repeated invocations, even in a different order:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"partition_automaton, z>>>"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"m2 = a.cominimize().cominimize().minimize().minimize()\n",
"m2"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"m == m2"
]
}
],
"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.4"
}
},
"nbformat": 4,
"nbformat_minor": 0
}