{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# automaton.rdivide(aut)\n",
"$\\newcommand \\ldivide{\\setminus}$\n",
"Compute the right quotient of two automata, i.e. the automaton recognizing the language of words $u$ such that there exists a word $v$ recognized by rhs with $uv$ recognized by lhs.\n",
"\n",
"In other words, it is the automata equivalent of languages right quotient, denoted by the operator / and defined by:\n",
"\n",
"$$K / L = \\bigcup\\limits_{v \\in L} K / v$$\n",
"\n",
"where $K / v$ is the right quotient of K by the word v, defined like this:\n",
"\n",
"$$K / v = \\bigcup\\limits_{w \\in K}w / v = \\{u \\mid uv \\in L\\}$$\n",
"\n",
"The algorithm uses the fact that\n",
"\n",
"$$K / L = (L^t \\ldivide K^t)^t$$\n",
"\n",
"where $\\ldivide$ is the [left quotient](automaton.ldivide.ipynb)\n",
"\n",
"Preconditions:\n",
"- None"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Examples"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import vcsn\n",
"ctx = vcsn.context('lal_char, b')\n",
"aut = lambda e : ctx.expression(e).automaton()"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, b>>"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a1 = aut('abcd')\n",
"a2 = aut('cd')\n",
"a1.rdivide(a2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This demonstrates how `rdivide` is defined: as combination of `ldivide` and `transpose`."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton, b>>"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(a2.transpose().ldivide(a1.transpose())).transpose()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"More examples can be found for the left division ([automaton.ldivide](automaton.ldivide.ipynb))."
]
}
],
"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.5.1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}