{
 "cells": [
  {
   "cell_type": "code",
   "outputs": [],
   "source": [
    "import automata.regex.regex as re\n",
    "from automata.fa.nfa import NFA\n",
    "from IPython.display import Math\n",
    "\n",
    "debug = True\n",
    "\n",
    "def regex_test(regex: str, inputs: list[str]):\n",
    "    re.validate(regex)\n",
    "    nfa = NFA.from_regex(regex)\n",
    "    for i in inputs:\n",
    "        print(f\"{i}: {nfa.accepts_input(i)}\")\n",
    "        \n",
    "def latexify(regex: str):\n",
    "    steps = regex\n",
    "    steps = steps.replace('()', '\\\\epsilon')\n",
    "    steps = steps.replace('(', '\\\\left(')\n",
    "    steps = steps.replace(')', '\\\\right)')\n",
    "    steps = steps.replace('|', '\\\\cup')\n",
    "    steps = steps.replace('&', '\\\\land')\n",
    "    steps = steps.replace('*', '^*')\n",
    "    steps = '$' + steps + '$'\n",
    "    return steps"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.498255Z",
     "start_time": "2024-03-22T22:22:26.217210Z"
    }
   },
   "id": "aa9fd8c82c66ac9a",
   "execution_count": 1
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'aaaab', 'a', 'b', 'aaab', 'ab', 'aaaa', 'aab'}\n",
      "['baaaa', 'ba', 'baab', 'baaaaa', 'baa', 'baaab']\n",
      "['', 'b', 'bb', 'bbb', 'bba', 'ba', 'bab']\n"
     ]
    }
   ],
   "source": [
    "l1 = ['b', 'ba']\n",
    "l2 = ['a', 'aab', 'aaaa']\n",
    "l3 = []\n",
    "for i in range(0, 5):\n",
    "    l3.append('a' * i + 'b')\n",
    "# turn all of these into sets\n",
    "l1 = set(l1)\n",
    "l2 = set(l2)\n",
    "l3 = set(l3)\n",
    "\n",
    "# l2 union l3\n",
    "l2.union(l3)\n",
    "if debug:\n",
    "    print(l2.union(l3))\n",
    "# l1 times l2\n",
    "a = []\n",
    "for i in l1:\n",
    "    for j in l2:\n",
    "        a.append(i + j)\n",
    "if debug:\n",
    "    print(a)\n",
    "\n",
    "# kleen star of l1 up to length 3\n",
    "a = ['']\n",
    "for i in l1:\n",
    "    a.append(i)\n",
    "    for j in l1:\n",
    "        a.append(i + j)\n",
    "        for k in l1:\n",
    "            a.append(i + j + k)\n",
    "# remove all strings of length greater than 3\n",
    "a = [x for x in a if len(x) <= 3]\n",
    "if debug:\n",
    "    print(a)"
   ],
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.505139Z",
     "start_time": "2024-03-22T22:22:26.499628Z"
    }
   },
   "id": "initial_id",
   "execution_count": 2
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 28\n",
    "## b.\n",
    "aaab, aaaa, a, aaaab, b, ab, aab\n",
    "\n",
    "## c.\n",
    "baaaaa, baaab, baa, baaaa, baab, ba\n",
    "\n",
    "## e. \n",
    "$\\epsilon$, ba, bab, b, bba, bb, bbb\n",
    "\n",
    "## h.\n",
    "Yes, because the Kleen star of $L_1$ includes all original strings in the language, and the string 'b', where n is zero is included in $(L_1)^*$, so it is possible for $(L_1)^*$ to have a string where there is more bs than as. "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "823eb4c275b95911"
  },