CFG_to_CNF.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computer Theory Project - Phase 2 (CFG to CNF)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Members`\n",
    "1. Antony Kiroles 202000897\n",
    "2. Donia Khaled 202001874\n",
    "3. Eslam Ahmed 202000039\n",
    "3. Mariam Barakat 202000210"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 277,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 278,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['N->S', 'S->ASB|a', 'A->aAS|a|ε', 'B->SbS|A|bb']\n"
     ]
    }
   ],
   "source": [
    "# 1- Create new start and add it to the inputs\n",
    "\n",
    "#test = ['S->ABA','A->aA|ε','B->bBc|ε']\n",
    "test = ['S->ASB|a', 'A->aAS|a|ε', 'B->SbS|A|bb']\n",
    "\n",
    "newStart = 'N->'+test[0][0]\n",
    "\n",
    "newTest = [None] * (len(test) + 1)\n",
    "\n",
    "newTest[0] = newStart\n",
    "\n",
    "newTest[1:] = test\n",
    "\n",
    "print(newTest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 279,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['N->S', 'S->A.S.B|a', 'A->a.A.S|a|ε', 'B->S.b.S|A|b.b']\n",
      "[{'N': {'S'}}, {'S': {'A.S.B', 'a'}}, {'A': {'ε', 'a.A.S', 'a'}}, {'B': {'S.b.S', 'b.b', 'A'}}]\n"
     ]
    }
   ],
   "source": [
    "def addAndSymbol(input:list[str])->list[str]:\n",
    "    operators = ['|','>','-','.']\n",
    "    for rule in range(len(input)):\n",
    "        rules = list(input[rule])\n",
    "        insertOffset = 0\n",
    "        for i in range(1, len(input[rule])):\n",
    "            if input[rule][i] not in operators and input[rule][i-1] not in operators:\n",
    "                a = rules[i]\n",
    "                b = rules[i-1]\n",
    "                rules.insert(i+insertOffset,'.')\n",
    "                insertOffset += 1\n",
    "        input[rule] = ''.join(rules)\n",
    "    return input\n",
    "\n",
    "def stringListToCFG(input:list[str])->dict[str,set[str]]:\n",
    "    input = addAndSymbol(input)\n",
    "    input = [x.split('->') for x in input]\n",
    "    input = [{x[0]:set(x[1].split('|'))} for x in input]\n",
    "    return input\n",
    "print(addAndSymbol(newTest))\n",
    "print(stringListToCFG(newTest))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "# helper functions that outputs the combinations of all the letters that need to be removed\n",
    "def remove_indices(string_,to_remove):\n",
    "    # find position all what you need to remove\n",
    "    positions_toremove =[] \n",
    "    for j in range(len(string_)):\n",
    "        if string_[j] == to_remove:\n",
    "            positions_toremove.append(j) \n",
    "    # generate combinations of this index\n",
    "    indecies=[]\n",
    "    for j in range(1,len(positions_toremove)+1):\n",
    "        indecies.extend(list(combinations(positions_toremove, r=j)))\n",
    "\n",
    "    return indecies   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "metadata": {},
   "outputs": [],
   "source": [
    "# a helper function to loop through the indices to remove and remove them \n",
    "def generate_combinations(string_,indecies):\n",
    "    # loop through string and remove according to the combination\n",
    "    temp_str=set()\n",
    "    c=list(string_)\n",
    "    for i in indecies:\n",
    "        x=c.copy()\n",
    "        for j in i:\n",
    "            x[j]=''\n",
    "\n",
    "        added = ''.join(x)\n",
    "        if len(added) == 0:\n",
    "            temp_str.add('ε') \n",
    "        else:\n",
    "            temp_str.add(added) \n",
    "\n",
    "    return temp_str   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 282,
   "metadata": {},
   "outputs": [],
   "source": [
    "# a helper function to make sure that there is no null to further remove\n",
    "def no_null(CFG, start):\n",
    "    for key, values in CFG.items():\n",
    "        if \"ε\" in values and key != start:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 283,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ========================== remove null productions \n",
    "def remove_null_production(CFG, start):\n",
    "    ###finished = []\n",
    "    while no_null(CFG, start) == False:\n",
    "        for key, values in CFG.items():\n",
    "            # start by finding any epsilon to be able to remove and replace it \n",
    "            ### if key in finished and \"ε\" in values and key != start:\n",
    "            ###     # remove the epsilon and call it a day\n",
    "            ###     CFG[key].remove('ε')\n",
    "            \n",
    "            if \"ε\" in values and key != start:\n",
    "                # find all the values of the key \n",
    "                CFG[key].remove('ε')\n",
    "                for keys2, values2 in CFG.items():\n",
    "                    # loop to find the key that had the epsolin \n",
    "                    for j in values2: \n",
    "                        if key in ''.join(list(j)):   \n",
    "                            #search for the key in the values \n",
    "                            CFG[keys2] = CFG[keys2].union(generate_combinations(j,remove_indices(j,key)))\n",
    "                ###finished.append(key)\n",
    "                CFGcopy = copy.deepcopy(CFG)\n",
    "                for i in CFGcopy:\n",
    "                    for j in CFGcopy[i]:\n",
    "                        # noEps = re.search('[a-zA-Z]+', j)\n",
    "                        CFG[i].add(j.replace('..', '.'))\n",
    "                        if (j != j.replace('..', '.')):\n",
    "                            CFG[i].remove(j)\n",
    "                            j = j.replace('..', '.')\n",
    "                        if (j[0] == '.' or j[-1] == '.'):\n",
    "                            CFG[i].add(j.strip('.'))\n",
    "                            CFG[i].remove(j)\n",
    "                            \n",
    "    return CFG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 284,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'N': {'S'}},\n",
       " {'S': {'A.S.B', 'a'}},\n",
       " {'A': {'a', 'a.A.S', 'ε'}},\n",
       " {'B': {'A', 'S.b.S', 'b.b'}}]"
      ]
     },
     "execution_count": 284,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CFG = stringListToCFG(newTest)\n",
    "CFG "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 285,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'N': {'S'},\n",
       " 'S': {'A.S.B', 'a'},\n",
       " 'A': {'a', 'a.A.S', 'ε'},\n",
       " 'B': {'A', 'S.b.S', 'b.b'}}"
      ]
     },
     "execution_count": 285,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CFGdict = {}\n",
    "for i in range (0, len(CFG)):\n",
    "    CFGdict.update(CFG[i])\n",
    "    \n",
    "CFGdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 286,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'N': {'S'},\n",
       " 'S': {'A.S', 'A.S.B', 'S', 'S.B', 'a'},\n",
       " 'A': {'a', 'a.A.S', 'a.S'},\n",
       " 'B': {'A', 'S.b.S', 'b.b'}}"
      ]
     },
     "execution_count": 286,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CFG = remove_null_production(CFGdict, newStart[0])\n",
    "CFG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 287,
   "metadata": {},
   "outputs": [],
   "source": [
    "# a helper function to search for all the nonterminals that are alone and adds them to a list\n",
    "def contain_nonterminal(set_value):\n",
    "    set_of_nonterminals = set()\n",
    "    for i in set_value:\n",
    "        if len(i) == 1 and i.isupper():\n",
    "            set_of_nonterminals.add(i)\n",
    "    return set_of_nonterminals\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 288,
   "metadata": {},
   "outputs": [],
   "source": [
    "# a helper function to make sure that there is no nontermianls alone anymore \n",
    "def done(CFG):\n",
    "    for k, v in CFG.items():\n",
    "        if len(contain_nonterminal(v)) != 0:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 289,
   "metadata": {},
   "outputs": [],
   "source": [
    "# =============================== Unit production final function\n",
    "def remove_unit_production(CFG):\n",
    "\n",
    "    while done(CFG) != True:\n",
    "        # loop through the dictionary to find nontemrminals that are alone\n",
    "        for primary_key, set_value in CFG.items():\n",
    "            set_non_terminals = contain_nonterminal(set_value)\n",
    "            if len(set_non_terminals) != 0:\n",
    "                #in case there is multiple nonterminals alone in a value\n",
    "                for i in set_non_terminals:\n",
    "                    # delete all the non-terminals\n",
    "                    CFG[primary_key].remove(i)\n",
    "                    # # union of the primary values and they nonterminal values we searched for \n",
    "                    CFG[primary_key] =  CFG[primary_key].union(CFG[i])\n",
    "                    # delete if the primary key is equal to a nonterminal\n",
    "                    if i == primary_key and i in CFG[primary_key]:\n",
    "                        CFG[primary_key].remove(i)\n",
    "    return CFG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'N': {'A.S.B', 'A.S', 'a', 'S.B'}, 'S': {'A.S.B', 'A.S', 'S.B', 'a'}, 'A': {'a.S', 'a.A.S', 'a'}, 'B': {'b.b', 'a.A.S', 'a', 'S.b.S', 'a.S'}}\n"
     ]
    }
   ],
   "source": [
    "#CFG2 = {\"S\": {\"A.a\", \"B\"}, \"A\": {\"a\", \"b.c\", \"B\"}, \"B\": {\"A\", \"b.b\"}}\n",
    "CFG = remove_unit_production(CFG)\n",
    "print(CFG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test = {'S': {'a.S', 'A', 'C'}, 'A': {'a'}, 'B': {'a.a'}, 'C': {'a.C.b'}}\n",
    "# start = 'S'\n",
    "\n",
    "def eliminateUselessProd(cfg, start):\n",
    "    testCopy = copy.deepcopy(cfg)\n",
    "    \n",
    "    # non-generating\n",
    "    non_generating = set()\n",
    "    for i in cfg[start]:\n",
    "        for j in i:\n",
    "            # case1: if the start state has a non-terminal that is not a key, meaning it does not have transitions, it is added to the non-generating set\n",
    "            if (j not in cfg.keys() and j.isupper()): \n",
    "                non_generating.add(j)\n",
    "                continue\n",
    "            # case2: if a non-terminal transitions to a terminal AND nonterminal, without and epsilon, meaning the nonterminal cannot be removed, \n",
    "            # it is considered as non generating. Checks if its uppercase and does not have an epsilon transition and any transitions to terminal\n",
    "            if ((j.isupper()) and ('' not in cfg[j]) and (len(cfg[j]) == 1)):\n",
    "                for k in str(cfg[j]):\n",
    "                    if k.isupper():\n",
    "                        non_generating.add(j)\n",
    "    \n",
    "    # deletes the element that has a non-generating non-terminal\n",
    "    for i in testCopy[start]:\n",
    "        for j in i:\n",
    "            if ((j in non_generating)):    \n",
    "                cfg[start].remove(i)\n",
    "    # deletes the non-generating non-terminal from the cfg \n",
    "    for i in non_generating:\n",
    "        del cfg[i]\n",
    "                        \n",
    "    # Non-reachable\n",
    "    reachable = {}\n",
    "    non_reachable = {}\n",
    "    \n",
    "    for i in cfg[start]:\n",
    "        for j in i:         # checks the non-terminals in the start state and appends them to reachable dict with their values\n",
    "            if (j.isupper()):\n",
    "                reachable[j] = cfg[j]   \n",
    "            \n",
    "    for i in cfg.keys():   # appends any non-terminals found in the CFG thats not in the reachable dict and appends it to the non reachable dict\n",
    "        if ((i not in reachable.keys()) and i != start):\n",
    "            non_reachable[i] = cfg[i]\n",
    "        \n",
    "    for i in testCopy:     # goes over the non-terminals that cannot be reached from the start state and deletes them\n",
    "        if i in non_reachable:\n",
    "            del cfg[i]\n",
    "            \n",
    "    return cfg\n",
    "\n",
    "CFG = eliminateUselessProd(CFG, newStart[0])\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 292,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'N': {'A.S.B', 'A.S', 'a', 'S.B'}, 'S': {'A.S.B', 'A.S', 'S.B', 'a'}, 'A': {'a.S', 'a.A.S', 'a'}, 'B': {'b.b', 'a.A.S', 'a', 'S.b.S', 'a.S'}}\n"
     ]
    }
   ],
   "source": [
    "print(CFG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 293,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'N': {'A.S.B', 'A.S', 'a', 'S.B'}, 'S': {'A.S.B', 'A.S', 'S.B', 'a'}, 'A': {'a.S', 'a.A.S', 'a'}, 'B': {'b.b', 'a.A.S', 'a', 'S.b.S', 'a.S'}}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'N': {'A.S', 'K0.B', 'S.B', 'a'},\n",
       " 'S': {'A.S', 'K0.B', 'S.B', 'a'},\n",
       " 'A': {'K1.S', 'K2.S', 'a'},\n",
       " 'B': {'K1.S', 'K2.S', 'K3.K3', 'K4.S', 'a'},\n",
       " 'K0': {'A.S'},\n",
       " 'K1': {'a'},\n",
       " 'K2': {'K1.A'},\n",
       " 'K3': {'b'},\n",
       " 'K4': {'S.K3'}}"
      ]
     },
     "execution_count": 293,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def ReduceStringToEvens(rule:str,originalInput:dict[str,set[str]],currentDict:dict[str,set[str]],currentCounter:int)->tuple[str,dict[str,str],int]:\n",
    "    output = {}\n",
    "    if rule.count('.') == 1:\n",
    "        return rule,{},currentCounter\n",
    "    splitString = rule.split('.')\n",
    "    if(len(splitString)%2==1):\n",
    "        evenRule = None\n",
    "        firstTwoLiterals = rule[:rule.index('.',rule.index('.')+1)]\n",
    "        if {firstTwoLiterals} in originalInput.values():\n",
    "            newRuleKey = list(originalInput.keys())[list(originalInput.values()).index({firstTwoLiterals})]\n",
    "            evenRule = rule.replace(firstTwoLiterals,newRuleKey)\n",
    "        elif {firstTwoLiterals} not in currentDict.values():\n",
    "            newRuleKey = f'K{currentCounter}'\n",
    "            currentCounter += 1\n",
    "            newRuleValue= firstTwoLiterals\n",
    "            output[newRuleKey] = {newRuleValue}\n",
    "            evenRule = rule.replace(firstTwoLiterals,newRuleKey)\n",
    "        else: \n",
    "            newRuleKey = list(currentDict.keys())[list(currentDict.values()).index({firstTwoLiterals})]\n",
    "            evenRule = rule.replace(firstTwoLiterals,newRuleKey)\n",
    "    else:\n",
    "        evenRule = rule\n",
    "\n",
    "    currentDict.update(output)\n",
    "    if len(evenRule.split('.'))>2:\n",
    "        left = '.'.join(splitString[:len(splitString)//2])\n",
    "        right = '.'.join(splitString[len(splitString)//2:])\n",
    "        leftSet = {left}\n",
    "        if leftSet in originalInput.values():\n",
    "            leftKey = list(originalInput.keys())[list(originalInput.values()).index(leftSet)]\n",
    "        elif leftSet in output.values():\n",
    "            leftKey = list(output.keys())[list(output.values()).index(leftSet)]\n",
    "        elif leftSet not in currentDict.values():\n",
    "            leftKey = currentCounter\n",
    "            currentCounter += 1\n",
    "            leftKey = f'K{leftKey}'\n",
    "        else:\n",
    "            leftKey = list(currentDict.keys())[list(currentDict.values()).index({left})]\n",
    "        splitStringLeft = ReduceStringToEvens(left,originalInput,currentDict,currentCounter)\n",
    "        currentCounter = splitStringLeft[2]\n",
    "        output.update(splitStringLeft[1])\n",
    "        output[f'{leftKey}'] = {splitStringLeft[0]}\n",
    "\n",
    "        rightSet = {right}\n",
    "        if rightSet in originalInput.values():\n",
    "            rightKey = list(originalInput.keys())[list(originalInput.values()).index(rightSet)]\n",
    "        elif rightSet in output.values():\n",
    "            rightKey = list(output.keys())[list(output.values()).index(rightSet)]\n",
    "        elif rightSet not in currentDict.values():\n",
    "            rightKey = currentCounter\n",
    "            currentCounter += 1\n",
    "            rightKey = f'K{rightKey}'\n",
    "        else:\n",
    "            rightKey = list(currentDict.keys())[list(currentDict.values()).index(rightSet)]\n",
    "        splitStringRight = ReduceStringToEvens(right,originalInput,currentDict,currentCounter)\n",
    "        output[f'{rightKey}'] = {splitStringRight[0]}\n",
    "        currentCounter = splitStringRight[2]\n",
    "        output.update(splitStringRight[1])\n",
    "\n",
    "        evenRule = f'{leftKey}.{rightKey}'\n",
    "    \n",
    "    return evenRule,output,currentCounter \n",
    "    \n",
    "    \n",
    "def ToCNF(input : dict[str,set[str]])->dict[str,set[str]]:\n",
    "    output = {}\n",
    "    newRuleCounter = 0\n",
    "    for k,v in input.items():\n",
    "        FinalValue = set()\n",
    "        for rule in v:\n",
    "            if(len(rule)>1):\n",
    "                elements = rule.split('.')\n",
    "                for i in range(len(elements)):\n",
    "                    if(elements[i].islower()):\n",
    "                        if {elements[i]} in input.values():\n",
    "                            newRuleKey = list(input.keys())[list(input.values()).index({elements[i]})]\n",
    "                            elements[i] = newRuleKey\n",
    "                        elif {elements[i]} not in output.values():\n",
    "                            newRuleKey = f'K{newRuleCounter}'\n",
    "                            newRuleCounter += 1\n",
    "                            newRuleValue = elements[i]\n",
    "                            output[newRuleKey] = {newRuleValue}\n",
    "                            elements[i] = newRuleKey\n",
    "                        else: \n",
    "                            newRuleKey = list(output.keys())[list(output.values()).index({elements[i]})]\n",
    "                            elements[i] = newRuleKey\n",
    "                rule = '.'.join(elements)\n",
    "            if len(rule.split('.'))<=2:\n",
    "                FinalValue.add(rule)\n",
    "                continue\n",
    "            final = ReduceStringToEvens(rule,input,output,newRuleCounter)\n",
    "            newRuleCounter = final[2]\n",
    "            output.update(final[1])\n",
    "            evenRule = final[0]\n",
    "            FinalValue.add(evenRule)\n",
    "        output[k] = FinalValue\n",
    "    sortedOutput = {}\n",
    "    for k in input.keys():\n",
    "        sortedOutput[k] = output[k]\n",
    "    sortedOutput.update(output)\n",
    "    return sortedOutput\n",
    "\n",
    "print(CFG)\n",
    "ToCNF(CFG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.9.13"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}