CS2333/Assignment 5.ipynb
2024-04-06 23:15:11 -03:00

701 lines
16 KiB
Plaintext
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

{
"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
}