
  {
   "cell_type": "markdown",
   "source": [
    "$\\pagebreak$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ae5527f9dab42f59"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 30\n",
    "## c."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "5f0f62a85e3cddd0"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "aabb: False\n",
      "aabbbb: False\n",
      "aabbbbb: True\n",
      "aaabbbbbb: False\n",
      "aaaabbbbbbbbb: True\n"
     ]
    },
    {
     "data": {
      "text/plain": "<IPython.core.display.Math object>",
      "text/latex": "$\\displaystyle \\left(aa\\right)^*\\left(bbbb\\right)^*b$"
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define a regex where 'a' is a multiple of 2 and 'b' is a multiple of 4 + 1\n",
    "q31c = '(aa)*(bbbb)*b'\n",
    "inputs = [\n",
    "\t'aabb',\n",
    "\t'aabbbb',\n",
    "\t'aabbbbb',\n",
    "\t'aaabbbbbb',\n",
    "\t'aaaabbbbbbbbb',\n",
    "]\n",
    "if debug:\n",
    "    regex_test(q31c, inputs)\n",
    "Math(latexify(q31c))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.515494Z",
     "start_time": "2024-03-22T22:22:26.506412Z"
    }
   },
   "id": "c0d81b8fb61431de",
   "execution_count": 3
  },
  {
   "cell_type": "markdown",
   "source": [
    "## d."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "53e09c458eafb680"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ab: True\n",
      "bab: False\n",
      "bbab: True\n",
      "bbbabb: True\n",
      "bbbabbb: False\n",
      "abb: False\n",
      "abbb: True\n",
      "ba: True\n",
      "bba: False\n",
      "bbba: True\n"
     ]
    },
    {
     "data": {
      "text/plain": "<IPython.core.display.Math object>",
      "text/latex": "$\\displaystyle \\left(\\left(bb\\right)^*ba\\left(bb\\right)^*\\right)\\cup\\left(\\left(bb\\right)^*ab\\left(bb\\right)^*\\right)$"
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define a regex where the number of as is 1 and the number of bs is odd\n",
    "q31e = \"((bb)*ba(bb)*)|((bb)*ab(bb)*)\"\n",
    "inputs = [\n",
    "    'ab',\n",
    "    'bab',\n",
    "    'bbab',\n",
    "    'bbbabb',\n",
    "    'bbbabbb',\n",
    "    'abb',\n",
    "    'abbb',\n",
    "    'ba',\n",
    "    'bba',\n",
    "    'bbba',\n",
    "]\n",
    "if debug:\n",
    "    regex_test(q31e, inputs)\n",
    "Math(latexify(q31e))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.522964Z",
     "start_time": "2024-03-22T22:22:26.517188Z"
    }
   },
   "id": "75f2af38daefc05b",
   "execution_count": 4
  },
  {
   "cell_type": "markdown",
   "source": [
    "$\\pagebreak$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "9271ff95c0925816"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 31\n",
    "## c."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c4c41d43969e22bb"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ": True\n",
      "0: True\n",
      "1: True\n",
      "00: True\n",
      "01: True\n",
      "10: True\n",
      "11: True\n",
      "000: True\n",
      "001: True\n",
      "010: True\n",
      "011: True\n",
      "100: True\n",
      "101: True\n",
      "0000: True\n",
      "0001: True\n",
      "0010: True\n",
      "0011: True\n",
      "0100: True\n",
      "0101: True\n",
      "0110: True\n",
      "0111: True\n",
      "1000: True\n",
      "00000: False\n",
      "11111: False\n"
     ]
    },
    {
     "data": {
      "text/plain": "<IPython.core.display.Math object>",
      "text/latex": "$\\displaystyle \\epsilon\\cup\\left(0\\cup1\\right)\\cup\\left(0\\cup1\\right)\\left(0\\cup1\\right)\\cup\\left(0\\cup1\\right)\\left(0\\cup1\\right)\\left(0\\cup1\\right)\\cup\\left(0\\cup1\\right)\\left(0\\cup1\\right)\\left(0\\cup1\\right)\\left(0\\cup1\\right)$"
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define a regex where the number of 1s or 0s is less than or equal to 4\n",
    "q31c = '()|(0|1)|(0|1)(0|1)|(0|1)(0|1)(0|1)|(0|1)(0|1)(0|1)(0|1)'\n",
    "inputs = [\n",
    "    '',\n",
    "    '0',\n",
    "    '1',\n",
    "    '00',\n",
    "    '01',\n",
    "    '10',\n",
    "    '11',\n",
    "    '000',\n",
    "    '001',\n",
    "    '010',\n",
    "    '011',\n",
    "    '100',\n",
    "    '101',\n",
    "    '0000',\n",
    "    '0001',\n",
    "    '0010',\n",
    "    '0011',\n",
    "    '0100',\n",
    "    '0101',\n",
    "    '0110',\n",
    "    '0111',\n",
    "    '1000',\n",
    "    '00000',\n",
    "    '11111',\n",
    "]\n",
    "if debug:\n",
    "    regex_test(q31c, inputs)\n",
    "Math(latexify(q31c))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.531449Z",
     "start_time": "2024-03-22T22:22:26.524511Z"
    }
   },
   "id": "404b569fb1f1b3dd",
   "execution_count": 5
  },