examples/Untitled1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "0a6f88e6-12bb-43b7-9b0f-fe4c6ad74ca2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The autoreload extension is already loaded. To reload it, use:\n",
      "  %reload_ext autoreload\n"
     ]
    }
   ],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "be825c99-3a78-4ea0-b923-8029cd9539df",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, \"..\")\n",
    "from tcs.tools.tools import Tools\n",
    "from tcs.automata.fa.dfa import DFA\n",
    "from tcs.automata.fa.nfa import NFA\n",
    "from tcs.regexpr.reg_expression import RegEx\n",
    "from tcs.grammar.regular.regular_grammar import RG\n",
    "from tcs.grammar.cf.cf_grammar import CFG\n",
    "from tcs.grammar.cs.cs_grammar import CSG\n",
    "from tcs.grammar.general.general_grammar import GG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "1514a127-8940-4cb1-b25a-45a31315d9b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "re1 = RegEx(alphabet={'a', 'b'},\n",
    "            expression=(Tools.simple_sequence('(a+b).a.(a+b).b*')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "eabd9ed0-3dc5-45d7-be60-ccf4551a2c69",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "re1.correct_string(Tools.tokens('aaabb'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "769267d8-3e1f-40b4-8f8f-a671703934ef",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(Ah8)         (Ah8) -> (b Ah0.h7)\n",
      "(b Ah0.h7)    (Ah0.h7) -> (a Ah1.h3)\n",
      "(b a Ah1.h3)  (Ah1.h3) -> (b)\n",
      "(b a b)\n"
     ]
    }
   ],
   "source": [
    "print(re1.rg.random_derivation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "e20c7a57-d9ee-47b4-8235-a9074602c27c",
   "metadata": {},
   "outputs": [],
   "source": [
    "gg0 = GG(\n",
    "    terminals={'0', '1'},\n",
    "    non_terminals={'A', 'B', 'C'},\n",
    "    axiom='A',\n",
    "    productions=Tools.simple_productions({\n",
    "        'A': {'0', '01BA', 'B1', 'BA0'},\n",
    "        'B0': {''},\n",
    "        'BA': {'', 'AB', '01'},\n",
    "        'A01': {'0', 'A0', 'C', '001'},\n",
    "        'AA': {'0A0', '0B1', ''}\n",
    "        })\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "f87b1d58-8738-4fe3-a373-1616a432c3c6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "terminals: 0,1\n",
      "non terminals: A,B,C\n",
      "axiom: A\n",
      "productions\n",
      "\tA -> BA0 | 01BA | B1 | 0 \n",
      "\tB0 -> _ \n",
      "\tBA -> _ | 01 | AB \n",
      "\tA01 -> C | A0 | 0 | 001 \n",
      "\tAA -> 0B1 | _ | 0A0\n"
     ]
    }
   ],
   "source": [
    "print(gg0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "01ad0db1-e97e-4db1-bd7e-786ddcdf8b2b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A  A -> 0\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "print(gg0.random_derivation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "11ba6d9b-2e9a-4dc4-9891-688390aaa905",
   "metadata": {},
   "outputs": [],
   "source": [
    "csg1 = CSG(\n",
    "    terminals={'a'},\n",
    "    non_terminals={'I', 'S', 'F', 'M'},\n",
    "    axiom='S',\n",
    "    productions=Tools.simple_productions({\n",
    "        'S': {'a','aa','IaF'},\n",
    "        'aF': {'Maa','MaaF'},\n",
    "        'aM': {'Maa'},\n",
    "        'IM': {'Ia','aa'}\n",
    "        }\n",
    "    ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "ef1c89be-e85d-420f-bf5d-ecc8270faf13",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "terminals: a\n",
      "non terminals: F,I,M,S\n",
      "axiom: S\n",
      "productions\n",
      "\tS -> aa | IaF | a \n",
      "\taF -> MaaF | Maa \n",
      "\taM -> Maa \n",
      "\tIM -> aa | Ia\n"
     ]
    }
   ],
   "source": [
    "print(csg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "13d8e2f9-8e9b-4285-9eaa-6b0575b4ca82",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S  S -> a\n",
      "a\n"
     ]
    }
   ],
   "source": [
    "print(csg1.random_derivation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "c86ebb9d-30e3-4a72-b36d-5179d2653e26",
   "metadata": {},
   "outputs": [],
   "source": [
    "cfg = CFG(\n",
    "    terminals={'a', 'b', 'c'},\n",
    "    non_terminals={'S', 'A', 'B', 'C'},\n",
    "    axiom='S',\n",
    "    productions=Tools.simple_productions({\n",
    "        'S': {'aSaS', 'aA', 'AB'},\n",
    "        'A': {'bbAB', 'bb', 'bAaB', 'B'},\n",
    "        'B': {'cAA', 'cc', 'C'},\n",
    "        'C': {'cC', 'c', 'S'}\n",
    "    })\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "867d14c6-0bf5-4d7a-8b2f-c14f91c715e4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "terminals: a,b,c\n",
      "non terminals: A,B,C,S\n",
      "axiom: S\n",
      "productions\n",
      "\tS -> aSaS | aA | AB \n",
      "\tA -> bb | bAaB | bbAB | B \n",
      "\tB -> C | cAA | cc \n",
      "\tC -> cC | S | c\n"
     ]
    }
   ],
   "source": [
    "print(cfg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "8401ee83-f8ab-4824-81e4-4ec9e54dc77d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S                                                                                                                                         S -> AB\n",
      "AB                                                                                                                                        B -> cc\n",
      "Acc                                                                                                                                       A -> B\n",
      "Bcc                                                                                                                                       B -> cAA\n",
      "cAAcc                                                                                                                                     A -> B\n",
      "cABcc                                                                                                                                     B -> cAA\n",
      "cAcAAcc                                                                                                                                   A -> B\n",
      "cAcABcc                                                                                                                                   B -> cc\n",
      "cAcAcccc                                                                                                                                  A -> bbAB\n",
      "cAcbbABcccc                                                                                                                               A -> bb\n",
      "cbbcbbABcccc                                                                                                                              B -> cc\n",
      "cbbcbbAcccccc                                                                                                                             A -> bbAB\n",
      "cbbcbbbbABcccccc                                                                                                                          B -> cc\n",
      "cbbcbbbbAcccccccc                                                                                                                         A -> B\n",
      "cbbcbbbbBcccccccc                                                                                                                         B -> cAA\n",
      "cbbcbbbbcAAcccccccc                                                                                                                       A -> bAaB\n",
      "cbbcbbbbcAbAaBcccccccc                                                                                                                    B -> cAA\n",
      "cbbcbbbbcAbAacAAcccccccc                                                                                                                  A -> B\n",
      "cbbcbbbbcAbAacABcccccccc                                                                                                                  A -> bAaB\n",
      "cbbcbbbbcAbbAaBacABcccccccc                                                                                                               A -> B\n",
      "cbbcbbbbcAbbBaBacABcccccccc                                                                                                               B -> C\n",
      "cbbcbbbbcAbbCaBacABcccccccc                                                                                                               C -> c\n",
      "cbbcbbbbcAbbcaBacABcccccccc                                                                                                               A -> bb\n",
      "cbbcbbbbcAbbcaBacbbBcccccccc                                                                                                              B -> cAA\n",
      "cbbcbbbbcAbbcacAAacbbBcccccccc                                                                                                            A -> bbAB\n",
      "cbbcbbbbcAbbcacAbbABacbbBcccccccc                                                                                                         A -> bb\n",
      "cbbcbbbbcbbbbcacAbbABacbbBcccccccc                                                                                                        A -> B\n",
      "cbbcbbbbcbbbbcacAbbBBacbbBcccccccc                                                                                                        B -> C\n",
      "cbbcbbbbcbbbbcacAbbBCacbbBcccccccc                                                                                                        B -> cc\n",
      "cbbcbbbbcbbbbcacAbbccCacbbBcccccccc                                                                                                       C -> c\n",
      "cbbcbbbbcbbbbcacAbbcccacbbBcccccccc                                                                                                       B -> cAA\n",
      "cbbcbbbbcbbbbcacAbbcccacbbcAAcccccccc                                                                                                     A -> bAaB\n",
      "cbbcbbbbcbbbbcacAbbcccacbbcAbAaBcccccccc                                                                                                  A -> bAaB\n",
      "cbbcbbbbcbbbbcacbAaBbbcccacbbcAbAaBcccccccc                                                                                               B -> C\n",
      "cbbcbbbbcbbbbcacbAaBbbcccacbbcAbAaCcccccccc                                                                                               A -> B\n",
      "cbbcbbbbcbbbbcacbAaBbbcccacbbcAbBaCcccccccc                                                                                               C -> cC\n",
      "cbbcbbbbcbbbbcacbAaBbbcccacbbcAbBacCcccccccc                                                                                              B -> C\n",
      "cbbcbbbbcbbbbcacbAaCbbcccacbbcAbBacCcccccccc                                                                                              A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbABaCbbcccacbbcAbBacCcccccccc                                                                                           B -> C\n",
      "cbbcbbbbcbbbbcacbbbACaCbbcccacbbcAbBacCcccccccc                                                                                           A -> bb\n",
      "cbbcbbbbcbbbbcacbbbbbCaCbbcccacbbcAbBacCcccccccc                                                                                          C -> S\n",
      "cbbcbbbbcbbbbcacbbbbbSaCbbcccacbbcAbBacCcccccccc                                                                                          C -> S\n",
      "cbbcbbbbcbbbbcacbbbbbSaSbbcccacbbcAbBacCcccccccc                                                                                          S -> aA\n",
      "cbbcbbbbcbbbbcacbbbbbaAaSbbcccacbbcAbBacCcccccccc                                                                                         A -> bAaB\n",
      "cbbcbbbbcbbbbcacbbbbbabAaBaSbbcccacbbcAbBacCcccccccc                                                                                      B -> C\n",
      "cbbcbbbbcbbbbcacbbbbbabAaCaSbbcccacbbcAbBacCcccccccc                                                                                      A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabAaCaSbbcccacbbcbbABbBacCcccccccc                                                                                   S -> AB\n",
      "cbbcbbbbcbbbbcacbbbbbabAaCaABbbcccacbbcbbABbBacCcccccccc                                                                                  B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabAaCaABbbcccacbbcbbABbccacCcccccccc                                                                                 A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbABaCaABbbcccacbbcbbABbccacCcccccccc                                                                              C -> cC\n",
      "cbbcbbbbcbbbbcacbbbbbabbbABacCaABbbcccacbbcbbABbccacCcccccccc                                                                             C -> c\n",
      "cbbcbbbbcbbbbcacbbbbbabbbABacCaABbbcccacbbcbbABbccacccccccccc                                                                             B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbABacCaABbbcccacbbcbbAccbccacccccccccc                                                                            A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbABacCabbABBbbcccacbbcbbAccbccacccccccccc                                                                         A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbABacCabbABBbbcccacbbcbbbbABccbccacccccccccc                                                                      C -> S\n",
      "cbbcbbbbcbbbbcacbbbbbabbbABacSabbABBbbcccacbbcbbbbABccbccacccccccccc                                                                      A -> B\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBBacSabbABBbbcccacbbcbbbbABccbccacccccccccc                                                                      B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBBacSabbABccbbcccacbbcbbbbABccbccacccccccccc                                                                     A -> B\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBBacSabbBBccbbcccacbbcbbbbABccbccacccccccccc                                                                     S -> AB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBBacABabbBBccbbcccacbbcbbbbABccbccacccccccccc                                                                    B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBBacABabbBBccbbcccacbbcbbbbAccccbccacccccccccc                                                                   B -> cAA\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBBacABabbcAABccbbcccacbbcbbbbAccccbccacccccccccc                                                                 A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBBacABabbcAABccbbcccacbbcbbbbbbABccccbccacccccccccc                                                              B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBccacABabbcAABccbbcccacbbcbbbbbbABccccbccacccccccccc                                                             A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBccacABabbcAABccbbcccacbbcbbbbbbbbABBccccbccacccccccccc                                                          B -> C\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBccacABabbcAABccbbcccacbbcbbbbbbbbACBccccbccacccccccccc                                                          A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBccacABabbcAbbABBccbbcccacbbcbbbbbbbbACBccccbccacccccccccc                                                       B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBccacAccabbcAbbABBccbbcccacbbcbbbbbbbbACBccccbccacccccccccc                                                      A -> bAaB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBccacAccabbcbAaBbbABBccbbcccacbbcbbbbbbbbACBccccbccacccccccccc                                                   A -> bb\n",
      "cbbcbbbbcbbbbcacbbbbbabbbBccacAccabbcbAaBbbABBccbbcccacbbcbbbbbbbbbbCBccccbccacccccccccc                                                  B -> C\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacAccabbcbAaBbbABBccbbcccacbbcbbbbbbbbbbCBccccbccacccccccccc                                                  B -> C\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacAccabbcbAaBbbACBccbbcccacbbcbbbbbbbbbbCBccccbccacccccccccc                                                  B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacAccabbcbAaccbbACBccbbcccacbbcbbbbbbbbbbCBccccbccacccccccccc                                                 B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacAccabbcbAaccbbACccccbbcccacbbcbbbbbbbbbbCBccccbccacccccccccc                                                B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacAccabbcbAaccbbACccccbbcccacbbcbbbbbbbbbbCccccccbccacccccccccc                                               C -> S\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacAccabbcbAaccbbASccccbbcccacbbcbbbbbbbbbbCccccccbccacccccccccc                                               A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacbbABccabbcbAaccbbASccccbbcccacbbcbbbbbbbbbbCccccccbccacccccccccc                                            A -> bAaB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacbbABccabbcbAaccbbbAaBSccccbbcccacbbcbbbbbbbbbbCccccccbccacccccccccc                                         B -> cAA\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacbbABccabbcbAaccbbbAacAASccccbbcccacbbcbbbbbbbbbbCccccccbccacccccccccc                                       C -> S\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacbbABccabbcbAaccbbbAacAASccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                                       A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacbbABccabbcbAaccbbbAacbbABASccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                                    B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbCccacbbAccccabbcbAaccbbbAacbbABASccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                                   C -> cC\n",
      "cbbcbbbbcbbbbcacbbbbbabbbcCccacbbAccccabbcbAaccbbbAacbbABASccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                                  A -> bAaB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbcCccacbbAccccabbcbAaccbbbAacbbbAaBBASccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                               A -> B\n",
      "cbbcbbbbcbbbbcacbbbbbabbbcCccacbbAccccabbcbBaccbbbAacbbbAaBBASccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                               C -> cC\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbAccccabbcbBaccbbbAacbbbAaBBASccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                              B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbAccccabbcbccaccbbbAacbbbAaBBASccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                             S -> aA\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbAccccabbcbccaccbbbAacbbbAaBBAaAccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                            A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbAccccabbcbccaccbbbbbABacbbbAaBBAaAccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                         B -> cAA\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbAccccabbcbccaccbbbbbAcAAacbbbAaBBAaAccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                       A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbABccccabbcbccaccbbbbbAcAAacbbbAaBBAaAccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                    A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbABBccccabbcbccaccbbbbbAcAAacbbbAaBBAaAccccbbcccacbbcbbbbbbbbbbSccccccbccacccccccccc                 S -> aA\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbABBccccabbcbccaccbbbbbAcAAacbbbAaBBAaAccccbbcccacbbcbbbbbbbbbbaAccccccbccacccccccccc                B -> cc\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbAccBccccabbcbccaccbbbbbAcAAacbbbAaBBAaAccccbbcccacbbcbbbbbbbbbbaAccccccbccacccccccccc               A -> bAaB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbAccBccccabbcbccaccbbbbbAcAAacbbbAaBBAabAaBccccbbcccacbbcbbbbbbbbbbaAccccccbccacccccccccc            A -> bbAB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbbbABccBccccabbcbccaccbbbbbAcAAacbbbAaBBAabAaBccccbbcccacbbcbbbbbbbbbbaAccccccbccacccccccccc         A -> bb\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbbbABccBccccabbcbccaccbbbbbAcAAacbbbAaBBAabAaBccccbbcccacbbcbbbbbbbbbbabbccccccbccacccccccccc        B -> C\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbbbABccBccccabbcbccaccbbbbbAcAAacbbbAaBCAabAaBccccbbcccacbbcbbbbbbbbbbabbccccccbccacccccccccc        A -> bAaB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbbbABccBccccabbcbccaccbbbbbAcbAaBAacbbbAaBCAabAaBccccbbcccacbbcbbbbbbbbbbabbccccccbccacccccccccc     C -> c\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbbbABccBccccabbcbccaccbbbbbAcbAaBAacbbbAaBcAabAaBccccbbcccacbbcbbbbbbbbbbabbccccccbccacccccccccc     A -> bAaB\n",
      "cbbcbbbbcbbbbcacbbbbbabbbccCccacbbbbbbbbABccBccccabbcbccaccbbbbbAcbAaBAacbbbAaBcAabbAaBaBccccbbcccacbbcbbbbbbbbbbabbccccccbccacccccccccc\n"
     ]
    }
   ],
   "source": [
    "print(cfg.random_derivation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "5b3defaa-2d77-415e-8916-80dd162fce6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "rg = RG(\n",
    "    terminals={'a', 'b', 'c'},\n",
    "    non_terminals={'S', 'A', 'B'},\n",
    "    axiom='S',\n",
    "    productions=Tools.simple_productions({\n",
    "        'S': {'aS', 'aA', 'bA'},\n",
    "        'A': {'bA', 'b', 'bB'},\n",
    "        'B': {'cA', 'c', ''}\n",
    "    }\n",
    "    )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "5e66a974-ab9f-4f49-9168-de5d6c7884a8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "terminals: a,b,c\n",
      "non terminals: A,B,S\n",
      "axiom: S\n",
      "productions\n",
      "\tS -> aS | aA | bA \n",
      "\tA -> b | bA | bB \n",
      "\tB -> c | _ | cA\n"
     ]
    }
   ],
   "source": [
    "print(rg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "3f3e6243-db99-4356-9ce2-9ae53ac8fd04",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S   S -> aA\n",
      "aA  A -> b\n",
      "ab\n"
     ]
    }
   ],
   "source": [
    "print(rg.random_derivation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "4861e7bf-3996-4e1d-8777-684037c45e30",
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar=cfg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "92dbed9e-3ede-4762-9db5-4d359b7bf4c1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "CFG{'terminals': {'a', 'b', 'c'}, 'non_terminals': {'S', 'C', 'B', 'A'}, 'axiom': 'S', 'all_chars': True, 'productions': {('S',): {('a', 'S', 'a', 'S'), ('a', 'A'), ('A', 'B')}, ('A',): {('b', 'b'), ('b', 'A', 'a', 'B'), ('b', 'b', 'A', 'B'), ('B',)}, ('B',): {('C',), ('c', 'A', 'A'), ('c', 'c')}, ('C',): {('c', 'C'), ('S',), ('c',)}}, 'no_null_production': False, 'null_string_produced': False, 'no_unit_production': False, 'reduced': False, 'cnf': False, 'gnf': False}"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "fe5bc97c-7669-46ef-825d-d72d120d52f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "ph, pr = cfg.derivations(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "6b74a5c5-fda5-4867-912b-fd97bcd19b2d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0: \n",
      "S \n",
      "1: \n",
      "aSaS aA AB \n",
      "2: \n",
      "bbB aSaaSaS abAaB aSaaA bbABB Acc abbAB AcAA AC aABaS BB aaSaSaS aaAaS aSaAB aB bAaBB \n",
      "3: \n",
      "acAA aaSaaAaS aaSaSaaSaS bbAaBaBB bbAccB bbACB aaSaABaS aSaaB aaAaaA abbbaB bbcAA aSabbABB aSaabAaB aSaaSaaSaS aABaaA aBBaS AcbbABA bbABcAA abAaC bAaBcAA aaBaS aaAaAB abAacAA aSaabb aaSaaSaSaS AcAB AcC bAacAAB aabbaS aabAaBaS bbbABaBB abAacc abbABBaS abbAcAA aabbABaS abbBaS abbAcc AS abBaB aaABaSaS aSaBB bAaccB BC bbAcAAB aaSaSaAB aSaaSaAB bBaBB BcAA aaSaSaaA abAaBBaS AcBA bbABC abbbbABB AcAbbAB abbAaBaB abbbbB ccB bAaBC aSaAC aaAaaSaS bbbAaBBB bAaCB CB aAccaS aSaaaSaSaS Bcc cAAB bbbaBB abbbAaBB aC aSaaSaaA bbBBB bbC AcbbA AcbAaBA bAaBcc aSaAcc aAcAAaS abbbABaB aSabbB AcAbAaB aSabAaBB aSaaABaS abbBB bbbbABBB aSaaaAaS aABaAB aABaaSaS aSaAcAA bbABcc abbAC aACaS aaaAaSaS bbbbBB aaaSaSaSaS Ac AcAbb aSaabbAB \n"
     ]
    }
   ],
   "source": [
    "cfg.derived_phrases(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "f308269b-ed71-4bee-bd42-f0633e565edf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0: \n",
      "\n",
      "1: \n",
      "\n",
      "2: \n",
      "abb \n",
      "3: \n",
      "acc bbcc \n"
     ]
    }
   ],
   "source": [
    "cfg.derived_strings(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "3b07dcbb-8c51-43c3-be9b-6697c6644cb2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "RG{'terminals': {'a', 'b'}, 'non_terminals': {'Ah12.h13', 'Ah12.h2', 'Ah0.h7', 'Ah10.h12', 'Ah0.h5', 'Ah1.h3', 'Ah8'}, 'axiom': 'Ah8', 'all_chars': False, 'productions': {('Ah8',): {('b', 'Ah0.h7'), ('a', 'Ah0.h5')}, ('Ah0.h5',): {('a', 'Ah1.h3')}, ('Ah0.h7',): {('a', 'Ah1.h3')}, ('Ah1.h3',): {('b',), ('a', 'Ah10.h12'), ('b', 'Ah12.h2'), ('a',)}, ('Ah10.h12',): {('b',), ('b', 'Ah12.h13')}, ('Ah12.h2',): {('b',), ('b', 'Ah12.h13')}, ('Ah12.h13',): {('b',), ('b', 'Ah12.h13')}}, 'no_null_production': False, 'null_string_produced': False, 'no_unit_production': False, 'reduced': False, 'cnf': False, 'gnf': False}"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "id": "a4e69f8c-8342-4d9e-8d4c-5d6d00aaae81",
   "metadata": {},
   "outputs": [],
   "source": [
    "rg = re1.rg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "id": "d47f89bb-9cba-4655-85cc-a0ed184d1967",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alphabet: a, b\n",
      "expression: ( ( ( ( a + b ) . a ) . ( a + b ) ) . b * )\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(re1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "id": "af7a3cb4-9a4c-4d8b-990a-d288ca77b2a8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('S',): {('a', 'S', 'a', 'S'), ('a', 'A'), ('A', 'B')}, ('A',): {('b', 'b'), ('b', 'A', 'a', 'B'), ('b', 'b', 'A', 'B'), ('B',)}, ('B',): {('C',), ('c', 'A', 'A'), ('c', 'c')}, ('C',): {('c', 'C'), ('S',), ('c',)}}\n"
     ]
    }
   ],
   "source": [
    "print(cfg.productions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "id": "304f7bd3-9460-4269-94d0-8b55d98b0459",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "terminals: a,b\n",
      "non terminals: Ah0.h5,Ah0.h7,Ah1.h3,Ah10.h12,Ah12.h13,Ah12.h2,Ah8\n",
      "axiom: Ah8\n",
      "productions\n",
      "\tAh8 -> b Ah0.h7 | a Ah0.h5 \n",
      "\tAh0.h5 -> a Ah1.h3 \n",
      "\tAh0.h7 -> a Ah1.h3 \n",
      "\tAh1.h3 -> b | a Ah10.h12 | b Ah12.h2 | a \n",
      "\tAh10.h12 -> b | b Ah12.h13 \n",
      "\tAh12.h2 -> b | b Ah12.h13 \n",
      "\tAh12.h13 -> b | b Ah12.h13\n"
     ]
    }
   ],
   "source": [
    "print(rg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "id": "2eb500c8-1122-40da-8a39-c53d9d371a0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "nt_dict = {}\n",
    "if len(rg.non_terminals) > 26:\n",
    "    print('Too many non terminals')\n",
    "else:\n",
    "    i = 65\n",
    "    for nt in rg.non_terminals:\n",
    "        if nt == rg.axiom:\n",
    "            nt_dict[nt] = 'S'\n",
    "        else:\n",
    "            nt_dict[nt] = chr(i)\n",
    "            i += 1\n",
    "            if i == 83:\n",
    "                i += 1\n",
    "    new_terminals = rg.terminals\n",
    "    new_non_terminals = set(nt_dict.values())\n",
    "    new_axiom = 'S'\n",
    "    new_prods = {}\n",
    "    for left_part, right_parts in rg.productions.items(): \n",
    "        new_prods[nt_dict[''.join(left_part)]] = set()\n",
    "        for right_part in right_parts:\n",
    "            s = ''\n",
    "            for t in right_part:\n",
    "                if t in rg.terminals:\n",
    "                    s+=t\n",
    "                else:\n",
    "                    s+=nt_dict[t]\n",
    "            new_prods[nt_dict[''.join(left_part)]].add(s)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "id": "530841ce-26a9-4056-8d4d-ffbe2dac6b14",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'S': {'aE', 'bC'}, 'E': {'aF'}, 'C': {'aF'}, 'F': {'aD', 'a', 'b', 'bB'}, 'D': {'bA', 'b'}, 'B': {'bA', 'b'}, 'A': {'bA', 'b'}}\n"
     ]
    }
   ],
   "source": [
    "print(new_prods)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "id": "32f395ae-4a46-4004-8ed6-6f67d67af514",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'S': {'aE', 'bC'}, 'E': {'aF'}, 'C': {'aF'}, 'F': {'aD', 'a', 'b', 'bB'}, 'D': {'bA', 'b'}, 'B': {'bA', 'b'}, 'A': {'bA', 'b'}}\n"
     ]
    }
   ],
   "source": [
    "print(new_prods)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "id": "24fa8757-64b3-4848-8117-74accbfd46b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "rg1 = RG(terminals=new_terminals,\n",
    "        non_terminals=new_non_terminals,\n",
    "        axiom = new_axiom,\n",
    "        productions = Tools.simple_productions(new_prods)\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "id": "5b98b649-361b-400f-9171-d13372bea329",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('S',): {('b', 'C'), ('a', 'E')}, ('E',): {('a', 'F')}, ('C',): {('a', 'F')}, ('F',): {('b',), ('b', 'B'), ('a', 'D'), ('a',)}, ('D',): {('b',), ('b', 'A')}, ('B',): {('b',), ('b', 'A')}, ('A',): {('b',), ('b', 'A')}}\n"
     ]
    }
   ],
   "source": [
    "print(rg1.productions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "id": "60967b85-169e-4420-a252-4d87b872485f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "terminals: a,b\n",
      "non terminals: A,B,C,D,E,F,S\n",
      "axiom: S\n",
      "productions\n",
      "\tS ->  b C |  a E \n",
      "\tE ->  a F \n",
      "\tC ->  a F \n",
      "\tF ->  b |  b B |  a D |  a \n",
      "\tD ->  b |  b A \n",
      "\tB ->  b |  b A \n",
      "\tA ->  b |  b A\n"
     ]
    }
   ],
   "source": [
    "print(rg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ae4f52e-ffab-4662-83e1-a41d63022abb",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8",
   "language": "python",
   "name": "python3.8"
  },
  "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.8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}