{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# _automaton_.lightest(_num_=1, _algo_=\"auto\")\n", "\n", "Return a (finite) approximation of the behavior of the automaton. In other words, compute the polynomial of the lightest accepted words (according to the shortlex order), and their associated weight.\n", "\n", "Arguments:\n", "- num the number of words to find (there might be fewer).\n", "- algo the algorithm name.\n", "\n", "The algorithm can be:\n", "- \"breadth-first\": uses the same algorithm as for the search of multiple words.\n", "- \"yen\": uses yen algorithm to retrieve multiple paths, the algorithm does not count loops as possible paths.\n", "- The different implementations of lightest path (see [lightest_automaton](automaton.lightest_automaton.ipynb)): if num is different from one it will use the default implementation of lightest.\n", " - \"auto\"\n", " - \"a-star\"\n", " - \"bellman-ford\"\n", " - \"dijkstra\"\n", "\n", "Preconditions:\n", "- None\n", "\n", "See also:\n", "- [_automaton_.shortest](automaton.shortest.ipynb)\n", "- [_automaton_.lightest_automaton](automaton.lightest_automaton.ipynb)\n", "\n", "## Examples" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import vcsn" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "mutable_automaton, nmin>>" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%automaton --strip bin\n", "context = \"lal_char, nmin\"\n", "$-> 0\n", "0 -> 1 <6>a\n", "0 -> 2 <1>a\n", "2 -> 3 <1>b\n", "3 -> 3 <2>b\n", "3 -> 4 <1>c\n", "4 -> 1 <1>d\n", "0 -> 5 <2>a\n", "5 -> 1 <3>b\n", "1 ->$" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$\\left\\langle 4\\right\\rangle \\mathit{abcd}$" ], "text/plain": [ "<4>abcd" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin.lightest()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that polynomials are printed in shortlex order, i.e., an order based on the labels, although here, a weight-based order would make more sense." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$\\left\\langle 5\\right\\rangle \\mathit{ab} \\oplus \\left\\langle 4\\right\\rangle \\mathit{abcd}$" ], "text/plain": [ "<5>ab + <4>abcd" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin.lightest(2)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$\\left\\langle 6\\right\\rangle \\mathit{a} \\oplus \\left\\langle 5\\right\\rangle \\mathit{ab} \\oplus \\left\\langle 4\\right\\rangle \\mathit{abcd} \\oplus \\left\\langle 6\\right\\rangle \\mathit{abbcd} \\oplus \\left\\langle 8\\right\\rangle \\mathit{abbbcd} \\oplus \\left\\langle 10\\right\\rangle \\mathit{abbbbcd} \\oplus \\left\\langle 12\\right\\rangle \\mathit{abbbbbcd} \\oplus \\left\\langle 14\\right\\rangle \\mathit{abbbbbbcd} \\oplus \\left\\langle 16\\right\\rangle \\mathit{abbbbbbbcd} \\oplus \\left\\langle 18\\right\\rangle \\mathit{abbbbbbbbcd}$" ], "text/plain": [ "<6>a + <5>ab + <4>abcd + <6>abbcd + <8>abbbcd + <10>abbbbcd + <12>abbbbbcd + <14>abbbbbbcd + <16>abbbbbbbcd + <18>abbbbbbbbcd" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin.lightest(10)" ] } ], "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.0+" } }, "nbformat": 4, "nbformat_minor": 0 }