Automates_TP1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "tm7J027xlF-e"
   },
   "source": [
    "# Automates finis - TP 1 \n",
    "\n",
    "\n",
    "## Objectif du TP\n",
    "\n",
    "L'objectif de ce premier TP est d'implémenter un programme en **Python** qui prend deux entrées : \n",
    "\n",
    "1. un fichier `.txt` contenant la description d'un automate fini _A_ et\n",
    "2. un mot _m_ à reconnaître. \n",
    "\n",
    "Votre programme doit (a) lire/charger l'automate _A_ à partir du fichier `.txt`, (b) afficher _ERROR_ si l'automate est non déterministe, ou (c) si, au contraire, l'automate est déterministe, afficher _YES_ si le mot peut être reconnu par l'automate, ou _NO_ si le mot ne peut pas être reconnu par l'automate. En pseudo-code, cela donne :\n",
    "```txt\n",
    "1. A = automate(fichier)\n",
    "2. si deterministe(A) alors\n",
    "3.    si reconnait(A,m) alors\n",
    "4.      afficher \"YES\"\n",
    "5.    sinon\n",
    "6.      afficher \"NON\"\n",
    "7. sinon\n",
    "8.   afficher \"ERROR\"\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "uKx7OCiolF-0"
   },
   "source": [
    "## Environnement de travail\n",
    "\n",
    "**Énoncés**: les énoncés des TPs d'automates finis sont disponibles en deux formats sur Ametice : PDF et notebook Jupyter `.ipynb`. Le notebook Jupyter contient du code python intégré que vous pouvez exécuter directement. C'est carrément cool ! Le PDF est statique, donc moins marrant, mais il est là au cas où, pour éviter d'être bloqué.e en cas de souci avec le notebook Jupyter.\n",
    "\n",
    "<!--Alternativement, [installez Jupyter sur votre ordinateur](https://jupyter.org/install) (avec Anaconda, ou séparément), puis ouvrez le notebook [Automates_TP1.ipynb](https://github.com/ceramisch/automatesfinis/blob/main/Automates_TP1.ipynb), ou alors ouvrez-le en utilisant [Google Colab](https://colab.research.google.com/).-->\n",
    "\n",
    "**Travailler en salle TP** Vous devrez écrire un programme `tp1automates.py` en langage **Python** pour implementer le pseudo-code ci-dessus. L'énoncé au format notebook Jupyter vous permet de tester des bouts de code, mais vous ne devez pas programmer sur les notebook Jupyter directement. En salle TP, utilisez l'environnement de programmation **Spyder** disponible sur la session **Linux/Luminy**. Pour travailler à la maison, consultez la fin l'énoncé. Mais avant de faire tout cela, il faut **lire tout l'énoncé** pour se familiariser avec la bibliothèque fournie.  Eh oui, on ne se met pas à coder tout de suite...\n",
    "\n",
    "**Dépôt de fichiers**: les TP sont incrémentaux : on a besoin du TP1 pour faire le TP2, etc... Cela aboutira à la création d'un programme capable de reconnaître, à l'aide d'un automate fini, si un _mot_ quelconque appartient au langage dénoté par une _expression régulière_ quelconque. Prenez un moment pendant la séance d'aujourd'hui pour préparer votre environnement de travail. Nous vous conseillons de créer un dépôt de contrôle de version `git` pour ce mini-projet sur [etulab](https://etulab.univ-amu.fr) (ou gitlab, github... au choix). Vous pouvez aussi travailler sur un dossier partagé Dropbox, Google Drive ou AMUBox. Dans tous les cas, sauvegardez vos fichiers à la fin de chaque séance.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "lEi3yB9elF-3"
   },
   "source": [
    "## Format de fichier `.txt`\n",
    "\n",
    "Un automate décrit dans un fichier `txt` consiste en une suite de lignes, où chaque ligne est un triplet, sauf la dernière. Les éléments du triplet sont séparés par des espaces. Le triplet `X a Y` correspond à une transition entre un état source `X` et un état cible `Y` étiquetée par le symbole `a`. Il est recommandé de représenter les états `X` et `Y` avec des nombres, et les symboles `a` avec des lettres majuscules ou minuscules non-accentuées. Le symbole spécial `%` est utilisé pour les transition-ε (pour le moment, pas nécessaire). Le premier état source de la première transition est considéré comme l'état initial de l'automate. La dernière ligne est toujours précédée de la lettre majuscule `A` indiquant les états d'acceptation. Ensuite, les états d'acceptation sont listés, séparés par des espaces.\n",
    "\n",
    "Voici un exemple d'automate déterministe décrit dans un fichier. Cet automate reconnait _a\\*+b\\*_. Pour vous en convaincre, vous pouvez le dessiner sur une feuille. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "Gxg9RdhclF-9"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 a 1\n",
      "0 b 2\n",
      "1 a 1\n",
      "2 b 2\n",
      "A 0 1 2\n",
      "\n"
     ]
    }
   ],
   "source": [
    "source = \"\"\"0 a 1\n",
    "0 b 2\n",
    "1 a 1\n",
    "2 b 2\n",
    "A 0 1 2\n",
    "\"\"\"\n",
    "print(source) # affiche la variable qui vient d'être initialisée ci-dessus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Note pour vous qui ne connaissez pas encore les notebook Jupyter_ : vous pouvez exécuter la cellule ci-dessus (se placer dans la cellule puis appuyer sur `⏵Exécuter` en haut de la page, ou `Ctrl+Entrée` pour le raccourci clavier). Cela va afficher la valeur de la variable `source`. Essayez de la modifier et voyez que l'affichage change. Sur ce notebook Jupyter, l'état des variables est gardé d'une cellule à l'autre. Voilà, vous savez maintenant comment utiliser un notebook Jupyter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RnT0JPsFlF_L"
   },
   "source": [
    "## Bibliothèque `automaton.py` fournie\n",
    "\n",
    "Nous vous fournissons une bibliothèque python `automaton.py`, disponible sur [le github du cours](https://github.com/ceramisch/automatesfinis), avec les fonctionnalités suivantes:\n",
    "*   Création et manipulation d'un objet `Automaton` qui représente un automate fini \n",
    "*   Lecture et écriture à partir d'un fichier textuel\n",
    "*   Affichage graphique à l'aide de `graphviz`\n",
    "\n",
    "Vous devez bien comprendre le fonctionnement de cette bibliothèque. En particulier, elle utilise de la programmation orientée objets en Python. Les prochaines sections vous permettent de découvrir la bibliothèque. Si vous êtes à l'aise en Python, vous pouvez ouvrir le code de la bibliothèque et le modifier, mais cela ne devrait pas être nécessaire.\n",
    "\n",
    "### Premier pas avec `automaton.py`\n",
    "\n",
    "Mais pour le moment, essayons déjà de comprendre son fonctionnement. Pas besoin de télécharger quoi que ce soit, la bibliothèque est déjà intégrée au notebook Jupyter (vous devrez téléchrger la bibliothèque sur votre ordinateur plus tard). Avec `automaton.py`, vous pouvez créer un nouvel automate et lui donner un nom. Cet automate, pour le moment, sera vide. Vérifiez en exécutant le code ci-dessous :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "AxNHmu1AlF_M",
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a_testg\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: Warning: graphviz not installed, will not draw automaton graphically\n"
     ]
    }
   ],
   "source": [
    "from automaton import Automaton\n",
    "a_test = Automaton('a_test'+\"g\")\n",
    "\n",
    "print(a_test.name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "3SJ9uf3JlF_W"
   },
   "source": [
    "Le code ci-dessus affiche un automate vide. Essayez de changer son nom et exécutez à nouveau le bloc ci-dessus. Alternativement, vous pouvez `print(a_test)` pour afficher l'automate sous forme textuelle.\n",
    "\n",
    "Notez la première ligne `import...` qui importe la bibliothèque automaton. Cela vous permet d'utiliser la bibliothèque par la suite.\n",
    "\n",
    "Continuons à nous familiariser avec la bibliothèque sur ce notebook. Vous pouvez ajouter des états et des transitions à votre automate vide. Attention, la source de la première transition ajoutée sera toujours considérée comme l'état initial:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "nc9s4FjYlF_Y",
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a_test = <Q={0,1}, S={a}, D, q0=0, F={}>\n",
      "D =\n",
      "| |a|\n",
      "-----\n",
      "|0|1|\n",
      "-----\n",
      "|1| |\n",
      "-----\n"
     ]
    }
   ],
   "source": [
    "a_test.reset()\n",
    "a_test.add_transition(\"0\",\"a\",\"1\")\n",
    "print(a_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "u--4U1fflF_f"
   },
   "source": [
    "Notez que cet automate ne reconnait aucun mot, car il n'a aucun état d'acceptation/final. Vous pouvez marquer un ou plusieurs états comme finaux à l'aide de la fonction suivante:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "GqY3WJ_8lF_f",
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a_test = <Q={0,1}, S={a}, D, q0=0, F={1}>\n",
      "D =\n",
      "| |a|\n",
      "-----\n",
      "|0|1|\n",
      "-----\n",
      "|1| |\n",
      "-----\n"
     ]
    }
   ],
   "source": [
    "a_test.make_accept(\"1\")\n",
    "print(a_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "h1YhqeWmlF_l"
   },
   "source": [
    "Alternativement, vous pouvez marquer plusieurs états comme états d'acceptation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "id": "tbCs2xKwlF_n"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<bound method Automaton.__str__ of <automaton.Automaton object at 0x00000204935A5750>>\n"
     ]
    }
   ],
   "source": [
    "a_test.make_accept([\"0\",\"1\"])\n",
    "print(a_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "7YmDl9s2lF_t"
   },
   "source": [
    "### Affichage textuel d'un automate\n",
    "\n",
    "Vous pouvez afficher l'automate sous la forme textuelle à n'importe quel moment dans votre code, par exemple, pour déboguer. Notez que la fonction delta est donnée sous la forme d'un tableau de transitions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "DQ0_6mzAlF_v",
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a_test = <Q={0,1}, S={a}, D, q0=0, F={0,1}>\n",
      "D =\n",
      "| |a|\n",
      "-----\n",
      "|0|1|\n",
      "-----\n",
      "|1| |\n",
      "-----\n"
     ]
    }
   ],
   "source": [
    "print(a_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ZA0IvMGflF_0"
   },
   "source": [
    "Dans cet exemple, `Q` contient la liste d'états `{0,1}`, l'alphabet `S` est automatiquement construit à partir des transitions et contient uniquement le symbole `{a}`, l'état initial est `q0=0` et les états d'acceptation `F={0,1}`. Ces valeurs sont accessibles aussi directement, sous la forme de listes ou de chaînes de caractères, via des variables de l'automate (contrairement à Java, toutes les méthodes et attributs sont publics en Python) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "id": "6KzwT_xHlF_0"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0', '1']\n",
      "['a']\n",
      "0\n",
      "['0', '1']\n",
      "| |a|\n",
      "-----\n",
      "|0|1|\n",
      "-----\n",
      "|1| |\n",
      "-----\n"
     ]
    }
   ],
   "source": [
    "print(a_test.states)\n",
    "print(a_test.alphabet)\n",
    "print(a_test.initial)\n",
    "print(a_test.acceptstates)\n",
    "print(a_test.transition_table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "bGLSDuHilF_6"
   },
   "source": [
    "Vous pouvez aussi afficher votre automate sous la forme de fichier `.txt`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "Gr7xz-FGlF_7"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 a 1\n",
      "A 0 1\n"
     ]
    }
   ],
   "source": [
    "print(a_test.to_txtfile(\"test.txt\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "mP92uxOxlGAB"
   },
   "source": [
    "### Lecture à partir d'un fichier\n",
    "\n",
    "Un automate peut être réinitialisé à tout moment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "id": "M1_kK6fllGAC",
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.43.0 (0)\n -->\n<!-- Title: L Pages: 1 -->\n<svg width=\"70pt\" height=\"68pt\"\n viewBox=\"0.00 0.00 70.00 68.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 64)\">\n<title>L</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-64 66,-64 66,4 -4,4\"/>\n<text text-anchor=\"middle\" x=\"31\" y=\"-7.8\" font-family=\"Times,serif\" font-size=\"14.00\">a_test</text>\n<!-- a -->\n<g id=\"node1\" class=\"node\">\n<title>a</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"0,-23.5 0,-59.5 62,-59.5 62,-23.5 0,-23.5\"/>\n<text text-anchor=\"middle\" x=\"31\" y=\"-37.8\" font-family=\"Times,serif\" font-size=\"14.00\">empty</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<automaton.Automaton at 0x7f7a585b7250>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a_test.reset()\n",
    "a_test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "b18nZ4m5lGAH"
   },
   "source": [
    "Vous pouvez aussi construire un automate à partir d'une chaîne de caractères directement à l'aide de la fonction `from_txt`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "KMWAY60PlGAI"
   },
   "outputs": [],
   "source": [
    "source = \"\"\"0 a 1\n",
    "0 b 2\n",
    "1 a 1\n",
    "2 b 2\n",
    "A 0 1 2\n",
    "\"\"\"\n",
    "astarbstar = Automaton(\"astarbstar\")\n",
    "astarbstar.from_txt(source)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "2Mw4cJZ2lGAN"
   },
   "source": [
    "Essayez de modifier la variable `source` et observez le résultat dans l'automate. Ajouter ou supprimez des transitions, des états, des états d'acceptation...\n",
    "\n",
    "Vous pouvez aussi lire un automate en passant directement le nom du fichier à la fonction `from_txtfile`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "chgwQjCslGAO"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: Automaton astarbstar not empty: content will be lost\n"
     ]
    }
   ],
   "source": [
    "astarbstar.from_txtfile(\"test/astarbstar.af\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "AC9kIFzMlGAU"
   },
   "source": [
    "_Remarque_: la bibliothèque vous préviendra si quelque chose d'étrange se passe à l'aide des `WARNING`, comme ci-dessus lors que vous écrasez le contenu existant par le chargement d'un nouvel automate. Parfois ces messages vous aideront à ne pas faire de bêtise, d'autres fois vous pouvez les ignorer sans problèmes.\n",
    "\n",
    "Les transitions-ε sont représentées par le symbole spécial `%` (constante `EPSILON` dans `automaton.py`). Vous pouvez créer un automate non-déterministe avec des transitions-ε comme ceci:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "1GmPTR5jlGAV"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: Automaton astarbstar not empty: content will be lost\n"
     ]
    }
   ],
   "source": [
    "source = \"\"\"0 % 1\n",
    "0 % 2\n",
    "1 a 0\n",
    "1 a 1\n",
    "2 b 2\n",
    "A 0 1 2\n",
    "\"\"\"\n",
    "astarbstar.from_txt(source)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "G5sUGG1WlGAZ"
   },
   "source": [
    "### Affichage graphique\n",
    "\n",
    "Les automates sur ce notebook Jupyter s'affichent graphiquement à l'aide de la fonction `to_graphviz()` (qui est executée automatiquement en coulisses). La fonction renvoie l'objet `graphviz` au [format DOT](https://graphviz.org/doc/info/lang.html), converti ensuite en un fichier PDF. Il n'est pas nécessaire de rentrer dans le détail, la bibliothèque gère l'affichage pour vous. \n",
    "\n",
    "Pour afficher des automates graphiquement quand vous serez en train de travailler en local, sur votre code-source sur Spyder, il suffira d'appeler la fonction `to_graphviz(\"test\")`. Un nouveau fichier `test.pdf` avec la représentation graphique de l'automate sera alos créé dans le même dossier contenant votre programme python (l'extension `.pdf` sera automatiquement ajoutée).\n",
    "\n",
    "L'exécution du code ci-dessous n'affichera rien. Mais si vous allez sur `Fichier->Ouvrir...` et que vous regardez dans le dossier `test`, vous remarquerez que le fichier `astarbstar.gv.pdf` aura été modifié il y a peu de temps. C'est ce fichier qui contient le résultat de l'exécution du code ci-dessous. Vous pouvez le télécharger et le visualiser avec un lecteur de PDF."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "tsO2vfhMlGAa"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: Graphviz not installed, cannot draw automaton\n"
     ]
    }
   ],
   "source": [
    "astarbstar_gv = astarbstar.to_graphviz(\"test/testt.gv\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vKeQvRjilGAg"
   },
   "source": [
    "### Structure interne des états et transitions\n",
    "\n",
    "À certains moments, vous aurez besoin d'accéder à la liste des **états** et de **transitions** à l'intérieur de l'automate. Ainsi, il faut comprendre comment ces éléments sont représentés en interne. Prenez le temps de bien comprendre la structure, faites un schéma sur une feuille si besoin. Vous pouvez aussi regarder le code-source de la bibliothèque `automaton.py` directement. Cela vous aidera à mieux vous servir de la bibliothèque lors de ce TP et des suivants.\n",
    "\n",
    "Chaque état est représenté comme un objet de la classe `State` et stocké dans un dictionnaire nommé `statesdict`. Les clés de ce dictionnaire sont les noms des états (`str`), et les valeurs sont les objets de type `State` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OrderedDict([('0', <automaton.State object at 0x00000204935A5BA0>), ('1', <automaton.State object at 0x00000204935A5F60>), ('2', <automaton.State object at 0x00000204935A5150>)])\n"
     ]
    }
   ],
   "source": [
    "print(astarbstar.statesdict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vous remarquerez l'usage d'un `OrderedDict` au lieu d'un dictionnaire python classique. La seule différence c'est que celui-ci conserve l'ordre d'insertion des paires clé-valeur, contrairement à un dictionnaire python standard. En pratique, c'est pareil.\n",
    "\n",
    "Par exemple, pour accéder à l'objet `State` correspondant à l'état nommé `\"1\"`, vous pouvez accéder à `astarbstar.statesdict[\"1\"]`, c'est-à-dire la valeur associée à la clé `\"1\"`, qui est un objet de la classe `State`. Chaque état contient une liste de transitions, aussi sous la forme d'un dictionnaire :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "OrderedDict([('a', OrderedDict([(<automaton.State at 0x204935a5f60>, None)]))])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astarbstar.statesdict[\"1\"].transitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous voyons ci-dessus, par exemple, que l'état nommé `\"1\"` contient une transition pour le symbole `a` menant vers un autre dictionnaire d'états. Ce dictionnaire permet de prendre en compte les transitions vers plusieurs états dans les automates non déterministes. Pour accéder à l'état destination de la transition, on doit d'abord transformer le dictionnaire en liste, puis récupérer le premier élément de cette liste, et finalement afficher cet état comme une chaîne de caractères `str`. Mis bout à bout, cela donne :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'b'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_28012/2787189045.py\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;31m# source state 1 (from dict of states), transition on \"a\", first (and only) destination state \"1\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[0mstr\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mastarbstar\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mstatesdict\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m\"1\"\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mtransitions\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m\"a\"\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 3\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mastarbstar\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mstatesdict\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m\"1\"\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mtransitions\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m\"b\"\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mKeyError\u001b[0m: 'b'"
     ]
    }
   ],
   "source": [
    "# source state 1 (from dict of states), transition on \"a\", first (and only) destination state \"1\"\n",
    "str(list(astarbstar.statesdict[\"1\"].transitions[\"a\"])[1])\n",
    "print(len(astarbstar.statesdict[\"1\"].transitions[\"b\"]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ouf ! C'est bien complexe, mais cela permet de représenter n'importe quel automate fini déterministe ou non déterministe.\n",
    "\n",
    "Alternativement, utilisez l'attribut `transitions` de l'automate, qui donne la liste de transitions sous la forme d'une `list` python simple. Chaque transition est une tuple de trois éléments de type `str` : source, symbole, destination. Cela peut être pratique, si vous voulez manipuler des objets plus simples que les dictionnaires et les objets `State` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 --%--> 1\n",
      "0 --%--> 2\n",
      "1 --a--> 1\n",
      "2 --b--> 2\n"
     ]
    }
   ],
   "source": [
    "for (source,symb,dest) in astarbstar.transitions : # et non pas a.transitions()\n",
    "  print( \"{} --{}--> {}\".format(source,symb,dest))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vous trouverez d'autres exemples d'usage de la bibliothèque dans `automaton.py` à la toute fin du code-source."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Étapes à suivre pas à pas\n",
    "#### ou \"Comment éviter de se perdre lors du TP1\"\n",
    "\n",
    "1. Lire la **totalité** de l'énoncé au format notebook Jupyter, tester les bouts de code, comprendre comment marche la bibliothèque `automaton.py`. Normalement, c'est ce que vous venez de faire.\n",
    "2. Télécharger depuis le [dépôt git du cours](https://github.com/ceramisch/automatesfinis/) la totalité du dossier `automatesfinis-main.zip` (Cliquer sur _Code_ > _Download ZIP_)\n",
    "3. Extraire les fichiers dans un dossier bien identifié, pour pouvoir le retrouver plus tard\n",
    "4. Ouvrir l'environnement Spyder, et ouvrir le squelette `tp1automates.py` fourni dans `automatesfinis-main` avec Spyder\n",
    "5. Configurer l'environnement avec les arguments de la ligne de commande comme suit :\n",
    "  - Sur Spyder, avec `tp1automates.py` ouvert, cliquer sur _Run_ > _Configuration per file_\n",
    "  - Cocher la case _Command line options_ et indiquer dans le champ textuel (a) le nom d'un fichier contenant un automate fini au format textuel et (b) un mot à reconnaître. Par exemple, pour commencer, vous pouvez écrire : <br/>`test/astarbstar.af aaa` -- où `test/astarbstar.af` est le chemin relatif du fichier (fourni). N'oubliez pas l'espace entre le nom du fichier `test/astarbstar.af` et le mot à reconnaître `aaa` <br/>Vous modifierez l'automate et le mot à reconnaître au fur et à mesure que vous avancez dans les TP pour tester d'autres automates, d'autres mots à reconnaître ou ne pas reconnaître.\n",
    "  - Les valeurs de ces deux arguments sont disponibles dans votre script dans la variable spéciale `sys.argv`\n",
    "6. Comprendre le squelette : le `main` vérifie les deux arguments de la ligne de commande `sys.argv[1]` et `sys.argv[2]`. Ensuite, il initialise un objet de la classe `Automaton` et appelle deux fonctions pour afficher `ERROR`, `YES` ou `NO`.\n",
    "7. Implémenter les deux fonctions attendues : `is_deterministic` et `recognizes` \n",
    "8. Avant la fin du TP, mettre en place un dépôt git sur [etulab](https://etulab.univ-amu.fr) pour organiser le travail pour la prochaine séance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "wwbVoN2GlGAh"
   },
   "source": [
    "## Travail à effectuer\n",
    "\n",
    "Votre travail consiste à implémenter deux fonctionnalités:\n",
    "\n",
    "1.   Écrire une fonction qui prend un automate fini en entrée et qui renvoie un booléen pour indiquer si, oui ou non, l'automate est déterministe\n",
    "\n",
    "2.   Écrire une fonction qui prend un automate fini déterministe et un mot en entrée, et qui renvoie un booléen pour indiquer si, oui ou non, le mot est reconnu par l'automate\n",
    "\n",
    "De plus, vous devez écrire un script/programme qui peut être exécuté sur un terminal et qui prend en entrée (`sys.argv`) deux [arguments](https://riptutorial.com/fr/python/example/6530/utilisation-d-arguments-en-ligne-de-commande-avec-argv): un fichier texte contenant un automate et un mot à reconnaître, dans cet ordre. Si vous ne connaissez pas les arguments `argv`, lisez le tutoriel ci-dessus. Ces arguments seront spécifiés dans Spyder à l'aide du menu _Run > Configuration per file_ (voir détail ci-dessous).\n",
    "\n",
    "Le script doit :\n",
    "\n",
    "1.   Charger l'automate depuis le fichier texte (à l'aide de la bibliothèque fournie)\n",
    "\n",
    "2.   Vérifier si l'automate est déterministe (fonctionnalité 1 ci-dessus) et, sinon, afficher _ERROR_\n",
    "\n",
    "3.   Si l'automate est déterministe, vérifier s'il reconnaît le mot (fonctionnalité 2 ci-dessus) et afficher _YES_ si le mot est reconnu, _NO_ sinon\n",
    "\n",
    "Une version squelette de `tp1automates.py` est fournie sur le [dépôt git du cours](https://github.com/ceramisch/automatesfinis/). Utilisez-la comme point de départ de votre TP. Vous n'aurez qu'à compléter les deux fonctions indiquées `is_deterministic` et `recognizes`, le reste est déjà fait pour vous."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tester votre programme\n",
    "\n",
    "Quelques fichiers de test vous sont fournis dans le dossier `test`. Voici quelques exemples de ce que doit afficher l'exécution pour votre programme `tp1automates.py` sur le terminal :\n",
    "\n",
    "```bash\n",
    "$ ./tp1automates.py test/astarbstar.af a\n",
    "YES\n",
    "$ ./tp1automates.py test/astarbstar.af b\n",
    "YES\n",
    "$ ./tp1automates.py test/astarbstar.af bbb\n",
    "YES\n",
    "$ ./tp1automates.py test/astarbstar.af %\n",
    "YES\n",
    "$ ./tp1automates.py test/astarbstar.af aaaaaaa\n",
    "YES\n",
    "$ ./tp1automates.py test/astarbstar.af bbaa\n",
    "NO\n",
    "$ ./tp1automates.py test/astarbstar.af aba\n",
    "NO\n",
    "$ ./tp1automates.py test/astarbstar.af aabbb\n",
    "NO\n",
    "$ ./tp1automates.py test/astarbstar.af abc\n",
    "NO\n",
    "$ ./tp1automates.py test/astarbstar-epsilon.af abb\n",
    "ERROR\n",
    "$ ./tp1automates.py test/astarbstar-nfa.af abb\n",
    "ERROR\n",
    "```\n",
    "\n",
    "Vous devez non seulement implémenter le programme mais aussi le tester. Pour cela, écrivez 3 automates finis au format textuel pour augmenter la base de tests au délà des deux fichiers fournis dans le dossier `test`. Vous pouvez utiliser des automates vus en cours ou en TD, par exemple. Ces automates doivent être placés dans le dossier `test` et formeront votre base de tests, qui grandira au fur et à mesure des TPs. Vous pouvez générer les `.pdf` correspondants à chaque automate test à l'aide de la fonction `to_graphviz()`\n",
    "\n",
    "Pour déboguer votre programme, n'oubliez pas que vous pouvez à tout moment appeler `print(a)` pour afficher l'automate sur le terminal, ou appeler `a.to_graphviz(\"out\")` pour le visualiser graphiquement dans un fichier `out.pdf`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Travailler à la maison\n",
    "\n",
    "Si vous avez l'habitude de travailler sur une IDE telle que intelliJ, eclipse, pycharm ou Spyder, utilisez-la. Sinon, installez Anaconda+Spyder, comme en salle TP. Alternativement, vous pouvez programmer avec un simple éditeur de texte comme atom, SublimeText, geany ou Notepad++, ou utiliser l'environnement 100% en ligne [repl.it](http://repl.it) (mais celui-ci ne permet pas l'affichage graphique).\n",
    "\n",
    "**Pré-requis à installer** : Pour les affichages graphiques ci-dessus, vous devez installer l'outil `graphviz` et la bibliothèque python correspondante. Sur **Linux**, une fois python 3 installé, vous pouvez exécuter:\n",
    "```bash\n",
    "sudo apt install graphviz\n",
    "pip3 install graphviz # ou tout simplement pip install graphviz, selon votre configuration\n",
    "```\n",
    "\n",
    "Si vous êtes sur **Windows**, le plus simple est d'installer Anaconda. Une fois que vous l'avez téléchargé et installé, allez sur Anaconda Navigator > Environement > Update index. Affichez les packages 'Not installed' au lieu de 'Installed' puis cherchez _graphviz_ dans la barre de recherche. Installez les packages _graphviz_ et _python-graphviz_ (les deux sont nécessaires). Ensuite, vous pouvez revenir à la page d'accueil (Home) et lancer l'IDE Spyder. Une [vidéo sur Ametice](https://www.youtube.com/watch?v=jiREDWQdKb4) vous explique comment installer Anaconda+Spyder et les pré-requis graphviz sur Windows.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Automates_TP1 ",
   "provenance": [],
   "toc_visible": true
  },
  "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.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}