{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Édition, visualisation d'automates\n",
" http://vaucanson-project.org/Awali/1.0/index.html ."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"application/javascript": [
"IPython.notebook.set_autosave_interval(0)"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Autosave disabled\n"
]
}
],
"source": [
"# We disable autosave for technical reasons.\n",
"# Replace 0 by 120 in next line to restore default.\n",
"%autosave 0"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[Warning] The python module awalipy relies on compilation executed \"on-the-fly\" depending on the context (type of weights, of labels, etc.). As a result, the very first call to a given function in a given context may take up to 10 seconds. \n"
]
}
],
"source": [
"import awalipy # If import fails, check that \n",
" # Python version used as Jupyter\n",
" # kernel matches the one\n",
" # Awalipy was compiled with."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(The above warning is displayed every time awalipy is imported.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Créer un automate"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Les alphabets sont des `str` Python\n",
"- chaque `char` de `str` est une lettre de l'alpahbet\n",
"- l'ordre n'a pas d'importance (`\"abc\"` et `\"bac\"` représentent le même alphabet)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"alph1 = \"abc\" # represents {a,b,c}\n",
"alph2 = \"01\" # represents {0,1}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Un **automate** peut être construit à partir d'un alphabet"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"A = awalipy.Automaton(alph1)\n",
"# ou directment `awalipy.Automaton(\"abc\")`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`A` est un automate sans états ni transitions sur l'alphabet {a,b,c}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ajout d'états\n",
"\n",
"par défaut le nom affiché de l'état est donné par son indice : le premier état est nommé `\"s0\"`, le second `\"s1\"`, etc."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"stt_0 = A.add_state()\n",
"stt_1 = A.add_state()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ajout de transitions"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"tr_0 = A.set_transition(stt_0,stt_1,'a')\n",
"tr_1 = A.set_transition(stt_1,stt_0,'b')\n",
"tr_2 = A.set_transition(stt_0,stt_0,'b')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"
\n",
"Il n'y a pas de classe Python pour les transitions et les états. On manipule leurs identifiants."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"2\n"
]
}
],
"source": [
"print (stt_0)\n",
"print (tr_2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Rendre les états initiaux ou terminaux"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"A.set_initial(stt_0)\n",
"A.set_final(stt_1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Visualiser un automate"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Visualisation graphique d'un automate.
\n",
"(Pour de petits automates)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"A.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Visualisation d'un automate en format texte."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Automaton (lal_char_b):\tWeight Set: B\tAlphabet: abc\n",
"States:{\t0(i)\t1(f)\t}\n",
"Transitions:{\t0--a-->1\t1--b-->0\t0--b-->0\t\t}"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"NB: la mention `(i)` qui suit un état indique qu'il est *initial*. De même, `(f)` indique *final* and `(i,f)` indique *initial et final*."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Détruire des flèches et des états"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Considérons l'automate `A`."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"A.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On ajoute tout d'abord des états et des transitions"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"stt_2 = A.add_state()\n",
"tr_3 = A.set_transition(stt_1,stt_1,'a')\n",
"# Not recording ids of transitions any further\n",
"A.set_transition(stt_2,stt_2,'b')\n",
"A.set_transition(stt_0,stt_2,'a')\n",
"A.set_transition(stt_2,stt_0,'b')\n",
"A.set_transition(stt_1,stt_2,'b')\n",
"A.set_transition(stt_1,stt_2,'a')\n",
"A.set_transition(stt_2,stt_1,'a')\n",
"A.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Détruire une transition par son identificateur"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"A.del_transition(tr_3) # tr_3 est la transition : s2 --a--> s2\n",
"A.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Détruire une transition par un triplet (origine, destination, label) "
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"A.del_transition(stt_2,stt_2,'b')\n",
"A.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Détruire un état (et toutes ses transitions entrantes et sortantes) "
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"A.del_state(stt_2)\n",
"A.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Charger et sauvegarder un automate"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Sauvegarder un automate dans un fichier. Le format utilisé est JavaScript Object Notation (JSON) d'où l'extension \".json\"."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"A.save(\"fibo.json\")"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[0m\u001b[01;36mawalipy.cpython-35m-x86_64-linux-gnu.so\u001b[0m@ Edition1.ipynb\r\n",
"\u001b[01;36mawalipy_purepython_extra.py\u001b[0m@ Edition2.ipynb\r\n",
"awalipy_purepython_extra.pyc Edition3.ipynb\r\n",
"\u001b[01;36mawalipy.so\u001b[0m@ fibo.json\r\n",
"ClassicalTransformations1.ipynb fibo_LR_additioner.json\r\n",
"ClassicalTransformations2.ipynb \u001b[01;34m__pycache__\u001b[0m/\r\n",
"CMakeLists.txt RationalExpression.ipynb\r\n"
]
}
],
"source": [
"ls"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Charger un automate"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"B = awalipy.load(\"fibo.json\")\n",
"B.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Quelques exemples dans la bibliothèque. On peut obtenir la liste comme ceci"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Name Description\n",
"---- -----------\n",
"a1 .............. NFA which recognizes words with factor 'ab'\n",
"b1 .............. Z-FA which counts the number of 'b'\n",
"binary .......... Z-FA which converts binary sequences into values\n",
"c1 .............. Z-FA that converts binary sequences on alphabet {a,b} into values\n",
"d1 .............. Z-FA which computes the difference between the numbers of 'a' and 'b'\n",
"e1 .............. Q-automaton that converts words of {a,b}^* into their binary values 'after the radix point'\n",
"evena ........... NFA which recognizes words with an even number of 'a'\n",
"fibotdc-lr ...... Sequential transducer which tries to replace 'abb' by 'baa'\n",
"gray ............ Gray code increment\n",
"heapmodel ....... Z-max-plus automaton, heap model with 2 pieces\n",
"lamplighter ..... Sequential transducer...\n",
"minab ........... Z-min-plus-automaton which computes the minimum among the numbers of 'a' and 'b' in every word\n",
"minblocka ....... Z-min-plus-automaton which computes the length of the shortest block of 'a' in every word\n",
"oddb ............ NFA which recognizes the words with an odd number of 'b'\n",
"prob-rabin ...... R-automaton (probabilistic automaton) that accepts w with prob. expansion(w)\n",
"rotation ........ C-automaton realizing a rotation\n",
"slowcerny ....... Synchronisable NFA which meets Cerny bound\n",
"slowgrow ........ Z-min-plus-automaton with a slow growing length function\n"
]
}
],
"source": [
"awalipy.list_example_automata()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Charger un exemple de la bibliothèque."
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"A = awalipy.load(\"a1\")\n",
"A.display()"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"([0, 1], [0, 1, 2])"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A.states(), A.transitions()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Obtenir la liste des états initiaux et terminaux"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"([0], [1])"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A.initial_states(), A.final_states()"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"Lister les transitions attachées à un état"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"([1], [0])"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A.outgoing(stt_1), A.incoming(stt_1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lister les transitions allant d'un état dans un autre"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0]"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A.outin(stt_0,stt_1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Déterminisation"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"A1 = awalipy.load(\"a1\")\n",
"A1.display()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"A2 = A1.determinize()\n",
"A2.display()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"A2.display(history=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Expressions rationnelles"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Créer une expression"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lorsqu'une expression est parsée, la précédence d'opérateurs ets la suivante : étoile > concatenation > union. Donc \n",
"\n",
"- `a+(b*)` = `a+b*` != `(a+b)*`\n",
"- `a(b*)` = `ab*` != `(ab)*`\n",
"- `a+(bc)` = `a+bc` != `(a+b)c`"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"e = awalipy.RatExp(\"(a+bc)c*(ab)*\")\n",
"e\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Par défaut, l'alphabet d'une expression rationnelle est l'ensemble des lettres qui apparaissent dans l'expression. Mais on peut augmenter cet alphabet."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"f = awalipy.RatExp(\"(a+b)(c*+a)*\", alphabet=\"abcd\")\n",
"f"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Afficher l'expression sous forme d'arbre"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"e.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Union"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"e+f"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Concaténation"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"e^^f"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Étoile\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"e.star()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Des expressions aux automates (Glushkov)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"g = awalipy.RatExp(\"1*0\")\n",
"g.standard().display()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.10.0"
}
},
"nbformat": 4,
"nbformat_minor": 1
}