{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# _expression_.thompson\n",
"\n",
"Generate the Thompson automaton from an expression.\n",
"\n",
"Preconditions:\n",
"- the expression is basic.\n",
"\n",
"Caveats:\n",
"- it is not guaranteed that `Result.is_valid()`\n",
"- the context of the result might be different from the original context: spontaneous-transition support is required.\n",
"\n",
"Properties:\n",
"- `Result.proper().is_isomorphic(r.standard())`\n",
"\n",
"See also:\n",
"- [_expression_.automaton](expression.automaton.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Examples"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Thompson procedure generates an automaton with spontaneous-transitions, which requires a labelset that features a \"one\" label. The nullableset and wordset labelsets (and their compositions) do support a \"one\" label."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton>, b>>"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import vcsn\n",
"vcsn.context('lan_char, b').expression('a[bc]d').thompson()"
]
},
{
"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": [
"vcsn.context('law_char, b').expression(\"'aa'[bc]'dd'\").thompson()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You may, however, use a labelset which does not feature a \"one\", in which case the context of the automaton will be different from the one of the expression."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$(\\{a, \\ldots\\})^?\\to\\mathbb{B}$"
],
"text/plain": [
"{a...}? -> B"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"vcsn.context('lal_char, b').expression(\"a\").thompson().context()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Weights"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Weights are supported."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\left( \\left\\langle \\frac{1}{6} \\right\\rangle \\,{a}^{*} + \\left\\langle \\frac{1}{3} \\right\\rangle \\,{b}^{*}\\right)^{*}$"
],
"text/plain": [
"(<1/6>a*+<1/3>b*)*"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"r = vcsn.context('lan_char(abc), q').expression('(<1/6>a*+<1/3>b*)*')\n",
"r"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton>, q>>"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t = r.thompson()\n",
"t"
]
},
{
"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": [
"t.proper()"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton>, q>>"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"r.standard()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note however that you may generate invalid automata (from invalid expressions):"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"mutable_automaton>, q>>"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t = vcsn.context('lan_char(abc), q').expression('\\e*').thompson()\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t.is_valid()"
]
}
],
"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
}