{
"metadata": {
"name": "",
"signature": "sha256:da3dddcbf05b77b493f02fd3b56e2f74ff4aa2d04faa5d113bb37240c44abb2f"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Welcome to Vaucanson"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Welcome to this Vaucanson tutorial. Vaucanson is a platform (C++ libraries with various interfaces, a Python binding, and some specific features for IPython) for weighted automata and rational expressions.\n",
"\n",
"This tutorial tries to guide you throw the Python binding, and more specifically the IPython interface, of Vaucanson. If you are not a Python programmer, rest assured that you don't need to know much, and if you are a Python programmer, rest assured that its conventions have been respected, and you will be able to take the full benefit from both Vaucanson and Python.\n",
"\n",
"* [00 - Welcome to Vaucanson](00 - Welcome to Vaucanson.ipynb)\n",
"* [01 - Playing with contexts](01 - Playing with contexts.ipynb)\n",
"* [02 - Basic operations on automata](02 - Basic operations on automata.ipynb)\n",
"* Algorithms\n",
" * [determinize](algos/determinize.ipynb)"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Quick Start"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First, import Vaucanson into Python, and define the \"context\" in which you want to work. Do not worry about the (ugly!) syntax, just see where the alphabet (the set of letters, $\\{a, b, c\\}$) is defined. The last line (`ctx`) is here so that IPython displays what this variable contains."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import vcsn\n",
"ctx = vcsn.context(\"lal_char(abc)_b\")\n",
"ctx"
],
"language": "python",
"metadata": {},
"outputs": [
{
"latex": [
"$\\{a, b, c\\}\\rightarrow\\mathbb{B}$"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"lal_char(abc)_b"
]
}
],
"prompt_number": 1
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This object, the context, defines the types of the various entities. To build a rational expression on this alphabet, use `ctx.ratexp` as follows:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"r1 = ctx.ratexp(\"ab*\")\n",
"r1"
],
"language": "python",
"metadata": {},
"outputs": [
{
"latex": [
"$a \\, {b}^{*}$"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"ab*"
]
}
],
"prompt_number": 2
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The syntax for rational expressions is as follows (with increasing precedence):\n",
"- `\\z` denotes the empty language\n",
"- `\\e` denotes the language of the empty word\n",
"- `a` denotes the language of the word `a`\n",
"- `e+f` denotes the union of the languages of `e` and `f` (note the use of `+`, `|` is not accepted)\n",
"- `ef` denotes the concatenation of the languages of `e` and `f`\n",
"- `e*` denotes the Kleene closure of the language of `e`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So for instance `r1` denotes the words starting with a single `a` followed by any number of `b`s."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Rational expressions are objects that feature methods. One such method is `shortest(number)` that lists the `number` first (in shortlex order) words of the language defined by the rational expresion:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"r1.shortest(10)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"latex": [
"$a \\oplus ab \\oplus abb \\oplus abbb \\oplus abbbb \\oplus abbbbb \\oplus abbbbbb \\oplus abbbbbbb \\oplus abbbbbbbb \\oplus abbbbbbbbb$"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 3,
"text": [
"a + ab + abb + abbb + abbbb + abbbbb + abbbbbb + abbbbbbb + abbbbbbbb + abbbbbbbbb"
]
}
],
"prompt_number": 3
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You may compose rational expressions using Python operators such as `+` for sum, `*` for multiplication (concatenation):"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"r1 + r1 * r1"
],
"language": "python",
"metadata": {},
"outputs": [
{
"latex": [
"$a \\, {b}^{*} + a \\, {b}^{*} \\, a \\, {b}^{*}$"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 4,
"text": [
"ab*+ab*ab*"
]
}
],
"prompt_number": 4
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Vaucanson features different means to build an automaton from a rational expression. The `ratexp.standard()` method builds the \"standard autamaton\", also known as the \"position automaton\", or the \"Glushkov automaton\":"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"r1.standard()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 5,
"svg": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text": [
"mutable_automaton"
]
}
],
"prompt_number": 5
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"When it comes to displaying automata as graphs, there are several \"traditions\". In Vaucanson, initial states are denoted by an entering arrow, and final (or \"accepting\") states are denoted by an exiting arrow. This automaton has one initial state, and two final states.\n",
"\n",
"The `ratexp.derived_term()` method builds the \"derived-term automaton\", aka, the Antimirov automaton."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a1 = r1.derived_term()\n",
"a1"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 6,
"svg": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text": [
"ratexp_automaton>"
]
}
],
"prompt_number": 6
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Python operators that are accepted by rational expressions are also accepted by automata, with matching semantics."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a2 = (r1 + r1*r1).derived_term()\n",
"a2"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 7,
"svg": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text": [
"ratexp_automaton>"
]
}
],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a3 = a1 + a1 * a1\n",
"a3"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 8,
"svg": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text": [
"mutable_automaton"
]
}
],
"prompt_number": 8
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Well, those two automata are not equal (or more rigorously \"isomorphic\"), but they are equivalent:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a2.is_equivalent(a3)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 9,
"text": [
"True"
]
}
],
"prompt_number": 9
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"All the classical algorithms about automata are implemented:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a3"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 10,
"svg": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text": [
"mutable_automaton"
]
}
],
"prompt_number": 10
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a3.determinize()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 11,
"svg": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text": [
"determinized_automaton>"
]
}
],
"prompt_number": 11
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The states of this automaton are decorated with metadata: the corresponding set of states of the input automaton. Use `strip` to remove this decoaration."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a3.determinize().strip().complete()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 12,
"svg": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text": [
"mutable_automaton"
]
}
],
"prompt_number": 12
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that useless states and transitions are gray."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To evaluate a word on an automaton, use `eval()`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a3.eval(\"a\")"
],
"language": "python",
"metadata": {},
"outputs": [
{
"latex": [
"$\\top$"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 13,
"text": [
"1"
]
}
],
"prompt_number": 13
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a3.eval(\"b\")"
],
"language": "python",
"metadata": {},
"outputs": [
{
"latex": [
"$\\bot$"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 14,
"text": [
"0"
]
}
],
"prompt_number": 14
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To see the 10 first accepted words (if there are that many), use `shortest(10)`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a3.shortest(10)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"latex": [
"$a \\oplus aa \\oplus ab \\oplus aab \\oplus aba \\oplus abb \\oplus aabb \\oplus abab \\oplus abba \\oplus abbb$"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 15,
"text": [
"a + aa + ab + aab + aba + abb + aabb + abab + abba + abbb"
]
}
],
"prompt_number": 15
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To extract a rational expression from the automaton, use `ratexp()`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a3.ratexp()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"latex": [
"$a \\, {b}^{*} + a \\, {b}^{*} \\, a \\, {b}^{*}$"
],
"metadata": {},
"output_type": "pyout",
"prompt_number": 16,
"text": [
"ab*+ab*ab*"
]
}
],
"prompt_number": 16
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Voil\u00e0 ! You may now proceed to discover other features in other notebooks. Bon voyage !"
]
}
],
"metadata": {}
}
]
}