Computer Science Help with SWI-Prolog Assignment

hw4.ipynb

{ "cells": [ { "cell_type": "markdown", "id": "12370bd8", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "a49990d3be0357dbca393ff30fd64b68", "grade": false, "grade_id": "cell-729052202d0ea16d", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "# Homework for Linguistics 538\n", "\n", "\n", "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel and run all cells** (in the menubar, select Kernel$\\rightarrow$Restart and run all cells).\n", "\n", "Do not add or delete any cells. If you want to try out code, you can open a second practice notebook.\n", "\n", "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name below:" ] }, { "cell_type": "markdown", "id": "ce98f652", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "595f46e9c5c531344e71e40d6e528fad", "grade": true, "grade_id": "cell-a315311983d56643", "locked": false, "points": 0, "schema_version": 3, "solution": true, "task": false } }, "source": [ "YOUR ANSWER HERE" ] }, { "cell_type": "markdown", "id": "15e2b202-29d7-46af-a0d1-874fc6fb9592", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "ecd3b45547364e98e78bac7f83ed96f2", "grade": false, "grade_id": "cell-513e00582a95bfe0", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "# Homework \\#4\n", "\n", "**Question \\#1**\n", "\n", "Write a function `alice/1` to read in the `alice.txt` corpus, replace `\\r\\n` with space, convert to lowercase, replace all punctuation with space, break into words, and return the list of words." ] }, { "cell_type": "code", "execution_count": null, "id": "69eeac04-ca6c-4f5a-a9b4-d020c0df7231", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "0d874b2b74ae35f98da3c60ce25c2875", "grade": false, "grade_id": "q1", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "96262b8c-2e4a-49aa-97c2-8fe1909cbadc", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "8e2dbf2f6016192fc44fe37a2196df62", "grade": true, "grade_id": "q1t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "{L}/(alice(X),length(X,L)), L > 30560, L < 30570." ] }, { "cell_type": "markdown", "id": "c6a619bb-05a6-4c5a-a34d-f9c0c0c7fa65", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "ef762f15773de10332edd9d61e26f29c", "grade": false, "grade_id": "cell-60490b0d3a959872", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "**Question \\#2**\n", "\n", "Write a function `redup/1` that invokes the `alice/1` function and uses backreferences to find all reduplicated words in the text.\n", "\n", "You may need a second function that `redup/1` calls to do the list matching." ] }, { "cell_type": "code", "execution_count": null, "id": "e2c7e27b-5eba-4c44-80ca-a7b498d541be", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "63bf28a101246f99be4a911e140940e7", "grade": false, "grade_id": "q2", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "dcdde8f0-fa91-4937-83d0-d8357a7430a1", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "944c158e869f146fe2cf1b72fd5a7945", "grade": true, "grade_id": "q2t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "redup(X), sort(X,Y), Y = [\"dodo\",\"ii\",\"ll\"]." ] }, { "cell_type": "markdown", "id": "d31ca580-a9af-455b-bfe9-d316b436ffc9", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "06b535542c38f515c514d3c68c301801", "grade": false, "grade_id": "cell-b0479559fec8ef1b", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "**Question \\#3**\n", "\n", "Write a function `beginend/1` that finds all words that begin and end in the same letter." ] }, { "cell_type": "code", "execution_count": null, "id": "0684afff-a144-4111-ad5d-6a0f3d86d392", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "8354665778fe6708c7badbd762e1cd25", "grade": false, "grade_id": "q3", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "4a2d72a4-c5f0-4fd1-86c2-3f1a37ad916b", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "31888213e5e05aee55d6ec679616f741", "grade": true, "grade_id": "q3t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "{}/(beginend(X), \\+member(\"happy\",X))." ] }, { "cell_type": "code", "execution_count": null, "id": "5e0cd563-bae1-4ed9-ab09-832b1e758569", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "de177381de212bcc453d04d438d1eae4", "grade": true, "grade_id": "q3t2", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "{L}/(beginend(X),length(X,L)), L > 1050, L < 1055." ] }, { "cell_type": "code", "execution_count": null, "id": "af7e130f-d6b0-4f95-a428-ea2b7ea35397", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "e007cd14f3d75aa1628c48e1a9e10a48", "grade": true, "grade_id": "q3t3", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "{}/(beginend(X),sort(X,Y),member(\"that\",Y))." ] }, { "cell_type": "markdown", "id": "c41da16b-1081-48aa-80fe-6de494d434c7", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "14c13c1f36e8442c73f4034ab08b02aa", "grade": false, "grade_id": "cell-c10b54b0520f2065", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "**Question \\#4**\n", "\n", "Write a function `string_reverse/2`. The first argument is the string and the second argument is the output.\n", "\n", "*Hint:* you can use the functions `string_chars/2` and `reverse/2` for this." ] }, { "cell_type": "code", "execution_count": null, "id": "d543a0bd-5d1d-440b-a64b-ab23689085b7", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "f3f7ff8f5587fac9036d387c8f57fbf2", "grade": false, "grade_id": "q4", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "8c78aa96-b44f-48d7-88cc-8f93a9f9dbbb", "metadata": { "deletable": false, "editable": false, "jupyter": { "source_hidden": true }, "nbgrader": { "cell_type": "code", "checksum": "e586c7dfc25ca0777f20a21b763722de", "grade": true, "grade_id": "q4t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "string_reverse(\"happy\",\"yppah\")." ] }, { "cell_type": "code", "execution_count": null, "id": "c10a4376-e2b0-4003-a787-b89e4d6abebd", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "e26b0cdfe7d8116672500eaaf6b08fbb", "grade": true, "grade_id": "q4t2", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "string_reverse(\"\",\"\")." ] }, { "cell_type": "markdown", "id": "c34b3e40-70bb-49f5-8c7b-71821bd09350", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "c150a43a32cfcce5f172d8d964074746", "grade": false, "grade_id": "cell-cc769e4bbc20df49", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "**Question \\#5**\n", "\n", "Now write a function `palindrome/1` that checks if a word is a palindrome. You should be able to do this in one line...." ] }, { "cell_type": "code", "execution_count": null, "id": "297f06eb-bb20-467d-a42e-a47933201713", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "b067b7ad66c20a6b4b5a9d3c94856954", "grade": false, "grade_id": "q5", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "2a2c7033-37ac-4331-9a8b-5fe828f1ddd7", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "8ac137e9383c3070ba49e2c182855a73", "grade": true, "grade_id": "q5t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "\\+palindrome(\"hat\")." ] }, { "cell_type": "code", "execution_count": null, "id": "09a1d615-df6b-4d14-a8ac-00e34b2850fa", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "91a16d96db12e5d91f589473071b92e9", "grade": true, "grade_id": "q5t2", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "palindrome(\"kayak\")." ] }, { "cell_type": "code", "execution_count": null, "id": "d746b083-2d90-4f85-a8e7-c85e88380077", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "f0eb91d4f84e7eee06b56d2ddd1b9446", "grade": true, "grade_id": "q5t3", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "palindrome(\"\")." ] }, { "cell_type": "markdown", "id": "d1629da9-8fb9-494f-a207-fb36427713e0", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "36550d7f2a3c35fd555a02f8abd35071", "grade": false, "grade_id": "cell-6a43986c1c734b29", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "**Question \\#6**\n", "\n", "In class, we implemented FSA by making `state`, `initial`, `final`, and `arc` basic facts in the database. Let's do an implementation now where these are structures. We will ultimately write a function `go/3` that takes three arguments: a specification of an FSA (as described below), a state, and a string. The function returns true or false depending on whether the string is accepted from that state.\n", "\n", "Here's an example:\n", "\n", "```prolog\n", "go(\n", " fsa(\n", " initial(1),\n", " final([3]),\n", " arcs([\n", " arc(1,a,2),\n", " arc(2,b,3),\n", " arc(2,b,2)\n", " ])\n", " ),\n", " 1,\n", " \"abbb\"\n", ").\n", "```\n", "\n", "The logic of the approach is that `go/3` will look at that first argument, rather than facts in the database.\n", "\n", "The first step, however, is to write a function that will extract the initial state from such an FSA representation `getinitial/2`. The first argument is an FSA representation like above and the second is the output." ] }, { "cell_type": "code", "execution_count": null, "id": "c503f523-f3be-4b12-baec-0b0b3703d39f", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "8bc815789968b4516501b2d21f270844", "grade": false, "grade_id": "q6", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "856e4763-3283-4dbe-8fc0-c79c0a5acbd7", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "0a7cea933d0725dac3c5a0c989d5d053", "grade": true, "grade_id": "q6t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "getinitial(fsa(initial(33),final([]),arcs([])),33)." ] }, { "cell_type": "code", "execution_count": null, "id": "f99feb82-96e0-4203-b4d8-2d8c592abe52", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "02ab8061721ad9678405ddfc2581f893", "grade": true, "grade_id": "q6t2", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "getinitial(fsa(initial(7),final([]),arcs([])),7)." ] }, { "cell_type": "markdown", "id": "4a37eedc-ba92-49c7-86f3-3cb52c8bac01", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "54005be7e4f077441b9f2dc95ef6ba4d", "grade": false, "grade_id": "cell-7055a3436c9116bd", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "**Question \\#7**\n", "\n", "Now write a function `isfinal/2` that tests if a state is final in some FSA. Here the first argument is an FSA specified as above and the second is a state name." ] }, { "cell_type": "code", "execution_count": null, "id": "941e6094-13be-4702-a6a0-d36bca1bc13d", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "23f59e57486fc927e116e9aa909717f4", "grade": false, "grade_id": "q7", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "f1ec1149-9424-4ba9-95cd-ae70b6396917", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "dff1bb817beda3f6e0b84eda3111629d", "grade": true, "grade_id": "q7t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "isfinal(fsa(initial(33),final([1,2,3]),arcs([])),2)." ] }, { "cell_type": "code", "execution_count": null, "id": "a5c1c691-7908-45dd-8929-a094c5aa13ff", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "94cdba33ce39fa3449e44b90816eafed", "grade": true, "grade_id": "q7t2", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "\\+isfinal(fsa(initial(33),final([1,2,3]),arcs([])),a)." ] }, { "cell_type": "markdown", "id": "24ffbd32-25c8-4d41-a026-b4c3f4077e57", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "ca111cc7d24c3e5b64107b21e57f236a", "grade": false, "grade_id": "cell-3e5271fed754cb4c", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "**Question \\#8**\n", "\n", "Now write a function `getarcs/2` to extract the arc list from an FSA." ] }, { "cell_type": "code", "execution_count": null, "id": "35426717-0f56-427f-af71-139f7b12c054", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "72e5830e2526388f816942c7ef95a139", "grade": false, "grade_id": "q8", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "14bcf064-a8c4-430b-80ff-64ccf5ddb098", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "4b43ad2022952746424ad65177440acd", "grade": true, "grade_id": "q8t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "{L}/(\n", " getarcs(\n", " fsa(initial(1),final([3]),arcs([arc(1,a,2),arc(2,b,3)])),\n", " A\n", " ),\n", " length(A,L)\n", " ),\n", " L == 2." ] }, { "cell_type": "markdown", "id": "eecbe105-ffc8-41d3-ab6c-fc4fe7f62c6c", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "f468752f1f7f0665c62ebf244b9c2ddd", "grade": false, "grade_id": "cell-3d87e681874ece67", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "**Question \\#9** (for 538 students)\n", "\n", "Write a function `go/3` as described above.\n", "\n", "You should use the functions above for this.\n", "\n", "The `go/3` function will be called by a new version of `islegal/2`. Here's the old one:\n", "\n", "```prolog\n", "islegal(Str) :�\n", " string_chars(Str,Cs),\n", " start(State),\n", " go(State,Cs).\n", "```\n", "\n", "Here's the new one:" ] }, { "cell_type": "code", "execution_count": null, "id": "3bef3dbc-a6e6-4b0a-ad89-88ddac4d18a5", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "86bd19d9175b1d408ac9fbd87f562288", "grade": false, "grade_id": "cell-44d9f7ba8c337dd8", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "islegal(F,S) :-\n", " string_chars(S,Cs),\n", " getinitial(F,I),\n", " go(F,I,Cs)." ] }, { "cell_type": "markdown", "id": "6e0568c5-b455-43f3-a632-ab7ddf490802", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "65795318c50922285cf0491993d15aae", "grade": false, "grade_id": "cell-0e65ede864787ed7", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "(Make sure to \"run\" that cell so you can use it.)\n", "\n", "Here is the old `go/2` function.\n", "\n", "```prolog\n", "go(State,[]) :� final(State), !.\n", "go(State,[C|Str]) :�\n", " arc(State,C,Otherstate),\n", " go(Otherstate,Str).\n", "```\n", "\n", "Now write `go/3`." ] }, { "cell_type": "code", "execution_count": null, "id": "eeab46c4-959e-4bf1-9e14-7e8fb0848b1e", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "20a9dc7785dcf4fee0262e47d9a3961c", "grade": false, "grade_id": "q9", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "%%CONSULT\n", "%Your code here" ] }, { "cell_type": "code", "execution_count": null, "id": "61cd3a7f-0201-4ee9-baa4-fa219c490d79", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "ae0629fc761493cabb59f2653ec0cb69", "grade": true, "grade_id": "q9t1", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "islegal(\n", " fsa(initial(1),final([3]),arcs([arc(1,a,2),arc(2,b,3)])),\n", " \"ab\"\n", ")." ] }, { "cell_type": "code", "execution_count": null, "id": "dbad4f42-44c2-4042-9457-284398454250", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "5315f7383d1f8b08214f8830c7a6e326", "grade": true, "grade_id": "q9t2", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "islegal(\n", " fsa(initial(1),final([3,1]),arcs([arc(1,a,2),arc(2,b,3)])),\n", " \"\"\n", ")." ] }, { "cell_type": "code", "execution_count": null, "id": "92ab5017-d2cf-434f-b3ef-0b03a794bab9", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "4a5dd4a04e007d2e7a580777b5010677", "grade": true, "grade_id": "q9t3", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "\\+islegal(\n", " fsa(initial(1),final([3]),arcs([arc(1,a,2),arc(2,b,3)])),\n", " \"abc\"\n", ")." ] } ], "metadata": { "kernelspec": { "display_name": "SWI Prolog", "language": "", "name": "swi_prolog_kernel" }, "language_info": { "file_extension": ".pl", "mimetype": "application/prolog", "name": "prolog" } }, "nbformat": 4, "nbformat_minor": 5 }