
  {
   "cell_type": "markdown",
   "source": [
    "## e."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "64279b55169daadf"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0100001: True\n",
      "0100000100001: True\n",
      "1000001: True\n",
      "00000010000100000: True\n",
      "1000100001: False\n"
     ]
    },
    {
     "data": {
      "text/plain": "<IPython.core.display.Math object>",
      "text/latex": "$\\displaystyle 0^*1\\left(00000^*1\\right)^*\\left(00000^*1\\right)0^*$"
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define a regex where the number of 1s is greater or equal to 2 and there are at least four zeros between each 1 and the next 1\n",
    "q31e = '0*1(00000*1)*(00000*1)0*'\n",
    "# 0*1 = 0 or more zeros followed by a 1\n",
    "# (00000*1) = 4 or more zeros followed by a 1\n",
    "inputs = [\n",
    "    '0100001',\n",
    "    '0100000100001',\n",
    "    '1000001',\n",
    "    '00000010000100000',\n",
    "    '1000100001',\n",
    "]\n",
    "if debug:\n",
    "    regex_test(q31e, inputs)\n",
    "Math(latexify(q31e))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.538114Z",
     "start_time": "2024-03-22T22:22:26.532887Z"
    }
   },
   "id": "91ecde46ccfd6037",
   "execution_count": 6
  },
  {
   "cell_type": "markdown",
   "source": [
    "$\\pagebreak$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "a5ed03840b4cc1a0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 32"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "bf475fac64302b91"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "00100: True\n",
      "00100: True\n",
      "00100: False\n"
     ]
    },
    {
     "data": {
      "text/plain": "<IPython.core.display.Math object>",
      "text/latex": "$\\displaystyle 00100$"
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Let R1 be the regular expression 1* 0 1* 0 1* 0 1* 0 1*\n",
    "# Let R2 be the regular expression 0* (1 ∪ ε) 0* (1 ∪ ε) 0* (1 ∪ ε) 0* (1 ∪ ε) 0*\n",
    "# Let R3 be the regular expression (0 ∪ 1)* 00 (0 ∪ 1)\n",
    "# Was not supposed to be accepted by all, only bt 2 and 3\n",
    "r1 = '1*01*01*01*01*'\n",
    "r2 = '0*(1|())0*(1|())0*(1|())0*(1|())0*'\n",
    "r3 = '(0|1)*00(0|1)'\n",
    "inputs = ['00100']\n",
    "if debug:\n",
    "    regex_test(r1, inputs)\n",
    "    regex_test(r2, inputs)\n",
    "    regex_test(r3, inputs)\n",
    "Math(latexify(inputs[0]))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.547221Z",
     "start_time": "2024-03-22T22:22:26.539392Z"
    }
   },
   "id": "e3c432e6556167c7",
   "execution_count": 7
  },