{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# _automaton_.has_twins_property\n",
"\n",
"Whether the automaton has the twins property.\n",
"\n",
"- Sibling states: Two states $p$, $q$ are _siblings_ if there exist two labels $x$ and $y$ such that $p$ and $q$ can be reached from an initial state by path labeled with $x$ and there is a cycle at $p$ and $q$ both labeled with $y$.\n",
"- Twins states: Two sibling states $p$ and $q$ are _twins_ iff for any label $y$:\n",
" $w[P(p, y, p)] = w(P[q, y, q])$\n",
"- Has twins property: An automaton has the twins property if any two sibling states of this automaton are twins. \n",
"\n",
"Preconditions:\n",
"- The automaton is not cycle ambiguous\n",
"\n",
"See also:\n",
"- [_automaton_.is_cycle_ambiguous](automaton.is_cycle_ambiguous.ipynb)\n",
"- [_automaton_.determinize](automaton.determinize.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Examples"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import vcsn\n",
"q = vcsn.context('lal_char(ab), q')\n",
"def std(e):\n",
" return q.expression(e, 'binary').standard()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider the following $\\mathbb{Q}$ automaton:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, q>>"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = std('(ab)* + (ab)*')\n",
"a"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"State $1$ and $3$ are siblings: they can be reached from $0$ with label \"a\" and there are two cycles in them with the same label \"ba\". Since the weights of these cycles equals $1$ (in $\\mathbb{Q}$), they are twins. This automaton has two sibling states only and they are twins so it has twins property."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.has_twins_property()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Conversely, the following automaton does not have the twins property because state $1$ and state $4$ are siblings but not twins: the weights of cycles differ ($1$ != $2$)."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, q>>"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = std('(<2>ab)* + (ab)*')\n",
"a"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.has_twins_property()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"When the automaton has no sibling states, it has the twins property."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, q>>"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = std(\"(aa)*+(ab)*\")\n",
"a"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.has_twins_property()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the tropical semiring ($\\mathbb{Z}_{\\text{min}}$), an automaton is determinizable iff the automaton has the twins property."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"name_automaton, zmin>>>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%automaton a\n",
"context = \"lal_char(abcd), zmin\"\n",
"$ -> 0\n",
"0 -> 1 <1>a\n",
"0 -> 2 <2>a\n",
"1 -> 1 <3>b\n",
"1 -> 3 <5>c\n",
"2 -> 2 <3>b\n",
"2 -> 3 <6>d\n",
"3 -> $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This automaton has the twins property (the two sibling states $1$ and $2$ are twins), so it is determinizable (in $\\mathbb{Z}_{\\text{min}}$)."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"determinized_automaton, zmin>>>, weighted_tag>"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.determinize()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The twins property can also be check in $\\mathbb{Z}$:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"name_automaton, z>>>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%automaton a\n",
"context = \"letterset, z\"\n",
"$ -> 0\n",
"0 -> 1 a\n",
"0 -> 2 <2>a\n",
"1 -> 1 <3>b\n",
"1 -> 3 <5>c\n",
"2 -> 2 <3>b\n",
"2 -> 3 <6>d\n",
"3 -> $"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.has_twins_property()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Or with tuples of weightsets:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"name_automaton, lat>>>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%automaton a\n",
"context = \"lal_char(abc), lat\"\n",
"$ -> 0\n",
"0 -> 1 <(1, 3)>a\n",
"0 -> 2 <(1, 5)>a\n",
"1 -> 3 <(4, 8)>b\n",
"3 -> $\n",
"2 -> 4 <(6, 4)>b\n",
"4 -> $\n",
"3 -> 1 <(9, 3)>a\n",
"4 -> 2 <(6, 7)>a"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.has_twins_property()"
]
}
],
"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
}