agreg/Algorithme de Cocke-Kasami-Younger (python3).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Table-des-matières\" data-toc-modified-id=\"Table-des-matières-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Table des matières</a></div><div class=\"lev1 toc-item\"><a href=\"#1.-Agrégation-externe-de-mathématiques\" data-toc-modified-id=\"1.-Agrégation-externe-de-mathématiques-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>1. Agrégation externe de mathématiques</a></div><div class=\"lev2 toc-item\"><a href=\"#1.1-Leçon-orale,-option-informatique\" data-toc-modified-id=\"1.1-Leçon-orale,-option-informatique-21\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>1.1 Leçon orale, option informatique</a></div><div class=\"lev4 toc-item\"><a href=\"#Feedbacks?\" data-toc-modified-id=\"Feedbacks?-2101\"><span class=\"toc-item-num\">2.1.0.1&nbsp;&nbsp;</span>Feedbacks?</a></div><div class=\"lev1 toc-item\"><a href=\"#2.-Algorithme-de-Cocke-Kasami-Younger\" data-toc-modified-id=\"2.-Algorithme-de-Cocke-Kasami-Younger-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>2. Algorithme de Cocke-Kasami-Younger</a></div><div class=\"lev3 toc-item\"><a href=\"#2.0.1-Implémentation-d'un-développement-pour-les-leçons-906,-907,-910,-923.\" data-toc-modified-id=\"2.0.1-Implémentation-d'un-développement-pour-les-leçons-906,-907,-910,-923.-301\"><span class=\"toc-item-num\">3.0.1&nbsp;&nbsp;</span>2.0.1 Implémentation d'un développement pour les leçons 906, 907, 910, 923.</a></div><div class=\"lev3 toc-item\"><a href=\"#2.0.2-Références-:\" data-toc-modified-id=\"2.0.2-Références-:-302\"><span class=\"toc-item-num\">3.0.2&nbsp;&nbsp;</span>2.0.2 Références :</a></div><div class=\"lev2 toc-item\"><a href=\"#2.1-Classes-pour-répresenter-une-grammaire\" data-toc-modified-id=\"2.1-Classes-pour-répresenter-une-grammaire-31\"><span class=\"toc-item-num\">3.1&nbsp;&nbsp;</span>2.1 Classes pour répresenter une grammaire</a></div><div class=\"lev3 toc-item\"><a href=\"#2.1.1-Du-typage-en-Python-?!\" data-toc-modified-id=\"2.1.1-Du-typage-en-Python-?!-311\"><span class=\"toc-item-num\">3.1.1&nbsp;&nbsp;</span>2.1.1 Du typage en Python ?!</a></div><div class=\"lev3 toc-item\"><a href=\"#2.1.2-La-classe-Grammaire\" data-toc-modified-id=\"2.1.2-La-classe-Grammaire-312\"><span class=\"toc-item-num\">3.1.2&nbsp;&nbsp;</span>2.1.2 La classe <code>Grammaire</code></a></div><div class=\"lev3 toc-item\"><a href=\"#2.1.3-Premier-exemple-de-grammaire-(non-Chomsky)\" data-toc-modified-id=\"2.1.3-Premier-exemple-de-grammaire-(non-Chomsky)-313\"><span class=\"toc-item-num\">3.1.3&nbsp;&nbsp;</span>2.1.3 Premier exemple de grammaire (non-Chomsky)</a></div><div class=\"lev3 toc-item\"><a href=\"#2.1.4-Second-exemple-de-grammaire-(non-Chomsky)\" data-toc-modified-id=\"2.1.4-Second-exemple-de-grammaire-(non-Chomsky)-314\"><span class=\"toc-item-num\">3.1.4&nbsp;&nbsp;</span>2.1.4 Second exemple de grammaire (non-Chomsky)</a></div><div class=\"lev3 toc-item\"><a href=\"#2.1.5-Dernier-exemple-de-grammaire\" data-toc-modified-id=\"2.1.5-Dernier-exemple-de-grammaire-315\"><span class=\"toc-item-num\">3.1.5&nbsp;&nbsp;</span>2.1.5 Dernier exemple de grammaire</a></div><div class=\"lev2 toc-item\"><a href=\"#2.2-Vérifier-qu'une-grammaire-est-bien-formée\" data-toc-modified-id=\"2.2-Vérifier-qu'une-grammaire-est-bien-formée-32\"><span class=\"toc-item-num\">3.2&nbsp;&nbsp;</span>2.2 Vérifier qu'une grammaire est bien formée</a></div><div class=\"lev2 toc-item\"><a href=\"#2.3-Vérifier-qu'une-grammaire-est-en-forme-normale-de-Chomsky\" data-toc-modified-id=\"2.3-Vérifier-qu'une-grammaire-est-en-forme-normale-de-Chomsky-33\"><span class=\"toc-item-num\">3.3&nbsp;&nbsp;</span>2.3 Vérifier qu'une grammaire est en forme normale de Chomsky</a></div><div class=\"lev2 toc-item\"><a href=\"#2.4-(enfin)-L'algorithme-de-Cocke-Kasami-Younger\" data-toc-modified-id=\"2.4-(enfin)-L'algorithme-de-Cocke-Kasami-Younger-34\"><span class=\"toc-item-num\">3.4&nbsp;&nbsp;</span>2.4 (enfin) L'algorithme de Cocke-Kasami-Younger</a></div><div class=\"lev2 toc-item\"><a href=\"#2.5-Exemples\" data-toc-modified-id=\"2.5-Exemples-35\"><span class=\"toc-item-num\">3.5&nbsp;&nbsp;</span>2.5 Exemples</a></div><div class=\"lev3 toc-item\"><a href=\"#2.5.1-Avec-$G_3$\" data-toc-modified-id=\"2.5.1-Avec-$G_3$-351\"><span class=\"toc-item-num\">3.5.1&nbsp;&nbsp;</span>2.5.1 Avec <span class=\"MathJax_Preview\" style=\"color: inherit;\"><span class=\"MJXp-math\" id=\"MJXp-Span-545\"><span class=\"MJXp-msubsup\" id=\"MJXp-Span-546\"><span class=\"MJXp-mi MJXp-italic\" id=\"MJXp-Span-547\" style=\"margin-right: 0.05em;\">G</span><span class=\"MJXp-mn MJXp-script\" id=\"MJXp-Span-548\" style=\"vertical-align: -0.4em;\">3</span></span></span></span><script type=\"math/tex\" id=\"MathJax-Element-96\">G_3</script></a></div><div class=\"lev3 toc-item\"><a href=\"#2.5.2-Avec-$G_6$\" data-toc-modified-id=\"2.5.2-Avec-$G_6$-352\"><span class=\"toc-item-num\">3.5.2&nbsp;&nbsp;</span>2.5.2 Avec <span class=\"MathJax_Preview\" style=\"color: inherit;\"><span class=\"MJXp-math\" id=\"MJXp-Span-556\"><span class=\"MJXp-msubsup\" id=\"MJXp-Span-557\"><span class=\"MJXp-mi MJXp-italic\" id=\"MJXp-Span-558\" style=\"margin-right: 0.05em;\">G</span><span class=\"MJXp-mn MJXp-script\" id=\"MJXp-Span-559\" style=\"vertical-align: -0.4em;\">6</span></span></span></span><script type=\"math/tex\" id=\"MathJax-Element-98\">G_6</script></a></div><div class=\"lev2 toc-item\"><a href=\"#2.6-Mise-en-forme-normale-de-Chomsky-(bonus)\" data-toc-modified-id=\"2.6-Mise-en-forme-normale-de-Chomsky-(bonus)-36\"><span class=\"toc-item-num\">3.6&nbsp;&nbsp;</span>2.6 Mise en forme normale de Chomsky <em>(bonus)</em></a></div><div class=\"lev3 toc-item\"><a href=\"#2.6.1-Exemple-pour-$G_1$\" data-toc-modified-id=\"2.6.1-Exemple-pour-$G_1$-361\"><span class=\"toc-item-num\">3.6.1&nbsp;&nbsp;</span>2.6.1 Exemple pour <span class=\"MathJax_Preview\">G_1</span><script type=\"math/tex\">G_1</script></a></div><div class=\"lev3 toc-item\"><a href=\"#2.6.2-Exemple-pour-$G_6$\" data-toc-modified-id=\"2.6.2-Exemple-pour-$G_6$-362\"><span class=\"toc-item-num\">3.6.2&nbsp;&nbsp;</span>2.6.2 Exemple pour <span class=\"MathJax_Preview\">G_6</span><script type=\"math/tex\">G_6</script></a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "dea75246-a31b-40b4-a49d-b9afe6eee2ee"
    }
   },
   "source": [
    "# Table des matières\n",
    "* [1. Agrégation externe de mathématiques](#1.-Agrégation-externe-de-mathématiques)\n",
    "\t* [1.1 Leçon orale, option informatique](#1.1-Leçon-orale,-option-informatique)\n",
    "* [2. Algorithme de Cocke-Kasami-Younger](#2.-Algorithme-de-Cocke-Kasami-Younger)\n",
    "\t* &nbsp;\n",
    "\t\t* [2.0.1 Implémentation d'un développement pour les leçons 906, 907, 910, 923.](#2.0.1-Implémentation-d'un-développement-pour-les-leçons-906,-907,-910,-923.)\n",
    "\t\t* [2.0.2 Références :](#2.0.2-Références-:)\n",
    "\t* [2.1 Classes pour répresenter une grammaire](#2.1-Classes-pour-répresenter-une-grammaire)\n",
    "\t\t* [2.1.1 Du typage en Python ?!](#2.1.1-Du-typage-en-Python-?!)\n",
    "\t\t* [2.1.2 La classe ``Grammaire``](#2.1.2-La-classe-Grammaire)\n",
    "\t\t* [2.1.3 Premier exemple de grammaire (non-Chomsky)](#2.1.3-Premier-exemple-de-grammaire-%28non-Chomsky%29)\n",
    "\t\t* [2.1.4 Second exemple de grammaire (non-Chomsky)](#2.1.4-Second-exemple-de-grammaire-%28non-Chomsky%29)\n",
    "\t\t* [2.1.5 Dernier exemple de grammaire](#2.1.5-Dernier-exemple-de-grammaire)\n",
    "\t* [2.2 Vérifier qu'une grammaire est bien formée](#2.2-Vérifier-qu'une-grammaire-est-bien-formée)\n",
    "\t* [2.3 Vérifier qu'une grammaire est en forme normale de Chomsky](#2.3-Vérifier-qu'une-grammaire-est-en-forme-normale-de-Chomsky)\n",
    "\t* [2.4 (enfin) L'algorithme de Cocke-Kasami-Younger](#2.4-%28enfin%29-L'algorithme-de-Cocke-Kasami-Younger)\n",
    "\t* [2.5 Exemples](#2.5-Exemples)\n",
    "\t\t* [2.5.1 Avec $G_3$](#2.5.1-Avec-$G_3$)\n",
    "\t\t* [2.5.2 Avec $G_6$](#2.5.2-Avec-$G_6$)\n",
    "\t* [2.6 Mise en forme normale de Chomsky *(bonus)*](#2.6-Mise-en-forme-normale-de-Chomsky-*%28bonus%29*)\n",
    "\t\t* [2.6.1 Exemple pour $G_1$](#2.6.1-Exemple-pour-$G_1$)\n",
    "\t\t* [2.6.2 Exemple pour $G_6$](#2.6.2-Exemple-pour-$G_6$)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "69c52735-d8a8-451b-93bb-eac98efd50ca"
    }
   },
   "source": [
    "# 1. Agrégation externe de mathématiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "49566064-31f5-48d8-9843-4cdc6e3ef152"
    }
   },
   "source": [
    "## 1.1 Leçon orale, option informatique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "9b3d1cdf-ca96-42cc-988b-be3a8a4715d9"
    }
   },
   "source": [
    "> - Ce [notebook Jupyter](http://jupyter.org/) est une implémentation d'un algorithme constituant un développement pour l'option informatique de l'agrégation externe de mathématiques.\n",
    "> - Il s'agit de l'[algorithme de Cocke-Kasami-Younger](https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami).\n",
    "> - Cette implémentation (partielle) a été rédigée par [Lilian Besson](http://perso.crans.org/besson/) ([sur GitHub ?](https://github.com/Naereen/), [sur Bitbucket ?](https://bitbucket.org/lbesson)), et [est open-source](https://github.com/Naereen/notebooks/blob/master/agreg/Algorithme%20de%20Cocke-Kasami-Younger%20%28python3%29.ipynb).\n",
    "\n",
    "> #### Feedbacks?\n",
    "> - Vous avez trouvé un bug ? → [Signalez-le moi svp !](https://github.com/Naereen/notebooks/issues/new), merci d'avance.\n",
    "> - Vous avez une question ? → [Posez la svp !](https://github.com/Naereen/ama.fr) [![Demandez moi n'importe quoi !](https://img.shields.io/badge/Demandez%20moi-n'%20importe%20quoi-1abc9c.svg)](https://GitHub.com/Naereen/ama.fr)\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "29640a95-6ba1-4db6-90c6-873eebb49d06"
    }
   },
   "source": [
    "# 2. Algorithme de Cocke-Kasami-Younger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "977443a2-4e87-43f0-8198-65a8a02d55a4"
    }
   },
   "source": [
    "### 2.0.1 Implémentation d'un développement pour les leçons 906, 907, 910, 923."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "7999839d-b7e5-43d6-8ede-6765f12a8b3c"
    }
   },
   "source": [
    "L'algorithme de Cocke-Kasami-Younger (CYK) permet de résoudre le problème du mot en temps $\\mathcal{O}(|w|^3)$, par programmation dynamique.\n",
    "La grammaire $G$ doit déjà avoir été mise en forme de [forme normale de Chomsky](https://fr.wikipedia.org/wiki/Forme_normale_de_Chomsky), ce qui prend un temps $\\mathcal{O}(|G|^2)$ et produit une grammaire équivalente $G'$ de taille $\\mathcal{O}(|G|^2)$ en partant de $G$ (qui doit être bien formée)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "981227ac-e731-447f-8fe9-b25e4e546547"
    }
   },
   "source": [
    "### 2.0.2 Références :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "67357bc2-f510-485b-a17d-fd89b46bbaf7"
    }
   },
   "source": [
    "- [Cocke-Kasami-Younger sur Wikipedia](https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami),\n",
    "- Bien traité dans [\"Hopcroft, Ullman\", Ch7.4.4, p298](https://catalogue.ens-cachan.fr/cgi-bin/koha/opac-detail.pl?biblionumber=23694),\n",
    "- Esquissé dans [\"Carton\", Ex4.7 Fig4.2 p170](https://catalogue.ens-cachan.fr/cgi-bin/koha/opac-detail.pl?biblionumber=41719),\n",
    "- [Développement tapé en PDF par Theo Pierron (2014)](http://perso.eleves.ens-rennes.fr/~tpier758/agreg/dvpt/info/CYK.pdf),\n",
    "- [Ces slides d'un cours sur les langages et les grammaires](http://pageperso.lif.univ-mrs.fr/~alexis.nasr/Ens/M2/pcfg.pdf).\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "1da0f4ab-ccfc-412f-9efa-e7520d73a821"
    }
   },
   "source": [
    "## 2.1 Classes pour répresenter une grammaire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "221b1aa3-999b-46bd-9ef6-ac240ccded3f"
    }
   },
   "source": [
    "Au lieu de types formels définis en OCaml, on utilise des classes en Python, pour répresenter une grammaire (pas seulement en forme normale de Chomsky mais dans une forme un peu plus générale)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "588b818a-344d-44f3-910f-8b094ab72da0"
    }
   },
   "source": [
    "### 2.1.1 Du typage en Python ?!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "eadf8257-9a0e-4406-9455-5b82921f0457"
    }
   },
   "source": [
    "Mais comme je veux frimer en utilisant des types formels, on va utiliser des [annotations de types en Python](https://www.python.org/dev/peps/pep-0484/).\n",
    "C'est assez nouveau, disponible **à partir de Python 3.5**. Si vous voulez en savoir plus, une bonne première lecture peut être [cette page](https://mypy.readthedocs.io/en/latest/builtin_types.html).\n",
    "\n",
    "*Note :* ces annotations de types ne sont PAS nécessaires."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "nbpresent": {
     "id": "aa8251b1-61e4-4914-9ad1-e66efd88b21f"
    }
   },
   "outputs": [],
   "source": [
    "# On a besoin de listes et de tuples\n",
    "from typing import List, Tuple  # Module disponible en Python version >= 3.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "7acecf25-b05e-42f7-9269-1ea5ba9e5265"
    }
   },
   "source": [
    "On définit les types qui nous intéressent :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "nbpresent": {
     "id": "9471cb9a-937d-4f95-9f54-260b3b2e4da3"
    }
   },
   "outputs": [],
   "source": [
    "# Type pour une variable, juste une chaine, e.g. 'X' ou 'S'\n",
    "Var = str\n",
    "# Type pour un alphabet\n",
    "Alphabet = List[Var]\n",
    "# Type pour une règle : un symbole transformé en une liste de symboles\n",
    "Regle = Tuple[Var, List[Var]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "609def09-9448-4ad3-ab50-ab5b76700114"
    }
   },
   "source": [
    "*Note :* ces annotations de types ne sont là que pour illustrer et aider le programmeur, Python reste un langage dynamiquement typé (i.e. on fait ce qu'on veut...)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "a1f2c855-d249-45fd-a621-65f5d25aedd9"
    }
   },
   "source": [
    "### 2.1.2 La classe ``Grammaire``"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "aa98b297-0aa0-4ca7-b9ec-64c271212a60"
    }
   },
   "source": [
    "Une grammaire $G$ est définie par :\n",
    "\n",
    "- $\\Sigma$ son alphabet de production, qui sont les lettres dans les mots produits à la fin, e.g., $\\Sigma = \\{ a, b\\}$,\n",
    "- $V$ son alphabet de travail, qui sont les lettres utilisées dans la génération de mots, mais pas dans les mots à la fin, e.g., $V = \\{S, A\\}$,\n",
    "- $S$ est le symbole de travail initial,\n",
    "- $R$ est un ensemble de règles, qui sont de la forme $U \\rightarrow x_1 \\dots x_n$ pour $U \\in V$ une variable de travail (***pas* de production**), et $x_1, \\dots, x_n$ sont variables de production ou de travail (dans $\\Sigma \\cup V$), e.g., $R = \\{ S \\rightarrow \\varepsilon, S \\rightarrow A S b, A \\rightarrow a, A \\rightarrow a a \\}$.\n",
    "\n",
    "\n",
    "Et ainsi on peut definir un classe ``Grammaire``, qui n'est rien d'autre qu'un moyen d'encapsuler ces différentes valeurs $\\Sigma$, $V$, $S$, et $R$ (en OCaml, ce serait un type avec des champs d'enregistrement, défini par exemple par ``type grammar = { sigma : string list; v: string list; s: string; r: (string, strin list) list; };;``).\n",
    "\n",
    "On ajoute aussi une méthode ``__str__`` à cette classe ``Grammaire`` pour afficher la grammaire joliment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "nbpresent": {
     "id": "90271656-b57e-408d-b001-5f689f7ec7ae"
    }
   },
   "outputs": [],
   "source": [
    "class Grammaire(object):\n",
    "    \"\"\" Type pour les grammaires algébriques (en forme de Chomsky). \"\"\"\n",
    "    def __init__(self, sigma: Alphabet, v: Alphabet, s: Var, r: List[Regle], nom=\"G\"):\n",
    "        \"\"\" Grammaire en forme de Chomsky :\n",
    "            - sigma : alphabet de production, type Alphabet,\n",
    "            - v : alphabet de travail, type Alphabet,\n",
    "            - s : symbol initial, type Var,\n",
    "            - r : liste de règles, type List[Regle].\n",
    "        \"\"\"\n",
    "        # On se contente de stocker les champs :\n",
    "        self.sigma = sigma\n",
    "        self.v = v\n",
    "        self.s = s\n",
    "        self.r = r\n",
    "        self.nom = nom\n",
    "        \n",
    "    def __str__(self) -> str:\n",
    "        \"\"\" Permet d'afficher une grammaire.\"\"\"\n",
    "        str_regles = ', '.join(\n",
    "            \"{} -> {}\".format(regle[0], ''.join(regle[1]) if regle[1] else 'ε')\n",
    "            for regle in self.r\n",
    "        )\n",
    "        return r\"\"\"Grammaire {} :\n",
    "    - Alphabet Σ = {},\n",
    "    - Non terminaux V = {},\n",
    "    - Symbole initial : '{}',\n",
    "    - Règles : {}.\"\"\".format(self.nom, set(self.sigma), set(self.v), self.s, str_regles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "78754350-e18a-4e1f-ad61-62ca80b13577"
    }
   },
   "source": [
    "### 2.1.3 Premier exemple de grammaire (non-Chomsky)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "f81db6b0-5909-4012-9172-5f8d69719308"
    }
   },
   "source": [
    "On commence avec un premier exemple basique, la grammaire $G_1$ avec pour seule règle : $S \\rightarrow aSb \\;|\\; \\varepsilon$.\n",
    "C'est la grammaire naturelle, bien formée, pour les mots de la forme $a^n b^n$ pour tout $n \\geq 0$.\n",
    "Cf. [cet exemple sur Wikipedia](https://fr.wikipedia.org/wiki/Grammaire_non_contextuelle#Exemple_1).\n",
    "Par contre, elle n'est pas en forme normale de Chomsky."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "nbpresent": {
     "id": "76f6562f-42fe-46ad-9428-e04c9715e2b9"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G1 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> aSb.\n"
     ]
    }
   ],
   "source": [
    "g1 = Grammaire(\n",
    "    ['a', 'b'],  # Alphabet de production\n",
    "    ['S'],       # Alphabet de travail\n",
    "    'S',         # Symbole initial (un seul)\n",
    "    [            # Règles\n",
    "        ('S', []),  # S -> ε\n",
    "        ('S', ['a', 'S', 'b']),  # S -> a S b\n",
    "    ],\n",
    "    nom=\"G1\"\n",
    ")\n",
    "print(g1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "c1a3f18e-6007-4803-8f1d-919099eb9d4d"
    }
   },
   "source": [
    "### 2.1.4 Second exemple de grammaire (non-Chomsky)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "7902e165-ed68-4295-81c6-d9cb677071f6"
    }
   },
   "source": [
    "Voici un autre exemple basique, la grammaire $G_2$ qui engendre les expressions arithmétiques\n",
    "en trois variables $x$, $y$ et $z$, correctement parenthésées.\n",
    "Une seule règle de production, ou une union de règle de production, suffit :\n",
    "    $$ S \\rightarrow x \\;|\\; y \\;|\\; z \\;|\\; S+S \\;|\\; S-S \\;|\\; S∗S \\;|\\; S/S \\;|\\; (S). $$\n",
    "\n",
    "Cf. [cet autre exemple sur Wikipedia](https://fr.wikipedia.org/wiki/Grammaire_non_contextuelle#Exemple_2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "nbpresent": {
     "id": "23c6f46c-01de-4de7-a493-c2c12b91705a"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G2 :\n",
      "    - Alphabet Σ = {'*', '/', 'z', 'y', '-', 'x', '(', ')', '+'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> x, S -> y, S -> z, S -> S+S, S -> S-S, S -> S*S, S -> S/S, S -> (S).\n"
     ]
    }
   ],
   "source": [
    "g2 = Grammaire(\n",
    "    ['x', 'y', 'z', '+', '-', '*', '/', '(', ')'],  # Alphabet de production\n",
    "    ['S'],  # Alphabet de travail\n",
    "    'S',    # Symbole initial (un seul)\n",
    "    [       # Règles\n",
    "        ('S', ['x']),            # S -> x\n",
    "        ('S', ['y']),            # S -> y\n",
    "        ('S', ['z']),            # S -> z\n",
    "        ('S', ['S', '+', 'S']),  # S -> S + S\n",
    "        ('S', ['S', '-', 'S']),  # S -> S - S\n",
    "        ('S', ['S', '*', 'S']),  # S -> S * S\n",
    "        ('S', ['S', '/', 'S']),  # S -> S / S\n",
    "        ('S', ['(', 'S', ')']),   # S -> (S)\n",
    "    ],\n",
    "    nom=\"G2\"\n",
    ")\n",
    "print(g2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "4d5849a2-1473-43cc-b262-f73fcc3c7fe9"
    }
   },
   "source": [
    "### 2.1.5 Dernier exemple de grammaire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "dfe894be-2610-444e-9c7c-3592c0fd387e"
    }
   },
   "source": [
    "Voici un dernier exemple, moins basique, la grammaire $G_3$ qui engendre des phrases \"simples\" (et très limitées) en anglais.\n",
    "[Inspirée de cet exemple sur Wikipedia (en anglais)](https://en.wikipedia.org/wiki/CYK_algorithm#Example).\n",
    "Cette grammaire $G_3$ est sous forme normale de Chomsky."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "nbpresent": {
     "id": "ab608e34-9e94-46d8-97a3-a16e11748e39"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G3 :\n",
      "    - Alphabet Σ = {'fish ', 'fork ', 'eats ', 'a ', 'she ', 'an ', 'sword ', 'ork ', 'with '},\n",
      "    - Non terminaux V = {'PP ', 'DetVo ', 'S', 'Det ', 'N ', 'P ', 'V ', 'NVo ', 'NP ', 'VP '},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> NP VP , VP  -> VP PP , VP  -> V NP , PP  -> P NP , NP  -> Det N , NP  -> DetVo NVo , VP  -> eats , NP  -> she , V  -> eats , P  -> with , N  -> fish , N  -> fork , N  -> sword , NVo  -> ork , Det  -> a , DetVo  -> an .\n"
     ]
    }
   ],
   "source": [
    "g3 = Grammaire(\n",
    "    # Alphabet de production, des vrais mots anglais (avec une espace pour que la phrase soit lisible\n",
    "    ['she ', 'eats ', 'with ', 'fish ', 'fork ', 'a ', 'an ', 'ork ', 'sword '],\n",
    "    # Alphabet de travail, des catégories de mots : V pour verbes, P pour pronom etc.\n",
    "    ['S', 'NP ', 'VP ', 'PP ', 'V ', 'Det ', 'DetVo ', 'N ', 'NVo ', 'P '],\n",
    "    # Det = a : déterminant\n",
    "    # DetVo = an : déterminant avant un nom commençant par une voyelle\n",
    "    # N = (fish, fork, sword) : un nom\n",
    "    # NVo = ork : un nom commençant par une voyelle\n",
    "    # NP = she | a (fish, fork, sword) | an ork : un sujet\n",
    "    # V = eats : verbe conjugué\n",
    "    # P = with : conjonction de coordination\n",
    "    # VP = eats : verbe conjugué suivi d'un objet\n",
    "    # PP : with NP : complément d'objet direct\n",
    "    'S',    # Symbole initial (un seul)\n",
    "    [       # Règles\n",
    "        # Règles de constuction de phrase\n",
    "        ( 'S',      ['NP ', 'VP '] ),      # 'S'  -> 'NP' 'VP'\n",
    "        ( 'VP ',    ['VP ', 'PP '] ),      # 'VP' -> 'VP' 'PP'\n",
    "        ( 'VP ',    ['V ', 'NP '] ),       # 'VP' -> 'V' 'NP'\n",
    "        ( 'PP ',    ['P ', 'NP '] ),       # 'PP' -> 'P' 'NP'\n",
    "        ( 'NP ',    ['Det ', 'N '] ),      # 'NP' -> 'Det' 'N'\n",
    "        ( 'NP ',    ['DetVo ', 'NVo '] ),  # 'NP' -> 'DetVo' 'NVo'\n",
    "        # Règles de création de mots\n",
    "        ( 'VP ',    ['eats '] ),   # 'VP'    -> 'eats '\n",
    "        ( 'NP ',    ['she '] ),    # 'NP'    -> 'she '\n",
    "        ( 'V ',     ['eats '] ),   # 'V'     -> 'eats '\n",
    "        ( 'P ',     ['with '] ),   # 'P'     -> 'with '\n",
    "        ( 'N ',     ['fish '] ),   # 'N'     -> 'fish '\n",
    "        ( 'N ',     ['fork '] ),   # 'N'     -> 'fork '\n",
    "        ( 'N ',     ['sword '] ),  # 'N'     -> 'sword '\n",
    "        ( 'NVo ',   ['ork '] ),    # 'NVo'   -> 'ork '\n",
    "        ( 'Det ',   ['a '] ),      # 'Det'   -> 'a '\n",
    "        ( 'DetVo ', ['an '] ),     # 'DetVo' -> 'an '\n",
    "    ],\n",
    "    nom=\"G3\"\n",
    ")\n",
    "print(g3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "93c8ccae-724e-4a0b-ae3b-d77a7686d50f"
    }
   },
   "source": [
    "Nous utiliserons ces exemples de grammaire plus tard, pour vérifier que nos fonctions sont correctement écrites.\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "8ba9e526-7b9d-46b8-aff5-c24770802e0b"
    }
   },
   "source": [
    "## 2.2 Vérifier qu'une grammaire est bien formée"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "a89bc86c-9498-4223-aca1-664c432e2fed"
    }
   },
   "source": [
    "On veut pouvoir vérifier qu'une grammaire $G$ (i.e., un objet instance de ``Grammaire``) est bien formée (cf. votre cours de langage formel pour une définition propre) :\n",
    "\n",
    "- $S$ doit être une variable de travail, i.e., $S \\in V$,\n",
    "- Les variables de production et les variables de travail doivent être distinctes, i.e., $\\Sigma \\cap V = \\emptyset$,\n",
    "- Pour chaque règle, $r = A \\rightarrow w$, les membres gauches des règles sont réduits à une seule variable de travail, et les membres droits sont des mots, vides ou constitués de variables de production ou de travail, i.e., $A \\in V$, et $w \\in (\\Sigma \\cup V)^{\\star}$,\n",
    "\n",
    "On vérifie ça facilement avec la fonction suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "nbpresent": {
     "id": "d11ac540-3961-4fe1-9e42-dcaed4f80ee4"
    }
   },
   "outputs": [],
   "source": [
    "def estBienFormee(self: Grammaire) -> bool:\n",
    "    \"\"\" Vérifie que G est bien formée. \"\"\"\n",
    "    sigma, v, s, regles = set(self.sigma), set(self.v), self.s, self.r\n",
    "    tests = [\n",
    "        s in v,  # s est bien une variable de travail\n",
    "        sigma.isdisjoint(v),  # Lettres et variables de travail sont disjointes\n",
    "        all(\n",
    "            regle[0] in v  # Les membres gauches de règles sont des variables\n",
    "            and  # Les membres droits de règles sont des variables ou des lettres\n",
    "            all(r in sigma | v for r in regle[1])\n",
    "            for regle in regles\n",
    "        )\n",
    "    ]\n",
    "    return all(tests)\n",
    "\n",
    "# On ajoute la fonction comme une méthode (au cas où...)\n",
    "Grammaire.estBienFormee = estBienFormee"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "nbpresent": {
     "id": "33675f93-4578-44b5-b7c3-cd58e0b6205f"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G1 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> aSb.\n",
      "La grammaire G1 est-elle bien formée ? True\n",
      "\n",
      "Grammaire G2 :\n",
      "    - Alphabet Σ = {'*', '/', 'z', 'y', '-', 'x', '(', ')', '+'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> x, S -> y, S -> z, S -> S+S, S -> S-S, S -> S*S, S -> S/S, S -> (S).\n",
      "La grammaire G2 est-elle bien formée ? True\n",
      "\n",
      "Grammaire G3 :\n",
      "    - Alphabet Σ = {'fish ', 'fork ', 'eats ', 'a ', 'she ', 'an ', 'sword ', 'ork ', 'with '},\n",
      "    - Non terminaux V = {'PP ', 'DetVo ', 'S', 'Det ', 'N ', 'P ', 'V ', 'NVo ', 'NP ', 'VP '},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> NP VP , VP  -> VP PP , VP  -> V NP , PP  -> P NP , NP  -> Det N , NP  -> DetVo NVo , VP  -> eats , NP  -> she , V  -> eats , P  -> with , N  -> fish , N  -> fork , N  -> sword , NVo  -> ork , Det  -> a , DetVo  -> an .\n",
      "La grammaire G3 est-elle bien formée ? True\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for g in [g1, g2, g3]:\n",
    "    print(g)\n",
    "    print(\"La grammaire\", g.nom, \"est-elle bien formée ?\", estBienFormee(g))\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "b06222f2-f0a6-483f-8b88-e7084f954d42"
    }
   },
   "source": [
    "On peut définir une autre grammaire qui n'est pas bien formée, pour voir.\n",
    "Cette grammaire $G_4$ engendre les mots de la forme $a^{n+k} b^n$ pour $n,k \\in \\mathbb{N}$, mais on lui donne une règle de dédoublement des $a$ : $a \\rightarrow a a$ (notez que $a$, une variable de production, est à gauche d'une règle)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "nbpresent": {
     "id": "afebb980-fd35-4b8c-9d9e-e33644b43915"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G4 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> aSb, a -> aa.\n",
      "La grammaire G4 est-elle bien formée ? False\n"
     ]
    }
   ],
   "source": [
    "g4 = Grammaire(\n",
    "    ['a', 'b'],  # Alphabet de production\n",
    "    ['S'],       # Alphabet de travail\n",
    "    'S',         # Symbole initial (un seul)\n",
    "    [            # Règles\n",
    "        ('S', []),               # S -> ε\n",
    "        ('S', ['a', 'S', 'b']),  # S -> a S b\n",
    "        ('a', ['a', 'a']),       # a -> a a, cette règle n'est pas en forme normale\n",
    "    ],\n",
    "    nom=\"G4\"\n",
    ")\n",
    "print(g4)\n",
    "print(\"La grammaire\", g4.nom, \"est-elle bien formée ?\", estBienFormee(g4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "92a7f470-cf9e-443a-9e4d-2dfdc60dab0a"
    }
   },
   "source": [
    "Juste par curiosité, la voici transformée pour devenir bien formée, ici on a juste eu besoin d'ajouter une variable de travail $A$ qui peut donner $a$ ou $A A$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "nbpresent": {
     "id": "5e3a665e-ff7b-4ec1-88b8-77f93147f76d"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G5 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S', 'A'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> ASb, A -> AA, A -> a.\n",
      "La grammaire G5 est-elle bien formée ? True\n"
     ]
    }
   ],
   "source": [
    "g5 = Grammaire(\n",
    "    ['a', 'b'],  # Alphabet de production\n",
    "    ['S', 'A'],  # Alphabet de travail\n",
    "    'S',         # Symbole initial (un seul)\n",
    "    [            # Règles\n",
    "        ('S', []),               # S -> ε\n",
    "        ('S', ['A', 'S', 'b']),  # S -> A S b\n",
    "        ('A', ['A', 'A']),       # A -> A A, voila comment on gère a -> a a\n",
    "        ('A', ['a']),            # A -> a\n",
    "    ],\n",
    "    nom=\"G5\"\n",
    ")\n",
    "print(g5)\n",
    "print(\"La grammaire\", g5.nom, \"est-elle bien formée ?\", estBienFormee(g5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "532339d5-5c9d-431d-812b-3d594e71870c"
    }
   },
   "source": [
    "## 2.3 Vérifier qu'une grammaire est en forme normale de Chomsky"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "737fc81b-be7b-484f-8323-da0f543bc541"
    }
   },
   "source": [
    "On veut maintenant pouvoir vérifier qu'une grammaire $G$ (i.e., un objet instance de ``Grammaire``) est bien en forme normale de Chomsky.\n",
    "En effet, l'algorithme CKY n'a aucune chance de fonctionner si la grammaire n'est pas sous la bonne forme.\n",
    "\n",
    "Pour que $G$ soit en forme normale de Chomsky :\n",
    "- elle doit d'abord être bien formée (cf. ci-dessus),\n",
    "- et chaque règle doit être\n",
    "   - soit de la forme $S \\rightarrow \\varepsilon$,\n",
    "   - soit de la forme $A \\rightarrow a$ pour $(A, a)$ dans $V \\times \\Sigma$,\n",
    "   - soit de la forme $A \\rightarrow B C$ pour $(A, B, C)$ dans $V^3$ (certains ouvrages demandent à ce qu'il n'y ait aucune production de $S$ le symbole initial, i.e., $B,C \\neq S$, mais ça ne change rien pour l'algorithme qu'on implémente plus bas).\n",
    "   \n",
    "On vérifie ça facilement, point par point, dans la fonction suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "nbpresent": {
     "id": "24c410d2-56f5-4c30-abd3-506afd8e9a06"
    }
   },
   "outputs": [],
   "source": [
    "def estChomsky(self: Grammaire) -> bool:\n",
    "    \"\"\" Vérifie que G est sous forme normale de Chomksy. \"\"\"\n",
    "    sigma, v, s, regles = set(self.sigma), set(self.v), self.s, self.r\n",
    "    estBienChomsky = all(\n",
    "        (   # S -> epsilon\n",
    "            regle[0] == s and not regle[1]\n",
    "        ) or (  # A -> a\n",
    "            len(regle[1]) == 1\n",
    "            and regle[1][0] in sigma  # a in Sigma\n",
    "        ) or (  # A -> B C\n",
    "            len(regle[1]) == 2\n",
    "            and regle[1][0] in v  # B in V, not Sigma\n",
    "            and regle[1][1] in v  # C in V, not Sigma\n",
    "        )\n",
    "        for regle in regles\n",
    "    )\n",
    "    return estBienChomsky and estBienFormee(self)\n",
    "\n",
    "# On ajoute la fonction comme une méthode (au cas où...)\n",
    "Grammaire.estChomsky = estChomsky"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "3323c87c-3015-46e9-a08f-9b197123ea54"
    }
   },
   "source": [
    "On peut tester avec les cinq grammaires definies plus haut ($G_1$, $G_2$, $G_3$, $G_4$, $G_5$).\n",
    "Seule la grammaire $G_3$ est de Chomsky."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "nbpresent": {
     "id": "a8f2efbb-f560-4e6c-8c9c-228fd8c3d0ca"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G1 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> aSb.\n",
      "La grammaire G1 est-elle de bien formée ? True\n",
      "La grammaire G1 est-elle de Chomsky ? False\n",
      "\n",
      "Grammaire G2 :\n",
      "    - Alphabet Σ = {'*', '/', 'z', 'y', '-', 'x', '(', ')', '+'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> x, S -> y, S -> z, S -> S+S, S -> S-S, S -> S*S, S -> S/S, S -> (S).\n",
      "La grammaire G2 est-elle de bien formée ? True\n",
      "La grammaire G2 est-elle de Chomsky ? False\n",
      "\n",
      "Grammaire G3 :\n",
      "    - Alphabet Σ = {'fish ', 'fork ', 'eats ', 'a ', 'she ', 'an ', 'sword ', 'ork ', 'with '},\n",
      "    - Non terminaux V = {'PP ', 'DetVo ', 'S', 'Det ', 'N ', 'P ', 'V ', 'NVo ', 'NP ', 'VP '},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> NP VP , VP  -> VP PP , VP  -> V NP , PP  -> P NP , NP  -> Det N , NP  -> DetVo NVo , VP  -> eats , NP  -> she , V  -> eats , P  -> with , N  -> fish , N  -> fork , N  -> sword , NVo  -> ork , Det  -> a , DetVo  -> an .\n",
      "La grammaire G3 est-elle de bien formée ? True\n",
      "La grammaire G3 est-elle de Chomsky ? True\n",
      "\n",
      "Grammaire G4 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> aSb, a -> aa.\n",
      "La grammaire G4 est-elle de bien formée ? False\n",
      "La grammaire G4 est-elle de Chomsky ? False\n",
      "\n",
      "Grammaire G5 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S', 'A'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> ASb, A -> AA, A -> a.\n",
      "La grammaire G5 est-elle de bien formée ? True\n",
      "La grammaire G5 est-elle de Chomsky ? False\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for g in [g1, g2, g3, g4, g5]:\n",
    "    print(g)\n",
    "    print(\"La grammaire\", g.nom, \"est-elle de bien formée ?\", estBienFormee(g))\n",
    "    print(\"La grammaire\", g.nom, \"est-elle de Chomsky ?\", estChomsky(g))\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "e4ba99dc-0283-4e95-a79a-fb015dac3272"
    }
   },
   "source": [
    "À la main, on peut transformer $G_5$ pour la mettre en forme de Chomsky (et après, on passe à CYK).\n",
    "Notez que cette transformation est automatique, elle est implémentée dans le cas general (d'une grammaire $G$ bien formée), ci-dessus en partie 5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "nbpresent": {
     "id": "8d550da7-ce2e-441a-b5ab-f10874825883"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G6 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S', 'A', 'T', 'B'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> AT, T -> SB, A -> AA, A -> a, B -> b.\n",
      "La grammaire G6 est-elle bien formée ? True\n",
      "La grammaire G6 est-elle de Chomsky ? True\n"
     ]
    }
   ],
   "source": [
    "g6 = Grammaire(\n",
    "    ['a', 'b'],            # Alphabet de production\n",
    "    ['S', 'T', 'A', 'B'],  # Alphabet de travail\n",
    "    'S',                   # Symbole initial (un seul)\n",
    "    [                      # Règles\n",
    "        ('S', []),               # S -> ε, on efface S si on veut produire le mot vide\n",
    "        # On coupe la règle S -> A S B en deux :\n",
    "        ('S', ['A', 'T']),       # S -> A T\n",
    "        ('T', ['S', 'B']),       # T -> S B\n",
    "        ('A', ['A', 'A']),       # A -> A A, voilà comment on gère a -> a a\n",
    "        # Production de lettres\n",
    "        ('A', ['a']),            # A -> a\n",
    "        ('B', ['b']),            # B -> b\n",
    "    ],\n",
    "    nom=\"G6\"\n",
    ")\n",
    "print(g6)\n",
    "print(\"La grammaire\", g6.nom, \"est-elle bien formée ?\", estBienFormee(g6))\n",
    "print(\"La grammaire\", g6.nom, \"est-elle de Chomsky ?\", estChomsky(g6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "1251164f-12db-4f25-8be3-f9673dff5224"
    }
   },
   "source": [
    "## 2.4 (enfin) L'algorithme de Cocke-Kasami-Younger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "2fc4b95c-7173-48bc-a321-132965860cf9"
    }
   },
   "source": [
    "On passe *enfin* à l'algorithme de Cocke-Kasami-Younger.\n",
    "\n",
    "L'algorithme va prendre une grammaire $G$, bien formée, de taille $|G|$ (definie comme la somme des longueurs de $\\Sigma$ et $V$ et la somme des tailles des règles), ainsi qu'un mot $w$ de taille $n = |w|$ (**attention**, ce n'est pas une ``str`` mais une liste de variables ``List[Var]``, i.e., une liste de ``str``).\n",
    "\n",
    "Le but est de vérifier si le mot $w$ peut être engendrée par la grammaire $G$, i.e., de déterminer si $w \\in L(G)$.\n",
    "Pour le détail de fonctionnement, cf. le code Python ci dessous, ou [la page Wikipedia](https://fr.wikipedia.org/wiki/Algorithme_de_Cocke-Younger-Kasami).\n",
    "\n",
    "L'algorithme aura :\n",
    "\n",
    "- une complexité en mémoire en $\\mathcal{O}(|G| + |w|^2)$,\n",
    "- une complexité en temps en $\\mathcal{O}(|G| \\times |w|^3)$, ce qui montrera que le problème du mot pour les grammaires en forme de Chomsky est dans $\\mathcal{P}$ (en temps polynomial, c'est déjà cool) et en temps raisonnable (cubique en $n = |w|$, c'est encore mieux !).\n",
    "\n",
    "On va utiliser une table de hachage ``E`` contiendra, à la fin du calcul, les $E_{i, j}$ définis par :\n",
    "$$ E_{i, j} := \\{ A \\in V : w[i, j] \\in L_G(A) \\}.$$\n",
    "Ou l'on a noté $w[i, j] = w_i \\dots w_j$ le sous-mot d'indices $i,\\dots,j$, et $L_G(A)$ le langage engendré par $G$ en partant du symbole $A$ (et pas du symbole initial $S$).\n",
    "\n",
    "*Note :* la table de hachage n'est pas vraiment requise, une liste de liste fonctionnerait aussi mais la notation en serait moins proche de celle utilisée en maths."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "nbpresent": {
     "id": "f5923095-60a8-4bee-99f9-4882995c47b4"
    }
   },
   "outputs": [],
   "source": [
    "def cocke_kasami_younger(self, w):\n",
    "    \"\"\" Vérifie si le mot w est dans L(G). \"\"\"\n",
    "    assert estChomsky(self), \"Erreur : {} n'est pas en forme de Chomsky, l'algorithme de Cocke-Kasami-Younger ne fonctionnera pas.\".format(self.nom)\n",
    "    sigma, v, s, regles = set(self.sigma), set(self.v), self.s, self.r\n",
    "    n = len(w)\n",
    "    E = dict()  # De taille n^2\n",
    "    # Cas special pour tester si le mot vide est dans L(G)\n",
    "    if n == 0:\n",
    "        return (s, []) in regles, E\n",
    "    # Boucle en O(n^2)\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            E[(i, j)] = set()\n",
    "    # Boucle en O(n x |G|)\n",
    "    for i in range(n):\n",
    "        for regle in regles:\n",
    "            # Si regle est de la forme : A -> a\n",
    "            if len(regle[1]) == 1:\n",
    "                A = regle[0]\n",
    "                a = regle[1][0]\n",
    "                if w[i] == a:  # Notez que c'est le seul moment ou utilise le mot w !\n",
    "                    E[(i, i)] = E[(i, i)] | {A}\n",
    "    # Boucle en O(n^3 x |G|)\n",
    "    for d in range(1, n):          # Longueur du morceau\n",
    "        for i in range(n - d):     # Début du morceau\n",
    "            j = i + d              # Fin du morceau, on regarde w[i]..w[j]\n",
    "            for k in range(i, j):  # Parcourt du morceau, ..w[k].., sans la fin\n",
    "                for regle in regles:\n",
    "                    # Si regle est de la forme A -> B C\n",
    "                    if len(regle[1]) == 2:\n",
    "                        A = regle[0]\n",
    "                        B, C = regle[1]\n",
    "                        if B in E[(i, k)] and C in E[(k + 1, j)]:\n",
    "                            E[(i, j)] = E[(i, j)] | {A}\n",
    "    # On a fini, il suffit maintenant d'utiliser la table créée par programmation dynamique\n",
    "    return s in E[(0, n - 1)], E\n",
    "\n",
    "# On ajoute la fonction comme une méthode (au cas où...)\n",
    "Grammaire.genere = cocke_kasami_younger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d1b05240-02ab-4500-b066-0c6402b6f904"
    }
   },
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "5773e8e4-8eea-46b9-8a93-24d0a49ef67b"
    }
   },
   "source": [
    "## 2.5 Exemples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "2d9326be-33da-4d10-b886-13e23c95ea30"
    }
   },
   "source": [
    "On présente ici des exemples d'utilisation de cette fonction ``cocke_kasami_younger`` avec les grammaires $G_i$ présentées plus haut et quelques examples de mots $w$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "nbpresent": {
     "id": "9dfc4bf1-c35a-43ba-a0b1-f5fa6c3bae7c"
    }
   },
   "outputs": [],
   "source": [
    "def testeMot(g, w):\n",
    "    \"\"\" Joli affichage pour un test \"\"\"\n",
    "    print(\"# Test si w in L(G) :\")\n",
    "    print(\"  Pour\", g.nom, \"et w =\", w)\n",
    "    estDansLG, E = cocke_kasami_younger(g, w)\n",
    "    if estDansLG:\n",
    "        print(\"  ==> Ce mot est bien engendré par G !\")\n",
    "    else:\n",
    "        print(\"  ==> Ce mot n'est pas engendré par G !\")\n",
    "    return estDansLG, E"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "c4c76082-22f2-41da-9be6-d692bf75fb7f"
    }
   },
   "source": [
    "### 2.5.1 Avec $G_3$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "nbpresent": {
     "id": "f11cc557-9a8c-43d9-8259-02de9950d273"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G3 :\n",
      "    - Alphabet Σ = {'fish ', 'fork ', 'eats ', 'a ', 'she ', 'an ', 'sword ', 'ork ', 'with '},\n",
      "    - Non terminaux V = {'PP ', 'DetVo ', 'S', 'Det ', 'N ', 'P ', 'V ', 'NVo ', 'NP ', 'VP '},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> NP VP , VP  -> VP PP , VP  -> V NP , PP  -> P NP , NP  -> Det N , NP  -> DetVo NVo , VP  -> eats , NP  -> she , V  -> eats , P  -> with , N  -> fish , N  -> fork , N  -> sword , NVo  -> ork , Det  -> a , DetVo  -> an .\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(g3)\n",
    "print(estChomsky(g3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "nbpresent": {
     "id": "ef2f9cfc-1edf-4d45-925f-1a0709592e2e"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G3 et w = ['she ', 'eats ', 'a ', 'fish ', 'with ', 'a ', 'fork ']\n",
      "  ==> Ce mot est bien engendré par G !\n"
     ]
    }
   ],
   "source": [
    "w1 = [ \"she \", \"eats \", \"a \", \"fish \", \"with \", \"a \", \"fork \" ]  # True\n",
    "estDansLG1, E1 = testeMot(g3, w1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "8119a069-284d-44b4-8734-49e9305d3356"
    }
   },
   "source": [
    "Pour cet exemple, on peut afficher la table ``E`` (en ne montrant que les cases qui ont un $E_{i, j}$ non-vide) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "nbpresent": {
     "id": "ff6fe115-4ffe-47b6-b50d-4c816e75c844"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(0, 0): {'NP '}, (0, 1): {'S'}, (0, 3): {'S'}, (0, 6): {'S'}, (1, 1): {'V ', 'VP '}, (1, 3): {'VP '}, (1, 6): {'VP '}, (2, 2): {'Det '}, (2, 3): {'NP '}, (3, 3): {'N '}, (4, 4): {'P '}, (4, 6): {'PP '}, (5, 5): {'Det '}, (5, 6): {'NP '}, (6, 6): {'N '}}\n"
     ]
    }
   ],
   "source": [
    "for k in E1.copy():\n",
    "    if k in E1 and not E1[k]:  # On retire les clés qui ont un E[(i, j)] vide\n",
    "        del(E1[k])\n",
    "print(E1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "65b58209-c5a4-4cea-95ec-727afa29f96e"
    }
   },
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "nbpresent": {
     "id": "9b75140e-97f5-420c-9416-2a26fc073568"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G3 et w = ['she ', 'attacks ', 'a ', 'fish ', 'with ', 'a ', 'fork ']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    }
   ],
   "source": [
    "w2 = [ \"she \", \"attacks \", \"a \", \"fish \", \"with \", \"a \", \"fork \" ]  # False\n",
    "estDansLG2, E2 = testeMot(g3, w2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "nbpresent": {
     "id": "4213cd21-6ae3-4806-a50c-e6e8897449b3"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G3 et w = ['she ', 'eats ', 'an ', 'ork ', 'with ', 'a ', 'sword ']\n",
      "  ==> Ce mot est bien engendré par G !\n"
     ]
    }
   ],
   "source": [
    "w3 = [ \"she \", \"eats \", \"an \", \"ork \", \"with \", \"a \", \"sword \" ]  # True\n",
    "estDansLG3, E3 = testeMot(g3, w3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "6c8e5dc3-8e39-4463-bb32-708931a9ac19"
    }
   },
   "source": [
    "D'autres exemples :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "nbpresent": {
     "id": "ef05902d-aa96-4f44-9138-0c82da8c9b27"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G3 et w = ['she ', 'eats ', 'an ', 'fish ', 'with ', 'a ', 'fork ']\n",
      "  ==> Ce mot n'est pas engendré par G !\n",
      "# Test si w in L(G) :\n",
      "  Pour G3 et w = ['she ', 'eat ', 'a ', 'fish ', 'with ', 'a ', 'fork ']\n",
      "  ==> Ce mot n'est pas engendré par G !\n",
      "# Test si w in L(G) :\n",
      "  Pour G3 et w = ['she ', 'eats ', 'a ', 'fish ', 'with ', 'a ', 'fish ', 'with ', 'a ', 'fish ', 'with ', 'a ', 'fish ', 'with ', 'a ', 'fish ']\n",
      "  ==> Ce mot est bien engendré par G !\n"
     ]
    }
   ],
   "source": [
    "w4 = [ \"she \", \"eats \", \"an \", \"fish \", \"with \", \"a \", \"fork \" ]  # False\n",
    "estDansLG4, E4 = testeMot(g3, w4)\n",
    "w5 = [ \"she \", \"eat \", \"a \", \"fish \", \"with \", \"a \", \"fork \" ]  # False\n",
    "estDansLG5, E5 = testeMot(g3, w5)\n",
    "w6 = [ \"she \", \"eats \", \"a \", \"fish \", \"with \", \"a \", \"fish \" , \"with \", \"a \", \"fish \" , \"with \", \"a \", \"fish \" , \"with \", \"a \", \"fish \" ]  # True\n",
    "estDansLG6, E6 = testeMot(g3, w6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "2609b145-67f9-4b81-a868-b1485626b70a"
    }
   },
   "source": [
    "### 2.5.2 Avec $G_6$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "nbpresent": {
     "id": "9625bf15-25ab-4a1f-8399-921b81aa315a"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G6 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S', 'A', 'T', 'B'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> AT, T -> SB, A -> AA, A -> a, B -> b.\n",
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = []\n",
      "  ==> Ce mot est bien engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(True, {})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = ['a', 'b']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(False, {(0, 0): {'A'}, (0, 1): set(), (1, 0): set(), (1, 1): {'B'}})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = ['a', 'a', 'a', 'b', 'b', 'b']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(False,\n",
       " {(0, 0): {'A'},\n",
       "  (0, 1): {'A'},\n",
       "  (0, 2): {'A'},\n",
       "  (0, 3): set(),\n",
       "  (0, 4): set(),\n",
       "  (0, 5): set(),\n",
       "  (1, 0): set(),\n",
       "  (1, 1): {'A'},\n",
       "  (1, 2): {'A'},\n",
       "  (1, 3): set(),\n",
       "  (1, 4): set(),\n",
       "  (1, 5): set(),\n",
       "  (2, 0): set(),\n",
       "  (2, 1): set(),\n",
       "  (2, 2): {'A'},\n",
       "  (2, 3): set(),\n",
       "  (2, 4): set(),\n",
       "  (2, 5): set(),\n",
       "  (3, 0): set(),\n",
       "  (3, 1): set(),\n",
       "  (3, 2): set(),\n",
       "  (3, 3): {'B'},\n",
       "  (3, 4): set(),\n",
       "  (3, 5): set(),\n",
       "  (4, 0): set(),\n",
       "  (4, 1): set(),\n",
       "  (4, 2): set(),\n",
       "  (4, 3): set(),\n",
       "  (4, 4): {'B'},\n",
       "  (4, 5): set(),\n",
       "  (5, 0): set(),\n",
       "  (5, 1): set(),\n",
       "  (5, 2): set(),\n",
       "  (5, 3): set(),\n",
       "  (5, 4): set(),\n",
       "  (5, 5): {'B'}})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = ['a', 'a', 'a', 'a', 'b', 'b', 'b']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(False,\n",
       " {(0, 0): {'A'},\n",
       "  (0, 1): {'A'},\n",
       "  (0, 2): {'A'},\n",
       "  (0, 3): {'A'},\n",
       "  (0, 4): set(),\n",
       "  (0, 5): set(),\n",
       "  (0, 6): set(),\n",
       "  (1, 0): set(),\n",
       "  (1, 1): {'A'},\n",
       "  (1, 2): {'A'},\n",
       "  (1, 3): {'A'},\n",
       "  (1, 4): set(),\n",
       "  (1, 5): set(),\n",
       "  (1, 6): set(),\n",
       "  (2, 0): set(),\n",
       "  (2, 1): set(),\n",
       "  (2, 2): {'A'},\n",
       "  (2, 3): {'A'},\n",
       "  (2, 4): set(),\n",
       "  (2, 5): set(),\n",
       "  (2, 6): set(),\n",
       "  (3, 0): set(),\n",
       "  (3, 1): set(),\n",
       "  (3, 2): set(),\n",
       "  (3, 3): {'A'},\n",
       "  (3, 4): set(),\n",
       "  (3, 5): set(),\n",
       "  (3, 6): set(),\n",
       "  (4, 0): set(),\n",
       "  (4, 1): set(),\n",
       "  (4, 2): set(),\n",
       "  (4, 3): set(),\n",
       "  (4, 4): {'B'},\n",
       "  (4, 5): set(),\n",
       "  (4, 6): set(),\n",
       "  (5, 0): set(),\n",
       "  (5, 1): set(),\n",
       "  (5, 2): set(),\n",
       "  (5, 3): set(),\n",
       "  (5, 4): set(),\n",
       "  (5, 5): {'B'},\n",
       "  (5, 6): set(),\n",
       "  (6, 0): set(),\n",
       "  (6, 1): set(),\n",
       "  (6, 2): set(),\n",
       "  (6, 3): set(),\n",
       "  (6, 4): set(),\n",
       "  (6, 5): set(),\n",
       "  (6, 6): {'B'}})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(False,\n",
       " {(0, 0): {'A'},\n",
       "  (0, 1): {'A'},\n",
       "  (0, 2): {'A'},\n",
       "  (0, 3): {'A'},\n",
       "  (0, 4): {'A'},\n",
       "  (0, 5): {'A'},\n",
       "  (0, 6): {'A'},\n",
       "  (0, 7): {'A'},\n",
       "  (0, 8): {'A'},\n",
       "  (0, 9): {'A'},\n",
       "  (0, 10): set(),\n",
       "  (0, 11): set(),\n",
       "  (0, 12): set(),\n",
       "  (0, 13): set(),\n",
       "  (0, 14): set(),\n",
       "  (0, 15): set(),\n",
       "  (1, 0): set(),\n",
       "  (1, 1): {'A'},\n",
       "  (1, 2): {'A'},\n",
       "  (1, 3): {'A'},\n",
       "  (1, 4): {'A'},\n",
       "  (1, 5): {'A'},\n",
       "  (1, 6): {'A'},\n",
       "  (1, 7): {'A'},\n",
       "  (1, 8): {'A'},\n",
       "  (1, 9): {'A'},\n",
       "  (1, 10): set(),\n",
       "  (1, 11): set(),\n",
       "  (1, 12): set(),\n",
       "  (1, 13): set(),\n",
       "  (1, 14): set(),\n",
       "  (1, 15): set(),\n",
       "  (2, 0): set(),\n",
       "  (2, 1): set(),\n",
       "  (2, 2): {'A'},\n",
       "  (2, 3): {'A'},\n",
       "  (2, 4): {'A'},\n",
       "  (2, 5): {'A'},\n",
       "  (2, 6): {'A'},\n",
       "  (2, 7): {'A'},\n",
       "  (2, 8): {'A'},\n",
       "  (2, 9): {'A'},\n",
       "  (2, 10): set(),\n",
       "  (2, 11): set(),\n",
       "  (2, 12): set(),\n",
       "  (2, 13): set(),\n",
       "  (2, 14): set(),\n",
       "  (2, 15): set(),\n",
       "  (3, 0): set(),\n",
       "  (3, 1): set(),\n",
       "  (3, 2): set(),\n",
       "  (3, 3): {'A'},\n",
       "  (3, 4): {'A'},\n",
       "  (3, 5): {'A'},\n",
       "  (3, 6): {'A'},\n",
       "  (3, 7): {'A'},\n",
       "  (3, 8): {'A'},\n",
       "  (3, 9): {'A'},\n",
       "  (3, 10): set(),\n",
       "  (3, 11): set(),\n",
       "  (3, 12): set(),\n",
       "  (3, 13): set(),\n",
       "  (3, 14): set(),\n",
       "  (3, 15): set(),\n",
       "  (4, 0): set(),\n",
       "  (4, 1): set(),\n",
       "  (4, 2): set(),\n",
       "  (4, 3): set(),\n",
       "  (4, 4): {'A'},\n",
       "  (4, 5): {'A'},\n",
       "  (4, 6): {'A'},\n",
       "  (4, 7): {'A'},\n",
       "  (4, 8): {'A'},\n",
       "  (4, 9): {'A'},\n",
       "  (4, 10): set(),\n",
       "  (4, 11): set(),\n",
       "  (4, 12): set(),\n",
       "  (4, 13): set(),\n",
       "  (4, 14): set(),\n",
       "  (4, 15): set(),\n",
       "  (5, 0): set(),\n",
       "  (5, 1): set(),\n",
       "  (5, 2): set(),\n",
       "  (5, 3): set(),\n",
       "  (5, 4): set(),\n",
       "  (5, 5): {'A'},\n",
       "  (5, 6): {'A'},\n",
       "  (5, 7): {'A'},\n",
       "  (5, 8): {'A'},\n",
       "  (5, 9): {'A'},\n",
       "  (5, 10): set(),\n",
       "  (5, 11): set(),\n",
       "  (5, 12): set(),\n",
       "  (5, 13): set(),\n",
       "  (5, 14): set(),\n",
       "  (5, 15): set(),\n",
       "  (6, 0): set(),\n",
       "  (6, 1): set(),\n",
       "  (6, 2): set(),\n",
       "  (6, 3): set(),\n",
       "  (6, 4): set(),\n",
       "  (6, 5): set(),\n",
       "  (6, 6): {'A'},\n",
       "  (6, 7): {'A'},\n",
       "  (6, 8): {'A'},\n",
       "  (6, 9): {'A'},\n",
       "  (6, 10): set(),\n",
       "  (6, 11): set(),\n",
       "  (6, 12): set(),\n",
       "  (6, 13): set(),\n",
       "  (6, 14): set(),\n",
       "  (6, 15): set(),\n",
       "  (7, 0): set(),\n",
       "  (7, 1): set(),\n",
       "  (7, 2): set(),\n",
       "  (7, 3): set(),\n",
       "  (7, 4): set(),\n",
       "  (7, 5): set(),\n",
       "  (7, 6): set(),\n",
       "  (7, 7): {'A'},\n",
       "  (7, 8): {'A'},\n",
       "  (7, 9): {'A'},\n",
       "  (7, 10): set(),\n",
       "  (7, 11): set(),\n",
       "  (7, 12): set(),\n",
       "  (7, 13): set(),\n",
       "  (7, 14): set(),\n",
       "  (7, 15): set(),\n",
       "  (8, 0): set(),\n",
       "  (8, 1): set(),\n",
       "  (8, 2): set(),\n",
       "  (8, 3): set(),\n",
       "  (8, 4): set(),\n",
       "  (8, 5): set(),\n",
       "  (8, 6): set(),\n",
       "  (8, 7): set(),\n",
       "  (8, 8): {'A'},\n",
       "  (8, 9): {'A'},\n",
       "  (8, 10): set(),\n",
       "  (8, 11): set(),\n",
       "  (8, 12): set(),\n",
       "  (8, 13): set(),\n",
       "  (8, 14): set(),\n",
       "  (8, 15): set(),\n",
       "  (9, 0): set(),\n",
       "  (9, 1): set(),\n",
       "  (9, 2): set(),\n",
       "  (9, 3): set(),\n",
       "  (9, 4): set(),\n",
       "  (9, 5): set(),\n",
       "  (9, 6): set(),\n",
       "  (9, 7): set(),\n",
       "  (9, 8): set(),\n",
       "  (9, 9): {'A'},\n",
       "  (9, 10): set(),\n",
       "  (9, 11): set(),\n",
       "  (9, 12): set(),\n",
       "  (9, 13): set(),\n",
       "  (9, 14): set(),\n",
       "  (9, 15): set(),\n",
       "  (10, 0): set(),\n",
       "  (10, 1): set(),\n",
       "  (10, 2): set(),\n",
       "  (10, 3): set(),\n",
       "  (10, 4): set(),\n",
       "  (10, 5): set(),\n",
       "  (10, 6): set(),\n",
       "  (10, 7): set(),\n",
       "  (10, 8): set(),\n",
       "  (10, 9): set(),\n",
       "  (10, 10): {'B'},\n",
       "  (10, 11): set(),\n",
       "  (10, 12): set(),\n",
       "  (10, 13): set(),\n",
       "  (10, 14): set(),\n",
       "  (10, 15): set(),\n",
       "  (11, 0): set(),\n",
       "  (11, 1): set(),\n",
       "  (11, 2): set(),\n",
       "  (11, 3): set(),\n",
       "  (11, 4): set(),\n",
       "  (11, 5): set(),\n",
       "  (11, 6): set(),\n",
       "  (11, 7): set(),\n",
       "  (11, 8): set(),\n",
       "  (11, 9): set(),\n",
       "  (11, 10): set(),\n",
       "  (11, 11): {'B'},\n",
       "  (11, 12): set(),\n",
       "  (11, 13): set(),\n",
       "  (11, 14): set(),\n",
       "  (11, 15): set(),\n",
       "  (12, 0): set(),\n",
       "  (12, 1): set(),\n",
       "  (12, 2): set(),\n",
       "  (12, 3): set(),\n",
       "  (12, 4): set(),\n",
       "  (12, 5): set(),\n",
       "  (12, 6): set(),\n",
       "  (12, 7): set(),\n",
       "  (12, 8): set(),\n",
       "  (12, 9): set(),\n",
       "  (12, 10): set(),\n",
       "  (12, 11): set(),\n",
       "  (12, 12): {'B'},\n",
       "  (12, 13): set(),\n",
       "  (12, 14): set(),\n",
       "  (12, 15): set(),\n",
       "  (13, 0): set(),\n",
       "  (13, 1): set(),\n",
       "  (13, 2): set(),\n",
       "  (13, 3): set(),\n",
       "  (13, 4): set(),\n",
       "  (13, 5): set(),\n",
       "  (13, 6): set(),\n",
       "  (13, 7): set(),\n",
       "  (13, 8): set(),\n",
       "  (13, 9): set(),\n",
       "  (13, 10): set(),\n",
       "  (13, 11): set(),\n",
       "  (13, 12): set(),\n",
       "  (13, 13): {'B'},\n",
       "  (13, 14): set(),\n",
       "  (13, 15): set(),\n",
       "  (14, 0): set(),\n",
       "  (14, 1): set(),\n",
       "  (14, 2): set(),\n",
       "  (14, 3): set(),\n",
       "  (14, 4): set(),\n",
       "  (14, 5): set(),\n",
       "  (14, 6): set(),\n",
       "  (14, 7): set(),\n",
       "  (14, 8): set(),\n",
       "  (14, 9): set(),\n",
       "  (14, 10): set(),\n",
       "  (14, 11): set(),\n",
       "  (14, 12): set(),\n",
       "  (14, 13): set(),\n",
       "  (14, 14): {'B'},\n",
       "  (14, 15): set(),\n",
       "  (15, 0): set(),\n",
       "  (15, 1): set(),\n",
       "  (15, 2): set(),\n",
       "  (15, 3): set(),\n",
       "  (15, 4): set(),\n",
       "  (15, 5): set(),\n",
       "  (15, 6): set(),\n",
       "  (15, 7): set(),\n",
       "  (15, 8): set(),\n",
       "  (15, 9): set(),\n",
       "  (15, 10): set(),\n",
       "  (15, 11): set(),\n",
       "  (15, 12): set(),\n",
       "  (15, 13): set(),\n",
       "  (15, 14): set(),\n",
       "  (15, 15): {'B'}})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = ['a', 'b', 'a']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(False,\n",
       " {(0, 0): {'A'},\n",
       "  (0, 1): set(),\n",
       "  (0, 2): set(),\n",
       "  (1, 0): set(),\n",
       "  (1, 1): {'B'},\n",
       "  (1, 2): set(),\n",
       "  (2, 0): set(),\n",
       "  (2, 1): set(),\n",
       "  (2, 2): {'A'}})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = ['a', 'a', 'a', 'b', 'b', 'b', 'b']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(False,\n",
       " {(0, 0): {'A'},\n",
       "  (0, 1): {'A'},\n",
       "  (0, 2): {'A'},\n",
       "  (0, 3): set(),\n",
       "  (0, 4): set(),\n",
       "  (0, 5): set(),\n",
       "  (0, 6): set(),\n",
       "  (1, 0): set(),\n",
       "  (1, 1): {'A'},\n",
       "  (1, 2): {'A'},\n",
       "  (1, 3): set(),\n",
       "  (1, 4): set(),\n",
       "  (1, 5): set(),\n",
       "  (1, 6): set(),\n",
       "  (2, 0): set(),\n",
       "  (2, 1): set(),\n",
       "  (2, 2): {'A'},\n",
       "  (2, 3): set(),\n",
       "  (2, 4): set(),\n",
       "  (2, 5): set(),\n",
       "  (2, 6): set(),\n",
       "  (3, 0): set(),\n",
       "  (3, 1): set(),\n",
       "  (3, 2): set(),\n",
       "  (3, 3): {'B'},\n",
       "  (3, 4): set(),\n",
       "  (3, 5): set(),\n",
       "  (3, 6): set(),\n",
       "  (4, 0): set(),\n",
       "  (4, 1): set(),\n",
       "  (4, 2): set(),\n",
       "  (4, 3): set(),\n",
       "  (4, 4): {'B'},\n",
       "  (4, 5): set(),\n",
       "  (4, 6): set(),\n",
       "  (5, 0): set(),\n",
       "  (5, 1): set(),\n",
       "  (5, 2): set(),\n",
       "  (5, 3): set(),\n",
       "  (5, 4): set(),\n",
       "  (5, 5): {'B'},\n",
       "  (5, 6): set(),\n",
       "  (6, 0): set(),\n",
       "  (6, 1): set(),\n",
       "  (6, 2): set(),\n",
       "  (6, 3): set(),\n",
       "  (6, 4): set(),\n",
       "  (6, 5): set(),\n",
       "  (6, 6): {'B'}})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = ['c']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(False, {(0, 0): set()})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Test si w in L(G) :\n",
      "  Pour G6 et w = ['a', 'a', 'a', 'c']\n",
      "  ==> Ce mot n'est pas engendré par G !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(False,\n",
       " {(0, 0): {'A'},\n",
       "  (0, 1): {'A'},\n",
       "  (0, 2): {'A'},\n",
       "  (0, 3): set(),\n",
       "  (1, 0): set(),\n",
       "  (1, 1): {'A'},\n",
       "  (1, 2): {'A'},\n",
       "  (1, 3): set(),\n",
       "  (2, 0): set(),\n",
       "  (2, 1): set(),\n",
       "  (2, 2): {'A'},\n",
       "  (2, 3): set(),\n",
       "  (3, 0): set(),\n",
       "  (3, 1): set(),\n",
       "  (3, 2): set(),\n",
       "  (3, 3): set()})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(g6)\n",
    "for w in [ [], ['a', 'b'], ['a', 'a', 'a', 'b', 'b', 'b'],  # True, True, True\n",
    "          ['a', 'a', 'a', 'a', 'b', 'b', 'b'],  # True\n",
    "          ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b'],  # True\n",
    "          ['a', 'b', 'a'], ['a', 'a', 'a', 'b', 'b', 'b', 'b'],  # False, False\n",
    "          ['c'], ['a', 'a', 'a', 'c'],  # False, False\n",
    "         ]:\n",
    "    testeMot(g6, w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "eeb5fbb8-ad49-4129-b380-e1778d23f0b4"
    }
   },
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "f117119d-b1bd-4ba7-84b7-788e6a1a181b"
    }
   },
   "source": [
    "## 2.6 Mise en forme normale de Chomsky *(bonus)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "4290aeb6-33da-4e25-934c-67389557731a"
    }
   },
   "source": [
    "On pourrait aussi implémenter la mise en forme normale de Chomsky, comme exposée et prouvée dans le développement.\n",
    "\n",
    "La preuve faite dans le développement garantit que la fonction ci-dessous transforme une grammaire $G$ en grammaire équivalente $G'$, avec l'éventuelle perte du mot vide $\\varepsilon$ :\n",
    "$$ L(G') = L(G) \\setminus \\{ \\varepsilon \\}. $$\n",
    "\n",
    "L'algorithme aura :\n",
    "\n",
    "- une complexité en mémoire en $\\mathcal{O}(|G|)$,\n",
    "- une complexité en temps en $\\mathcal{O}(|G| |\\Sigma_G|)$.\n",
    "\n",
    "C'est un algorithme en deux étapes :\n",
    "\n",
    "1. D'abord, on transforme $G$ en $G'$ : on ajoute des variables de travail pour chaque lettre de production, $V_a \\in V$ pour $a \\in \\Sigma$, on remplace chaque $a$ dans des membres gauches de règles par la nouvelle $V_a$, et ensuite on ajoute des règles de production de lettre $V_a \\rightarrow a$ dans $R$,\n",
    "2. Ensuite, $G''$ est obtenue en découpant les règles de $G$ qui sont de tailles $> 2$ : une règle $S \\rightarrow S_1 \\dots S_n$ devient $n-1$ règles : $S \\rightarrow S_1 S_2'$, $S_i' \\rightarrow S_i S_{i+1}'$ (pour $i = 2,\\dots,n - 2$), et $S_{n-1}' \\rightarrow S_{n-1} S_n$. Il faut aussi ajouter toutes ces nouvelles variables $S_i'$ (en s'assurant qu'elles sont uniques, pour chaque règle), on ajoute pour cela le numéro de la règle : $S_i'=$ ``A'_k`` pour la ``k`` -ième règle et le symbole $S_i=$ ``A``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "nbpresent": {
     "id": "dd178a86-cdc5-40f7-99b8-59d33415cb8d"
    }
   },
   "outputs": [],
   "source": [
    "def miseChomsky(self):\n",
    "    \"\"\" Met en forme normale de Chomsky la grammaire self, qui doit être bien formée.\n",
    "    \n",
    "    - On suppose que l'alphabet Sigma est dans {a,..,z},\n",
    "    - On suppose que l'alphabet v est dans {A,..,Z}.\n",
    "    \"\"\"\n",
    "    assert estBienFormee(self), \"Erreur : {} n'est pas en bien formée, la mise en forme normale de Chomsky ne fonctionnera pas.\".format(self.nom)\n",
    "    sigma, v, s, regles = set(self.sigma), set(self.v), self.s, self.r\n",
    "    if estChomsky(self):\n",
    "        print(\"Info : la grammaire {} est déjà en forme normale de Chomsky, il n'y a rien à faire.\".format(self.nom))\n",
    "        return Grammaire(sigma, v, s, regles)\n",
    "    assert sigma < set(chr(i) for i in range(ord('a'), ord('z') + 1)), \"Erreur : {} n'a pas ses lettres de production Sigma dans 'a'..'z' ...\".format(self.nom)\n",
    "    assert v < set(chr(i) for i in range(ord('A'), ord('Z') + 1)), \"Erreur : {} n'a pas ses lettres de travail V dans 'A'..'Z' ...\".format(self.nom)\n",
    "\n",
    "    # Algorithme en deux étapes, G --> G', puis G' --> G''\n",
    "    \n",
    "    # 1. G --> G' : On ajoute des variables de travail et on substitue a -> V_a dans les autres règles\n",
    "    # On pose les attributs de G', qui vont être changés\n",
    "    sigma2 = list(sigma)\n",
    "    v2 = set(v)\n",
    "    s2 = s\n",
    "    regles2 = []\n",
    "\n",
    "    V_ = lambda a: 'V_{}'.format(a)\n",
    "    for a in sigma:\n",
    "        v2.add(V_(a))\n",
    "        regles2.append([V_(a), [a]])  # Ajout de la règle V_a -> a (production de la lettre correspondante)\n",
    "    substitutionLettre = lambda b: V_(b) if (b in sigma) else b\n",
    "    substitutionMot = lambda lb: [substitutionLettre(b) for b in lb]\n",
    "    for regle in regles:\n",
    "        S = regle[0]\n",
    "        w = regle[1]\n",
    "        if len(w) >= 2:  # Si ce n'est pas une règle A -> epsilon\n",
    "            regles2.append([S, substitutionMot(w)])\n",
    "        else:  # Ici on devrait garder la possibilte de creer le mot vide\n",
    "            regles2.append([S, w])\n",
    "    nom2 = self.nom + \"'\"\n",
    "    print(Grammaire(list(sigma2), list(v2), s2, regles2, nom=nom2))\n",
    "    \n",
    "    # 2. G' --> G'' : On découpe les règles A -> A1..An qui ont n > 2\n",
    "    # On pose les attributs de G'', qui vont être changés\n",
    "    sigma3 = list(sigma2)\n",
    "    v3 = set(v2)\n",
    "    s3 = s2\n",
    "    regles3 = []\n",
    "    \n",
    "    for k, regle in enumerate(regles2):\n",
    "        S = regle[0]\n",
    "        w = regle[1]  # w = S1 .. Sn\n",
    "        n = len(w)\n",
    "        if n > 2:\n",
    "            prime = lambda Si: \"%s'_%d\" % (Si, k)  # Ajouter le k dans le nom assure que les nouvelles variables de travail sont toutes uniques\n",
    "            # Premiere règle : S -> S_1 S'_2\n",
    "            regles3.append([S, [w[0], prime(w[1])]])\n",
    "            v3.add(prime(w[1]))\n",
    "            for i in range(1, len(w) - 2):\n",
    "                # Pour chaque règle intermédiaire : S'_i -> S_i  S'_{i+1}\n",
    "                regles3.append([prime(w[i]), [w[i], prime(w[i + 1])]])\n",
    "                v3.add(prime(w[i]))\n",
    "                v3.add(prime(w[i + 1]))\n",
    "            # Dernière règle : S'_{n-1} -> S_{n-1} S_n\n",
    "            regles3.append([prime(w[n - 2]), [w[n - 2], w[n - 1]]])\n",
    "            v3.add(prime(w[n - 2]))\n",
    "        else:\n",
    "            regles3.append([S, w])\n",
    "    # Terminé\n",
    "    nom3 = self.nom + \"''\"\n",
    "    return Grammaire(list(sigma3), list(v3), s3, regles3, nom=nom3)\n",
    "\n",
    "# On ajoute la fonction comme une méthode (au cas où...)\n",
    "Grammaire.miseChomsky = miseChomsky"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "ac1e7550-4c59-4052-9815-e57cbdd37dee"
    }
   },
   "source": [
    "### 2.6.1 Exemple pour $G_1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "nbpresent": {
     "id": "9a23d60c-82eb-497e-a2f6-5a7fae98839a"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G1 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> aSb.\n",
      "\n",
      "(Non) La grammaire G1 est-elle de Chomsky ? False\n",
      "\n",
      "On essaie de la mettre sous forme normale de Chomksy...\n",
      "\n",
      "Grammaire G1' :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S', 'V_a', 'V_b'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : V_b -> b, V_a -> a, S -> ε, S -> V_aSV_b.\n",
      "Grammaire G1'' :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S', 'V_a', \"S'_3\", 'V_b'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : V_b -> b, V_a -> a, S -> ε, S -> V_aS'_3, S'_3 -> SV_b.\n",
      "\n",
      "  ==> La grammaire G1'' est-elle de Chomsky ? True\n"
     ]
    }
   ],
   "source": [
    "print(g1)\n",
    "print(\"\\n(Non) La grammaire\", g1.nom, \"est-elle de Chomsky ?\", estChomsky(g1))\n",
    "print(\"\\nOn essaie de la mettre sous forme normale de Chomksy...\\n\")\n",
    "g1_Chom = miseChomsky(g1)\n",
    "print(g1_Chom)\n",
    "print(\"\\n  ==> La grammaire\", g1_Chom.nom, \"est-elle de Chomsky ?\", estChomsky(g1_Chom))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "ade465ca-80a7-45a8-a507-b12316f31994"
    }
   },
   "source": [
    "### 2.6.2 Exemple pour $G_6$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "nbpresent": {
     "id": "16c2a9b2-acdc-458d-872f-474686ffd1c7"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammaire G5 :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S', 'A'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : S -> ε, S -> ASb, A -> AA, A -> a.\n",
      "\n",
      "(Non) La grammaire G5 est-elle de Chomsky ? False\n",
      "\n",
      "On essaie de la mettre sous forme normale de Chomksy...\n",
      "\n",
      "Grammaire G5' :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'S', 'V_a', 'A', 'V_b'},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : V_b -> b, V_a -> a, S -> ε, S -> ASV_b, A -> AA, A -> a.\n",
      "Grammaire G5'' :\n",
      "    - Alphabet Σ = {'b', 'a'},\n",
      "    - Non terminaux V = {'V_b', 'S', 'A', 'V_a', \"S'_3\"},\n",
      "    - Symbole initial : 'S',\n",
      "    - Règles : V_b -> b, V_a -> a, S -> ε, S -> AS'_3, S'_3 -> SV_b, A -> AA, A -> a.\n",
      "\n",
      "  ==> La grammaire G5'' est-elle de Chomsky ? True\n"
     ]
    }
   ],
   "source": [
    "print(g5)\n",
    "print(\"\\n(Non) La grammaire\", g5.nom, \"est-elle de Chomsky ?\", estChomsky(g5))\n",
    "print(\"\\nOn essaie de la mettre sous forme normale de Chomksy...\\n\")\n",
    "g5_Chom = miseChomsky(g5)\n",
    "print(g5_Chom)\n",
    "print(\"\\n  ==> La grammaire\", g5_Chom.nom, \"est-elle de Chomsky ?\", estChomsky(g5_Chom))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "55b060c3-5d0a-419a-b2d1-39ec92eb2fee"
    }
   },
   "source": [
    "----\n",
    "\n",
    "> *C'est tout pour aujourd'hui les amis !*\n",
    "> [Allez voir d'autres notebooks](https://github.com/Naereen/notebooks/tree/master/agreg) si vous voulez."
   ]
  }
 ],
 "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.6.6"
  },
  "nbpresent": {
   "slides": {
    "024a184d-f5a3-4a85-9473-da1dea41c8c6": {
     "id": "024a184d-f5a3-4a85-9473-da1dea41c8c6",
     "prev": "a48fa9ba-d6ba-42bf-9cdd-4b34c3729f5e",
     "regions": {
      "40736ce7-0648-466a-8219-42560e36e168": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "afebb980-fd35-4b8c-9d9e-e33644b43915",
        "part": "whole"
       },
       "id": "40736ce7-0648-466a-8219-42560e36e168"
      }
     }
    },
    "0328b7d6-7612-4703-b2a1-982600114627": {
     "id": "0328b7d6-7612-4703-b2a1-982600114627",
     "prev": "3e62eadf-d8f4-4623-8350-13b654221a61",
     "regions": {
      "5edeb35f-803e-44f5-8d0e-5fce5e99a749": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "c1a3f18e-6007-4803-8f1d-919099eb9d4d",
        "part": "whole"
       },
       "id": "5edeb35f-803e-44f5-8d0e-5fce5e99a749"
      }
     }
    },
    "0482321c-c7ad-4ae3-90b3-314947d36c30": {
     "id": "0482321c-c7ad-4ae3-90b3-314947d36c30",
     "prev": "ccd7f428-e390-46e4-af07-61ddf2f62581",
     "regions": {
      "a8b8ece2-0539-4a76-9744-b5c705f72ced": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "d11ac540-3961-4fe1-9e42-dcaed4f80ee4",
        "part": "whole"
       },
       "id": "a8b8ece2-0539-4a76-9744-b5c705f72ced"
      }
     }
    },
    "06194ea7-51cd-4aed-8513-cf743994e82c": {
     "id": "06194ea7-51cd-4aed-8513-cf743994e82c",
     "prev": "51e6169e-50b0-4f51-86ab-a5f111f14635",
     "regions": {
      "2287d24c-aa8c-4ec3-b485-a56e56c0fa0e": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "f117119d-b1bd-4ba7-84b7-788e6a1a181b",
        "part": "whole"
       },
       "id": "2287d24c-aa8c-4ec3-b485-a56e56c0fa0e"
      }
     }
    },
    "08c1c0c4-9cc6-40e7-a45b-583488648fa1": {
     "id": "08c1c0c4-9cc6-40e7-a45b-583488648fa1",
     "prev": "78963353-6e7f-4596-afbc-3b50435a281f",
     "regions": {
      "1f6b6dfd-dae0-4fcb-8d9d-1c51129944dd": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "ef05902d-aa96-4f44-9138-0c82da8c9b27",
        "part": "whole"
       },
       "id": "1f6b6dfd-dae0-4fcb-8d9d-1c51129944dd"
      }
     }
    },
    "0cda7ef7-232e-4e56-b86e-033967af2dc4": {
     "id": "0cda7ef7-232e-4e56-b86e-033967af2dc4",
     "prev": "b319b0e7-3a72-43e4-a4df-bde2f4b7bfa7",
     "regions": {
      "73bff5fc-c933-4eec-853b-e0295c64b41f": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "24c410d2-56f5-4c30-abd3-506afd8e9a06",
        "part": "whole"
       },
       "id": "73bff5fc-c933-4eec-853b-e0295c64b41f"
      }
     }
    },
    "0d27e3ea-f68a-4b49-89ab-fd86c0feca48": {
     "id": "0d27e3ea-f68a-4b49-89ab-fd86c0feca48",
     "prev": "cfc89203-a0f3-4b77-8614-4255433674b1",
     "regions": {
      "ee046c20-ffd2-4c47-a4db-64acd922adc1": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "5e3a665e-ff7b-4ec1-88b8-77f93147f76d",
        "part": "whole"
       },
       "id": "ee046c20-ffd2-4c47-a4db-64acd922adc1"
      }
     }
    },
    "11d0ae16-2cb5-4bd0-9cf2-54280b921f92": {
     "id": "11d0ae16-2cb5-4bd0-9cf2-54280b921f92",
     "prev": "8816919e-38e3-4be0-9d88-3e25a0eeebd0",
     "regions": {
      "2e0d8598-1f64-42d2-8666-974a389944bf": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "16c2a9b2-acdc-458d-872f-474686ffd1c7",
        "part": "whole"
       },
       "id": "2e0d8598-1f64-42d2-8666-974a389944bf"
      }
     }
    },
    "192b0ef2-85b0-4571-aec5-06b14e045021": {
     "id": "192b0ef2-85b0-4571-aec5-06b14e045021",
     "prev": "748e0b6e-f064-4c36-82c0-d5812b84c847",
     "regions": {
      "da0c6e68-3fc7-4d5f-a724-a1fde5b0431e": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "ef2f9cfc-1edf-4d45-925f-1a0709592e2e",
        "part": "whole"
       },
       "id": "da0c6e68-3fc7-4d5f-a724-a1fde5b0431e"
      }
     }
    },
    "1b553148-4e15-4f04-95a0-a96522ec7d53": {
     "id": "1b553148-4e15-4f04-95a0-a96522ec7d53",
     "prev": "ac83755f-6c9c-4eff-bde3-7fd89fac3d94",
     "regions": {
      "ec13b7e1-abaa-4863-930f-3a1420d09b28": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4d5849a2-1473-43cc-b262-f73fcc3c7fe9",
        "part": "whole"
       },
       "id": "ec13b7e1-abaa-4863-930f-3a1420d09b28"
      }
     }
    },
    "1de3e0d2-96fa-47bb-8173-5bb3ac9d0b43": {
     "id": "1de3e0d2-96fa-47bb-8173-5bb3ac9d0b43",
     "prev": null,
     "regions": {
      "3f02a964-e1a0-46d2-bd70-e9d454f9a030": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "dea75246-a31b-40b4-a49d-b9afe6eee2ee",
        "part": "whole"
       },
       "id": "3f02a964-e1a0-46d2-bd70-e9d454f9a030"
      }
     },
     "theme": null
    },
    "1e998cf7-4e3b-4262-ac18-91e572b6ef7d": {
     "id": "1e998cf7-4e3b-4262-ac18-91e572b6ef7d",
     "prev": "3ec7beb3-5982-4bdc-a4c4-874061465a3f",
     "regions": {
      "f3ab77dc-2c14-41b8-a006-af4709b8aa8e": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "ac1e7550-4c59-4052-9815-e57cbdd37dee",
        "part": "whole"
       },
       "id": "f3ab77dc-2c14-41b8-a006-af4709b8aa8e"
      }
     }
    },
    "21a56f52-a12e-4dc1-8729-0738cf031afe": {
     "id": "21a56f52-a12e-4dc1-8729-0738cf031afe",
     "prev": "2db44f00-9303-422e-bcd1-27dfd08f0887",
     "regions": {
      "510df7fe-98c8-4abe-85e7-91a196ddd044": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "9625bf15-25ab-4a1f-8399-921b81aa315a",
        "part": "whole"
       },
       "id": "510df7fe-98c8-4abe-85e7-91a196ddd044"
      }
     }
    },
    "228f720e-84a2-4678-9b1b-852e8130f277": {
     "id": "228f720e-84a2-4678-9b1b-852e8130f277",
     "prev": "4308e353-33c2-4043-97ff-e599fa4497ff",
     "regions": {
      "2b7da23b-8d1d-4055-b4fd-6beaf529bf67": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "aa8251b1-61e4-4914-9ad1-e66efd88b21f",
        "part": "whole"
       },
       "id": "2b7da23b-8d1d-4055-b4fd-6beaf529bf67"
      }
     }
    },
    "25d0391b-d01d-41d3-a5ca-59415b427620": {
     "id": "25d0391b-d01d-41d3-a5ca-59415b427620",
     "prev": "de94994c-2a6e-4e26-88a1-2144056eceea",
     "regions": {
      "7c595312-9c8d-4415-9c90-8877f5f543af": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "977443a2-4e87-43f0-8198-65a8a02d55a4",
        "part": "whole"
       },
       "id": "7c595312-9c8d-4415-9c90-8877f5f543af"
      }
     }
    },
    "2db44f00-9303-422e-bcd1-27dfd08f0887": {
     "id": "2db44f00-9303-422e-bcd1-27dfd08f0887",
     "prev": "08c1c0c4-9cc6-40e7-a45b-583488648fa1",
     "regions": {
      "4624d250-6e6f-4788-8070-720fe67966b8": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "2609b145-67f9-4b81-a868-b1485626b70a",
        "part": "whole"
       },
       "id": "4624d250-6e6f-4788-8070-720fe67966b8"
      }
     }
    },
    "2e8144c8-8d17-42f4-8eb7-92f3f1b1be8a": {
     "id": "2e8144c8-8d17-42f4-8eb7-92f3f1b1be8a",
     "prev": "192b0ef2-85b0-4571-aec5-06b14e045021",
     "regions": {
      "12c5faa4-18d4-4dbc-86fb-aeaf140a2db1": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "8119a069-284d-44b4-8734-49e9305d3356",
        "part": "whole"
       },
       "id": "12c5faa4-18d4-4dbc-86fb-aeaf140a2db1"
      }
     }
    },
    "337b14d7-fea5-43cd-a825-38f17119bece": {
     "id": "337b14d7-fea5-43cd-a825-38f17119bece",
     "prev": "6c9a8a64-6039-4aa1-baa8-f0e2cc14b066",
     "regions": {
      "263a4b08-7aa3-4109-b107-2ff2a708bbbe": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "78754350-e18a-4e1f-ad61-62ca80b13577",
        "part": "whole"
       },
       "id": "263a4b08-7aa3-4109-b107-2ff2a708bbbe"
      }
     }
    },
    "34e5dc94-7b12-4fa3-a438-5564243c1944": {
     "id": "34e5dc94-7b12-4fa3-a438-5564243c1944",
     "prev": "d1e2f9c4-744b-42a6-b190-ac7d755e4b95",
     "regions": {
      "cc891ca1-2a43-4fd2-b57f-5e221643abb9": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "49566064-31f5-48d8-9843-4cdc6e3ef152",
        "part": "whole"
       },
       "id": "cc891ca1-2a43-4fd2-b57f-5e221643abb9"
      }
     }
    },
    "38366a36-b291-4435-8b61-45939de9271c": {
     "id": "38366a36-b291-4435-8b61-45939de9271c",
     "prev": "0328b7d6-7612-4703-b2a1-982600114627",
     "regions": {
      "fc6a1e44-5d84-4bd4-8ba7-105f92a70e86": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "7902e165-ed68-4295-81c6-d9cb677071f6",
        "part": "whole"
       },
       "id": "fc6a1e44-5d84-4bd4-8ba7-105f92a70e86"
      }
     }
    },
    "38b77f60-427d-43f7-913a-a9c0ccd11cfb": {
     "id": "38b77f60-427d-43f7-913a-a9c0ccd11cfb",
     "prev": "3c06aa7f-2ded-433e-90d4-43714752c48b",
     "regions": {
      "9ebbf63f-fcdb-4708-b9e8-0e77a30925b1": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "1251164f-12db-4f25-8be3-f9673dff5224",
        "part": "whole"
       },
       "id": "9ebbf63f-fcdb-4708-b9e8-0e77a30925b1"
      }
     }
    },
    "3c06aa7f-2ded-433e-90d4-43714752c48b": {
     "id": "3c06aa7f-2ded-433e-90d4-43714752c48b",
     "prev": "c8b8f370-e8a7-4e0d-9980-3a732e7a10d7",
     "regions": {
      "e7a0d506-3594-4646-ad17-462a07ef8211": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "8d550da7-ce2e-441a-b5ab-f10874825883",
        "part": "whole"
       },
       "id": "e7a0d506-3594-4646-ad17-462a07ef8211"
      }
     }
    },
    "3e62eadf-d8f4-4623-8350-13b654221a61": {
     "id": "3e62eadf-d8f4-4623-8350-13b654221a61",
     "prev": "8f8eb981-6025-4fcf-a059-31081891a005",
     "regions": {
      "92e79e51-9e3a-4e60-8d64-6b1111a2e995": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "76f6562f-42fe-46ad-9428-e04c9715e2b9",
        "part": "whole"
       },
       "id": "92e79e51-9e3a-4e60-8d64-6b1111a2e995"
      }
     }
    },
    "3ec7beb3-5982-4bdc-a4c4-874061465a3f": {
     "id": "3ec7beb3-5982-4bdc-a4c4-874061465a3f",
     "prev": "db018a31-7f8b-4680-b47a-4a63f1b99eaa",
     "regions": {
      "40612cd4-f6d2-49f2-a872-0d1878b24ddf": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "dd178a86-cdc5-40f7-99b8-59d33415cb8d",
        "part": "whole"
       },
       "id": "40612cd4-f6d2-49f2-a872-0d1878b24ddf"
      }
     }
    },
    "4308e353-33c2-4043-97ff-e599fa4497ff": {
     "id": "4308e353-33c2-4043-97ff-e599fa4497ff",
     "prev": "9bc0fe08-9fe7-46c6-af09-26252d60578b",
     "regions": {
      "775c3a73-bd09-44c3-995e-f6d8c8d5b8d6": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "eadf8257-9a0e-4406-9455-5b82921f0457",
        "part": "whole"
       },
       "id": "775c3a73-bd09-44c3-995e-f6d8c8d5b8d6"
      }
     }
    },
    "49946442-2ac9-4b98-8fa9-9a1b4483b6ad": {
     "id": "49946442-2ac9-4b98-8fa9-9a1b4483b6ad",
     "prev": "34e5dc94-7b12-4fa3-a438-5564243c1944",
     "regions": {
      "8c945463-a72b-42e9-903b-668fd37f0799": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "9b3d1cdf-ca96-42cc-988b-be3a8a4715d9",
        "part": "whole"
       },
       "id": "8c945463-a72b-42e9-903b-668fd37f0799"
      }
     }
    },
    "4c6180fd-5191-4e82-bf98-d61194a72fc4": {
     "id": "4c6180fd-5191-4e82-bf98-d61194a72fc4",
     "prev": "79a41456-d88f-4084-8ed5-069cb49a2359",
     "regions": {
      "efb8d913-1296-41b7-96bd-f18581b503f4": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "aa98b297-0aa0-4ca7-b9ec-64c271212a60",
        "part": "whole"
       },
       "id": "efb8d913-1296-41b7-96bd-f18581b503f4"
      }
     }
    },
    "4c863375-81c0-405c-82cd-3dc163b4eb4c": {
     "id": "4c863375-81c0-405c-82cd-3dc163b4eb4c",
     "prev": "8b7f021c-1e1b-41d3-9ea8-1b2821582f58",
     "regions": {
      "0ce4d06a-7a8f-49dc-bf4e-26a540a7ddb2": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "93c8ccae-724e-4a0b-ae3b-d77a7686d50f",
        "part": "whole"
       },
       "id": "0ce4d06a-7a8f-49dc-bf4e-26a540a7ddb2"
      }
     }
    },
    "5124a426-eba1-4696-892d-c43ff84c0d8c": {
     "id": "5124a426-eba1-4696-892d-c43ff84c0d8c",
     "prev": "d6e93343-286f-49e0-b738-19baf3942ac2",
     "regions": {
      "e5bd920e-92aa-4112-9784-32f5b56e1154": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "f5923095-60a8-4bee-99f9-4882995c47b4",
        "part": "whole"
       },
       "id": "e5bd920e-92aa-4112-9784-32f5b56e1154"
      }
     }
    },
    "51e6169e-50b0-4f51-86ab-a5f111f14635": {
     "id": "51e6169e-50b0-4f51-86ab-a5f111f14635",
     "prev": "21a56f52-a12e-4dc1-8729-0738cf031afe",
     "regions": {
      "ddb5590b-a7f2-4494-8b03-5d421b451e33": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "eeb5fbb8-ad49-4129-b380-e1778d23f0b4",
        "part": "whole"
       },
       "id": "ddb5590b-a7f2-4494-8b03-5d421b451e33"
      }
     }
    },
    "53cda4a3-b880-42cf-9284-f4f3fad77257": {
     "id": "53cda4a3-b880-42cf-9284-f4f3fad77257",
     "prev": "0d27e3ea-f68a-4b49-89ab-fd86c0feca48",
     "regions": {
      "0053cc9d-a157-45c1-a565-4824dea03b0d": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "532339d5-5c9d-431d-812b-3d594e71870c",
        "part": "whole"
       },
       "id": "0053cc9d-a157-45c1-a565-4824dea03b0d"
      }
     }
    },
    "541e5a25-e82f-48f8-b28e-242e506acffe": {
     "id": "541e5a25-e82f-48f8-b28e-242e506acffe",
     "prev": "1e998cf7-4e3b-4262-ac18-91e572b6ef7d",
     "regions": {
      "2d7402c5-668f-4f05-aea7-1b9ded0900cc": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "9a23d60c-82eb-497e-a2f6-5a7fae98839a",
        "part": "whole"
       },
       "id": "2d7402c5-668f-4f05-aea7-1b9ded0900cc"
      }
     }
    },
    "590eeca5-f978-4386-8dfa-2fa04734f122": {
     "id": "590eeca5-f978-4386-8dfa-2fa04734f122",
     "prev": "5124a426-eba1-4696-892d-c43ff84c0d8c",
     "regions": {
      "69b171e5-e332-4cd8-9e1c-7c0cb9eeecde": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "d1b05240-02ab-4500-b066-0c6402b6f904",
        "part": "whole"
       },
       "id": "69b171e5-e332-4cd8-9e1c-7c0cb9eeecde"
      }
     }
    },
    "6253a88b-f5c4-4bf8-ab68-cecac0697c33": {
     "id": "6253a88b-f5c4-4bf8-ab68-cecac0697c33",
     "prev": "0482321c-c7ad-4ae3-90b3-314947d36c30",
     "regions": {
      "00dbf440-17b2-4f96-be62-8e3f35a3caf4": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "33675f93-4578-44b5-b7c3-cd58e0b6205f",
        "part": "whole"
       },
       "id": "00dbf440-17b2-4f96-be62-8e3f35a3caf4"
      }
     }
    },
    "6c9a8a64-6039-4aa1-baa8-f0e2cc14b066": {
     "id": "6c9a8a64-6039-4aa1-baa8-f0e2cc14b066",
     "prev": "4c6180fd-5191-4e82-bf98-d61194a72fc4",
     "regions": {
      "0c95a2a7-5242-4b49-9f94-590dd825f1a6": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "90271656-b57e-408d-b001-5f689f7ec7ae",
        "part": "whole"
       },
       "id": "0c95a2a7-5242-4b49-9f94-590dd825f1a6"
      }
     }
    },
    "6d003971-1a11-4e26-a00a-7ba20c36f240": {
     "id": "6d003971-1a11-4e26-a00a-7ba20c36f240",
     "prev": "a185be58-5fb5-4dbc-9b0b-fba7fb3c4f0c",
     "regions": {
      "ae366838-2f1c-4cdf-bb80-fd9c76427ce5": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "9471cb9a-937d-4f95-9f54-260b3b2e4da3",
        "part": "whole"
       },
       "id": "ae366838-2f1c-4cdf-bb80-fd9c76427ce5"
      }
     }
    },
    "6f920e38-9cb4-4d91-a0c4-e1f999736374": {
     "id": "6f920e38-9cb4-4d91-a0c4-e1f999736374",
     "prev": "78b135dd-06b5-40a3-8641-7b12d852b418",
     "regions": {
      "dd11ee8e-34cf-446f-95a3-44721d52b97b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "9b75140e-97f5-420c-9416-2a26fc073568",
        "part": "whole"
       },
       "id": "dd11ee8e-34cf-446f-95a3-44721d52b97b"
      }
     }
    },
    "746c8133-9bf7-431b-947a-8195cb97342d": {
     "id": "746c8133-9bf7-431b-947a-8195cb97342d",
     "prev": "bf51ee24-ed36-4250-9bf0-6b69ecbdc74e",
     "regions": {
      "3714c216-0450-4b6c-a0d6-28eb5f0716da": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "67357bc2-f510-485b-a17d-fd89b46bbaf7",
        "part": "whole"
       },
       "id": "3714c216-0450-4b6c-a0d6-28eb5f0716da"
      }
     }
    },
    "748e0b6e-f064-4c36-82c0-d5812b84c847": {
     "id": "748e0b6e-f064-4c36-82c0-d5812b84c847",
     "prev": "91be8f45-be68-46b3-9f82-2af92971f184",
     "regions": {
      "92ee1e9d-5d29-4849-aa02-9b837ee969c2": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "f11cc557-9a8c-43d9-8259-02de9950d273",
        "part": "whole"
       },
       "id": "92ee1e9d-5d29-4849-aa02-9b837ee969c2"
      }
     }
    },
    "76b6de76-8b05-4900-b047-8800ada5021a": {
     "id": "76b6de76-8b05-4900-b047-8800ada5021a",
     "prev": "746c8133-9bf7-431b-947a-8195cb97342d",
     "regions": {
      "c544a12e-0ee1-4f81-b662-620ff3a3657a": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "1da0f4ab-ccfc-412f-9efa-e7520d73a821",
        "part": "whole"
       },
       "id": "c544a12e-0ee1-4f81-b662-620ff3a3657a"
      }
     }
    },
    "78963353-6e7f-4596-afbc-3b50435a281f": {
     "id": "78963353-6e7f-4596-afbc-3b50435a281f",
     "prev": "a7a2ba69-c9e9-4728-98ad-ee072d9b11ff",
     "regions": {
      "75b8e003-e5b2-415f-ac03-8279d684939d": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "6c8e5dc3-8e39-4463-bb32-708931a9ac19",
        "part": "whole"
       },
       "id": "75b8e003-e5b2-415f-ac03-8279d684939d"
      }
     }
    },
    "78b135dd-06b5-40a3-8641-7b12d852b418": {
     "id": "78b135dd-06b5-40a3-8641-7b12d852b418",
     "prev": "ab03671a-9ee7-4bcf-8ab1-a434abf03528",
     "regions": {
      "b33ec547-76ac-4dc5-b3c1-15e174ec19bb": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "65b58209-c5a4-4cea-95ec-727afa29f96e",
        "part": "whole"
       },
       "id": "b33ec547-76ac-4dc5-b3c1-15e174ec19bb"
      }
     }
    },
    "79a41456-d88f-4084-8ed5-069cb49a2359": {
     "id": "79a41456-d88f-4084-8ed5-069cb49a2359",
     "prev": "9e26c2ac-faab-49df-a251-f7be6094a42c",
     "regions": {
      "142ed0b6-adae-4c51-92db-27ae0c51ce77": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "a1f2c855-d249-45fd-a621-65f5d25aedd9",
        "part": "whole"
       },
       "id": "142ed0b6-adae-4c51-92db-27ae0c51ce77"
      }
     }
    },
    "8676be22-3bfe-4c88-8800-b6dd119b5b17": {
     "id": "8676be22-3bfe-4c88-8800-b6dd119b5b17",
     "prev": "11d0ae16-2cb5-4bd0-9cf2-54280b921f92",
     "regions": {
      "dfca7e64-6dbe-4f81-aa4d-98c7ffccc70b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "55b060c3-5d0a-419a-b2d1-39ec92eb2fee",
        "part": "whole"
       },
       "id": "dfca7e64-6dbe-4f81-aa4d-98c7ffccc70b"
      }
     }
    },
    "8816919e-38e3-4be0-9d88-3e25a0eeebd0": {
     "id": "8816919e-38e3-4be0-9d88-3e25a0eeebd0",
     "prev": "541e5a25-e82f-48f8-b28e-242e506acffe",
     "regions": {
      "e49115ab-62f0-4537-a970-99de2489276f": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "ade465ca-80a7-45a8-a507-b12316f31994",
        "part": "whole"
       },
       "id": "e49115ab-62f0-4537-a970-99de2489276f"
      }
     }
    },
    "887f762e-9e54-4b5a-a002-5244dcb55d4d": {
     "id": "887f762e-9e54-4b5a-a002-5244dcb55d4d",
     "prev": "ff7a9b95-4459-41ec-8123-31b17477083b",
     "regions": {
      "28da8752-ceb4-41db-8e31-abdb72e7d473": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "9dfc4bf1-c35a-43ba-a0b1-f5fa6c3bae7c",
        "part": "whole"
       },
       "id": "28da8752-ceb4-41db-8e31-abdb72e7d473"
      }
     }
    },
    "8aacb149-61ee-4937-9eab-ec9db74da7ef": {
     "id": "8aacb149-61ee-4937-9eab-ec9db74da7ef",
     "prev": "1b553148-4e15-4f04-95a0-a96522ec7d53",
     "regions": {
      "e8f88cb4-30eb-44ea-bebd-113af9ac512b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "dfe894be-2610-444e-9c7c-3592c0fd387e",
        "part": "whole"
       },
       "id": "e8f88cb4-30eb-44ea-bebd-113af9ac512b"
      }
     }
    },
    "8b7f021c-1e1b-41d3-9ea8-1b2821582f58": {
     "id": "8b7f021c-1e1b-41d3-9ea8-1b2821582f58",
     "prev": "8aacb149-61ee-4937-9eab-ec9db74da7ef",
     "regions": {
      "fb2d8a90-a64c-404b-85e9-02cef25e2d7c": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "ab608e34-9e94-46d8-97a3-a16e11748e39",
        "part": "whole"
       },
       "id": "fb2d8a90-a64c-404b-85e9-02cef25e2d7c"
      }
     }
    },
    "8f8eb981-6025-4fcf-a059-31081891a005": {
     "id": "8f8eb981-6025-4fcf-a059-31081891a005",
     "prev": "337b14d7-fea5-43cd-a825-38f17119bece",
     "regions": {
      "bed8f65a-3162-490e-a6fd-9aed41957b2d": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "f81db6b0-5909-4012-9172-5f8d69719308",
        "part": "whole"
       },
       "id": "bed8f65a-3162-490e-a6fd-9aed41957b2d"
      }
     }
    },
    "8fe938e1-038b-48e3-ab24-36f8a8cef44a": {
     "id": "8fe938e1-038b-48e3-ab24-36f8a8cef44a",
     "prev": "590eeca5-f978-4386-8dfa-2fa04734f122",
     "regions": {
      "05fcdb24-11f3-4cb5-9ba5-6955e8fd7e86": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "5773e8e4-8eea-46b9-8a93-24d0a49ef67b",
        "part": "whole"
       },
       "id": "05fcdb24-11f3-4cb5-9ba5-6955e8fd7e86"
      }
     }
    },
    "91be8f45-be68-46b3-9f82-2af92971f184": {
     "id": "91be8f45-be68-46b3-9f82-2af92971f184",
     "prev": "887f762e-9e54-4b5a-a002-5244dcb55d4d",
     "regions": {
      "28407747-c3f7-4285-b812-8a27825c80ff": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "c4c76082-22f2-41da-9be6-d692bf75fb7f",
        "part": "whole"
       },
       "id": "28407747-c3f7-4285-b812-8a27825c80ff"
      }
     }
    },
    "9bc0fe08-9fe7-46c6-af09-26252d60578b": {
     "id": "9bc0fe08-9fe7-46c6-af09-26252d60578b",
     "prev": "b1c4a6c5-2871-4df9-a1a0-53004d56b4b2",
     "regions": {
      "dcd0a375-ca21-4b46-923a-53f7c9979119": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "588b818a-344d-44f3-910f-8b094ab72da0",
        "part": "whole"
       },
       "id": "dcd0a375-ca21-4b46-923a-53f7c9979119"
      }
     }
    },
    "9d2408fe-76a1-4506-8c0b-94ae3f9059b5": {
     "id": "9d2408fe-76a1-4506-8c0b-94ae3f9059b5",
     "prev": "0cda7ef7-232e-4e56-b86e-033967af2dc4",
     "regions": {
      "51d46c5e-a90f-433c-a762-fca6019f68b3": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "3323c87c-3015-46e9-a08f-9b197123ea54",
        "part": "whole"
       },
       "id": "51d46c5e-a90f-433c-a762-fca6019f68b3"
      }
     }
    },
    "9e26c2ac-faab-49df-a251-f7be6094a42c": {
     "id": "9e26c2ac-faab-49df-a251-f7be6094a42c",
     "prev": "6d003971-1a11-4e26-a00a-7ba20c36f240",
     "regions": {
      "a3eca349-cc83-4f0b-9136-af80e15c5c2c": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "609def09-9448-4ad3-ab50-ab5b76700114",
        "part": "whole"
       },
       "id": "a3eca349-cc83-4f0b-9136-af80e15c5c2c"
      }
     }
    },
    "a185be58-5fb5-4dbc-9b0b-fba7fb3c4f0c": {
     "id": "a185be58-5fb5-4dbc-9b0b-fba7fb3c4f0c",
     "prev": "228f720e-84a2-4678-9b1b-852e8130f277",
     "regions": {
      "f2040fb2-6047-4ca5-bab8-13dc37f828a3": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "7acecf25-b05e-42f7-9269-1ea5ba9e5265",
        "part": "whole"
       },
       "id": "f2040fb2-6047-4ca5-bab8-13dc37f828a3"
      }
     }
    },
    "a48fa9ba-d6ba-42bf-9cdd-4b34c3729f5e": {
     "id": "a48fa9ba-d6ba-42bf-9cdd-4b34c3729f5e",
     "prev": "6253a88b-f5c4-4bf8-ab68-cecac0697c33",
     "regions": {
      "cd5174a6-cb5f-4b26-a441-bf444e378b97": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "b06222f2-f0a6-483f-8b88-e7084f954d42",
        "part": "whole"
       },
       "id": "cd5174a6-cb5f-4b26-a441-bf444e378b97"
      }
     }
    },
    "a7a2ba69-c9e9-4728-98ad-ee072d9b11ff": {
     "id": "a7a2ba69-c9e9-4728-98ad-ee072d9b11ff",
     "prev": "6f920e38-9cb4-4d91-a0c4-e1f999736374",
     "regions": {
      "bd4556f1-5280-4915-a8a6-10c135b8abfe": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4213cd21-6ae3-4806-a50c-e6e8897449b3",
        "part": "whole"
       },
       "id": "bd4556f1-5280-4915-a8a6-10c135b8abfe"
      }
     }
    },
    "ab03671a-9ee7-4bcf-8ab1-a434abf03528": {
     "id": "ab03671a-9ee7-4bcf-8ab1-a434abf03528",
     "prev": "2e8144c8-8d17-42f4-8eb7-92f3f1b1be8a",
     "regions": {
      "b5df22e4-82df-45cd-9a57-46a807861ba5": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "ff6fe115-4ffe-47b6-b50d-4c816e75c844",
        "part": "whole"
       },
       "id": "b5df22e4-82df-45cd-9a57-46a807861ba5"
      }
     }
    },
    "ac83755f-6c9c-4eff-bde3-7fd89fac3d94": {
     "id": "ac83755f-6c9c-4eff-bde3-7fd89fac3d94",
     "prev": "38366a36-b291-4435-8b61-45939de9271c",
     "regions": {
      "43dd87fc-85d6-4dfe-8480-0651eea0e598": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "23c6f46c-01de-4de7-a493-c2c12b91705a",
        "part": "whole"
       },
       "id": "43dd87fc-85d6-4dfe-8480-0651eea0e598"
      }
     }
    },
    "b1c4a6c5-2871-4df9-a1a0-53004d56b4b2": {
     "id": "b1c4a6c5-2871-4df9-a1a0-53004d56b4b2",
     "prev": "76b6de76-8b05-4900-b047-8800ada5021a",
     "regions": {
      "b6801aba-674c-4544-b30b-dac83cf874dc": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "221b1aa3-999b-46bd-9ef6-ac240ccded3f",
        "part": "whole"
       },
       "id": "b6801aba-674c-4544-b30b-dac83cf874dc"
      }
     }
    },
    "b319b0e7-3a72-43e4-a4df-bde2f4b7bfa7": {
     "id": "b319b0e7-3a72-43e4-a4df-bde2f4b7bfa7",
     "prev": "53cda4a3-b880-42cf-9284-f4f3fad77257",
     "regions": {
      "7d64769d-e89a-4a11-979d-d9dc9211b167": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "737fc81b-be7b-484f-8323-da0f543bc541",
        "part": "whole"
       },
       "id": "7d64769d-e89a-4a11-979d-d9dc9211b167"
      }
     }
    },
    "bf51ee24-ed36-4250-9bf0-6b69ecbdc74e": {
     "id": "bf51ee24-ed36-4250-9bf0-6b69ecbdc74e",
     "prev": "c6257dee-ad20-4707-a2e5-c50cf72c7dcf",
     "regions": {
      "fde9d489-2f8c-4669-a995-90abc7387389": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "981227ac-e731-447f-8fe9-b25e4e546547",
        "part": "whole"
       },
       "id": "fde9d489-2f8c-4669-a995-90abc7387389"
      }
     }
    },
    "c6257dee-ad20-4707-a2e5-c50cf72c7dcf": {
     "id": "c6257dee-ad20-4707-a2e5-c50cf72c7dcf",
     "prev": "25d0391b-d01d-41d3-a5ca-59415b427620",
     "regions": {
      "c972da75-73c9-4aa6-830a-115c9c693a81": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "7999839d-b7e5-43d6-8ede-6765f12a8b3c",
        "part": "whole"
       },
       "id": "c972da75-73c9-4aa6-830a-115c9c693a81"
      }
     }
    },
    "c8b8f370-e8a7-4e0d-9980-3a732e7a10d7": {
     "id": "c8b8f370-e8a7-4e0d-9980-3a732e7a10d7",
     "prev": "d1656010-3069-44f1-a856-0c29de4cf794",
     "regions": {
      "2c89d110-a7e2-498b-9add-66aeda5352a3": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "e4ba99dc-0283-4e95-a79a-fb015dac3272",
        "part": "whole"
       },
       "id": "2c89d110-a7e2-498b-9add-66aeda5352a3"
      }
     }
    },
    "ccd7f428-e390-46e4-af07-61ddf2f62581": {
     "id": "ccd7f428-e390-46e4-af07-61ddf2f62581",
     "prev": "eb8f41e6-5cb1-4461-90ef-494bafdc2e40",
     "regions": {
      "404ef428-6e1c-44ce-95a7-d2317baf7c3e": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "a89bc86c-9498-4223-aca1-664c432e2fed",
        "part": "whole"
       },
       "id": "404ef428-6e1c-44ce-95a7-d2317baf7c3e"
      }
     }
    },
    "cfc89203-a0f3-4b77-8614-4255433674b1": {
     "id": "cfc89203-a0f3-4b77-8614-4255433674b1",
     "prev": "024a184d-f5a3-4a85-9473-da1dea41c8c6",
     "regions": {
      "7e56860f-d6fb-4f25-81ef-6d42b89e18c3": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "92a7f470-cf9e-443a-9e4d-2dfdc60dab0a",
        "part": "whole"
       },
       "id": "7e56860f-d6fb-4f25-81ef-6d42b89e18c3"
      }
     }
    },
    "d1656010-3069-44f1-a856-0c29de4cf794": {
     "id": "d1656010-3069-44f1-a856-0c29de4cf794",
     "prev": "9d2408fe-76a1-4506-8c0b-94ae3f9059b5",
     "regions": {
      "c10ed1e8-d5c8-42a9-b92c-4c9852e38484": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "a8f2efbb-f560-4e6c-8c9c-228fd8c3d0ca",
        "part": "whole"
       },
       "id": "c10ed1e8-d5c8-42a9-b92c-4c9852e38484"
      }
     }
    },
    "d1e2f9c4-744b-42a6-b190-ac7d755e4b95": {
     "id": "d1e2f9c4-744b-42a6-b190-ac7d755e4b95",
     "prev": "1de3e0d2-96fa-47bb-8173-5bb3ac9d0b43",
     "regions": {
      "e8ed4df7-fc1d-4e6f-87a4-e63f06476d3c": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "69c52735-d8a8-451b-93bb-eac98efd50ca",
        "part": "whole"
       },
       "id": "e8ed4df7-fc1d-4e6f-87a4-e63f06476d3c"
      }
     }
    },
    "d6e93343-286f-49e0-b738-19baf3942ac2": {
     "id": "d6e93343-286f-49e0-b738-19baf3942ac2",
     "prev": "38b77f60-427d-43f7-913a-a9c0ccd11cfb",
     "regions": {
      "dd0f9f13-89ad-47f2-841e-668f49b66bf8": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "2fc4b95c-7173-48bc-a321-132965860cf9",
        "part": "whole"
       },
       "id": "dd0f9f13-89ad-47f2-841e-668f49b66bf8"
      }
     }
    },
    "db018a31-7f8b-4680-b47a-4a63f1b99eaa": {
     "id": "db018a31-7f8b-4680-b47a-4a63f1b99eaa",
     "prev": "06194ea7-51cd-4aed-8513-cf743994e82c",
     "regions": {
      "cf030597-f8c2-4ecc-989c-2f0f2c5fcedd": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4290aeb6-33da-4e25-934c-67389557731a",
        "part": "whole"
       },
       "id": "cf030597-f8c2-4ecc-989c-2f0f2c5fcedd"
      }
     }
    },
    "de94994c-2a6e-4e26-88a1-2144056eceea": {
     "id": "de94994c-2a6e-4e26-88a1-2144056eceea",
     "prev": "49946442-2ac9-4b98-8fa9-9a1b4483b6ad",
     "regions": {
      "c5315e20-a256-4cae-9319-251f59d5dd04": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "29640a95-6ba1-4db6-90c6-873eebb49d06",
        "part": "whole"
       },
       "id": "c5315e20-a256-4cae-9319-251f59d5dd04"
      }
     }
    },
    "eb8f41e6-5cb1-4461-90ef-494bafdc2e40": {
     "id": "eb8f41e6-5cb1-4461-90ef-494bafdc2e40",
     "prev": "4c863375-81c0-405c-82cd-3dc163b4eb4c",
     "regions": {
      "0fd73668-3c11-4ff3-aa6f-389e94bf78f3": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "8ba9e526-7b9d-46b8-aff5-c24770802e0b",
        "part": "whole"
       },
       "id": "0fd73668-3c11-4ff3-aa6f-389e94bf78f3"
      }
     }
    },
    "ff7a9b95-4459-41ec-8123-31b17477083b": {
     "id": "ff7a9b95-4459-41ec-8123-31b17477083b",
     "prev": "8fe938e1-038b-48e3-ab24-36f8a8cef44a",
     "regions": {
      "87527301-4114-4d58-848a-342d13b734da": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "2d9326be-33da-4d10-b886-13e23c95ea30",
        "part": "whole"
       },
       "id": "87527301-4114-4d58-848a-342d13b734da"
      }
     }
    }
   },
   "themes": {
    "default": "b04cdc6e-7ddd-49c5-b42a-80251a3ef029",
    "theme": {}
   }
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "427.732px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_position": {
    "height": "413.143px",
    "left": "0px",
    "right": "888.384px",
    "top": "134.857px",
    "width": "208.759px"
   },
   "toc_section_display": "block",
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}