
  {
   "cell_type": "markdown",
   "source": [
    "$\\pagebreak$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "77d9bf7018723f74"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 33"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "afd92f4bb203df3a"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p: True\n",
      "cp: True\n",
      "pc: True\n",
      "cpc: True\n",
      "ccpcc: True\n",
      "ccpccpcc: True\n",
      "ccpccpccpcc: True\n",
      "ccpccpccpccpcc: True\n",
      "cpcpcpcpcpc: True\n",
      "pp: True\n"
     ]
    },
    {
     "data": {
      "text/plain": "<IPython.core.display.Math object>",
      "text/latex": "$\\displaystyle \\left(c^*pc^*\\right)^*$"
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define a regex where no p is touching another p, and any number of c's can be between any two p's\n",
    "q33 = '(c*pc*)*'\n",
    "inputs = [\n",
    "    'p',\n",
    "    'cp',\n",
    "    'pc',\n",
    "    'cpc',\n",
    "    'ccpcc',\n",
    "    'ccpccpcc',\n",
    "    'ccpccpccpcc',\n",
    "    'ccpccpccpccpcc',\n",
    "    'cpcpcpcpcpc',\n",
    "    'pp', # Not supposed to be here\n",
    "]\n",
    "if debug:\n",
    "    regex_test(q33, inputs)\n",
    "Math(latexify(q33))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.555155Z",
     "start_time": "2024-03-22T22:22:26.549229Z"
    }
   },
   "id": "5b8c9ad34523ea81",
   "execution_count": 8
  },
  {
   "cell_type": "markdown",
   "source": [
    "$\\pagebreak$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "567a0f904e3a8b66"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 34"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "8580d9b65031d9f7"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0: True\n",
      "1: True\n",
      "00: True\n",
      "01: True\n",
      "10: True\n",
      "11: True\n",
      "000: False\n",
      "001: False\n",
      "010: False\n",
      "0000: True\n",
      "00001: True\n",
      "001100: False\n",
      "011001110: False\n"
     ]
    },
    {
     "data": {
      "text/plain": "<IPython.core.display.Math object>",
      "text/latex": "$\\displaystyle \\left(\\left(0\\cup1\\right)\\left(0\\cup1\\right)\\left(0\\cup1\\right)\\right)^*\\left(\\left(0\\cup1\\right)\\cup\\left(00\\cup01\\cup10\\cup11\\right)\\right)$"
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define a regex where the length of the string is not a multiple of 3, on input {0, 1}\n",
    "q34 = '((0|1)(0|1)(0|1))*((0|1)|(00|01|10|11))'\n",
    "inputs = [\n",
    "    '0', # 1\n",
    "    '1', # 1\n",
    "    '00', # 2\n",
    "    '01', # 2\n",
    "    '10', # 2 \n",
    "    '11', # 2\n",
    "    '000', # 3\n",
    "    '001', # 3\n",
    "    '010', # 3\n",
    "    '0000', # 4\n",
    "    '00001', # 5\n",
    "    '001100', # 6\n",
    "    '011001110', # 9\n",
    "]\n",
    "if debug:\n",
    "    regex_test(q34, inputs)\n",
    "Math(latexify(q34))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-22T22:22:26.563180Z",
     "start_time": "2024-03-22T22:22:26.556508Z"
    }
   },
   "id": "6aa37e012a2b072d",
   "execution_count": 9
  },
  {
   "cell_type": "markdown",
   "source": [
    "$\\pagebreak$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "28524e4a3d3c6e8e"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 35\n",
    "## a.\n",
    "$$L = \\{ w \\in \\{ 0, 1 \\}^* \\ | n_0(w) \\text{ is a multiple of } 4 \\}$$\n",
    "\n",
    "## b.\n",
    "$$L = \\{ a^x b^y c^z \\ | x \\geq 1, y \\geq 2, z \\geq 3 \\}$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "1f0065878ddf68f8"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}