496 lines
55 KiB
Plaintext
496 lines
55 KiB
Plaintext
|
{
|
||
|
|
"cells": [
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 1,
|
||
|
|
"id": "initial_id",
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": true,
|
||
|
|
"ExecuteTime": {
|
||
|
|
"end_time": "2024-02-17T00:51:01.367829600Z",
|
||
|
|
"start_time": "2024-02-17T00:51:01.209832800Z"
|
||
|
|
}
|
||
|
|
},
|
||
|
|
"outputs": [],
|
||
|
|
"source": [
|
||
|
|
"# Helpers and imports\n",
|
||
|
|
"from automata.fa.nfa import NFA\n",
|
||
|
|
"\n",
|
||
|
|
"debug = False\n",
|
||
|
|
"\n",
|
||
|
|
"def nfa_test(nfa: NFA, str_arr: list[str]):\n",
|
||
|
|
" for s in str_arr:\n",
|
||
|
|
" if s == \"\":\n",
|
||
|
|
" print(f'ε is accepted: {nfa.accepts_input(s)}')\n",
|
||
|
|
" else:\n",
|
||
|
|
" print(f'{s} is accepted: {nfa.accepts_input(s)}')"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"# Q22\n",
|
||
|
|
"## (a)"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "2a3d28941b3eac7d"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"data": {
|
||
|
|
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.44.0 (0)\n -->\n<!-- Pages: 1 -->\n<svg width=\"655pt\" height=\"94pt\"\n viewBox=\"0.00 0.00 654.82 94.25\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 90.25)\">\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-90.25 650.82,-90.25 650.82,4 -4,4\"/>\n<!-- ef361926-1987-4988-9833-4dc84f84fd2e -->\n<g id=\"node1\" class=\"node\">\n<title>ef361926-1987-4988-9833-4dc84f84fd2e</title>\n<g id=\"a_node1\"><a xlink:title=\".\">\n<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-30.5\" rx=\"1.8\" ry=\"1.8\"/>\n</a>\n</g>\n</g>\n<!-- q0 -->\n<g id=\"node2\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"63.35\" cy=\"-30.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"63.35\" y=\"-26.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q0</text>\n</g>\n<!-- ef361926-1987-4988-9833-4dc84f84fd2e->q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>ef361926-1987-4988-9833-4dc84f84fd2e->q0</title>\n<g id=\"a_edge1\"><a xlink:title=\"->q0\">\n<path fill=\"none\" stroke=\"black\" d=\"M3.83,-30.5C7.36,-30.5 19.4,-30.5 31.65,-30.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"31.98,-33.48 40.48,-30.5 31.98,-27.53 31.98,-33.48\"/>\n</a>\n</g>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"154.84\" cy=\"-30.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"154.84\" y=\"-26.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q1</text>\n</g>\n<!-- q0->q1 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0->q1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M86.47,-30.5C97.53,-30.5 111.08,-30.5 123.13,-30.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"123.48,-33.48 131.98,-30.5 123.48,-27.53 123.48,-33.48\"/>\n<text text-anchor=\"middle\" x=\"109.1\" y=\"-34.3\" font-family=\"Times-Roman\" font-size=\"14.00\">0</text>\n</g>\n<!-- q2 -->\n<g id=\"node4\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"246.34\" cy=\"-30.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"246.34\" y=\"-26.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q2</text>\n</g>\n<!-- q1->q2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q1->q2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M177.97,-30.5C189.02,-30.5 202.58,-30.5 214.62,-30.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"214.97,-33.48 223.47,-30.5 214.97,-27.53 214.97,-33.48\"/>\n<text text-anchor=\"middle\" x=\"200.59\" y=\"-34.3\" font-family=\"Times-Roman\" font-size=\"14.00\">1</text>\n</g>\n<!-- q3 -->\n<g id=\"node5\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"337.84\" cy=\"-30.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"337.84\" y=\"-26.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q3</text>\n</g>\n<!-- q2->q3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q2->q3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M269.46,-30.5C280.52,-30.5 294.07,-30.5 306.12,-30.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"306.47,-33.48 314.97,-30.5 306.47,-27.53 306.47,-33.48\"/>\n<text text-anchor=\"middle\" x=\"292.09\" y=\"-34.3\" font-family=\"Times-Roman\" font-size=\"14.00\">1</text>\n</g>\n<!-- q3->q3 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q3->q3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M329.79,-51.88C328.79,-62.17 331.48,-71.25 337.84,-71.25 342.31,-71.25 344.96,-66.76 345.8,-60.52\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"348.78,-60.41 345.88,-51.88 342.83,-60.36 348.78,-60.41\"/>\n<text text-anchor=\"m
|
||
|
|
"text/plain": "<AGraph <Swig Object of type 'Agraph_t *' at 0x7f462467f9c0>>"
|
||
|
|
},
|
||
|
|
"execution_count": 2,
|
||
|
|
"metadata": {},
|
||
|
|
"output_type": "execute_result"
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"q22a = NFA(\n",
|
||
|
|
" states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'q6'},\n",
|
||
|
|
" input_symbols={'0', '1'},\n",
|
||
|
|
" transitions={\n",
|
||
|
|
" 'q0': {'0': {'q1'}},\n",
|
||
|
|
" 'q1': {'1': {'q2'}},\n",
|
||
|
|
" 'q2': {'1': {'q3'}},\n",
|
||
|
|
" 'q3': {'0': {'q3', 'q4'}, '1': {'q3'}},\n",
|
||
|
|
" 'q4': {'0': {'q5'}},\n",
|
||
|
|
" 'q5': {'0': {'q6'}}\n",
|
||
|
|
" },\n",
|
||
|
|
" initial_state='q0',\n",
|
||
|
|
" final_states={'q6'}\n",
|
||
|
|
")\n",
|
||
|
|
"# Should be true\n",
|
||
|
|
"t = [\n",
|
||
|
|
" \"011000\",\n",
|
||
|
|
" \"0110000\",\n",
|
||
|
|
" \"011010000\",\n",
|
||
|
|
" \"011011010000\"\n",
|
||
|
|
"]\n",
|
||
|
|
"# Should be false\n",
|
||
|
|
"f = [\n",
|
||
|
|
" \"\",\n",
|
||
|
|
" \"0\",\n",
|
||
|
|
" \"1\",\n",
|
||
|
|
" \"0110\",\n",
|
||
|
|
" \"0110001\",\n",
|
||
|
|
" \"011010001\",\n",
|
||
|
|
" \"011011010001\"\n",
|
||
|
|
"]\n",
|
||
|
|
"if debug:\n",
|
||
|
|
" nfa_test(q22a, t)\n",
|
||
|
|
" print('-'*20)\n",
|
||
|
|
" nfa_test(q22a, f)\n",
|
||
|
|
"q22a.show_diagram()"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false,
|
||
|
|
"ExecuteTime": {
|
||
|
|
"end_time": "2024-02-17T00:51:01.419829300Z",
|
||
|
|
"start_time": "2024-02-17T00:51:01.419829300Z"
|
||
|
|
}
|
||
|
|
},
|
||
|
|
"id": "8ec96b76671bd51f",
|
||
|
|
"execution_count": 2
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"## (b)"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "4c318b8332558fe6"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"data": {
|
||
|
|
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.44.0 (0)\n -->\n<!-- Pages: 1 -->\n<svg width=\"289pt\" height=\"278pt\"\n viewBox=\"0.00 0.00 288.84 278.25\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 274.25)\">\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-274.25 284.84,-274.25 284.84,4 -4,4\"/>\n<!-- b36964c3-7cac-44c2-80ec-5a57927f24cb -->\n<g id=\"node1\" class=\"node\">\n<title>b36964c3-7cac-44c2-80ec-5a57927f24cb</title>\n<g id=\"a_node1\"><a xlink:title=\".\">\n<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-118.5\" rx=\"1.8\" ry=\"1.8\"/>\n</a>\n</g>\n</g>\n<!-- q0 -->\n<g id=\"node2\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"63.35\" cy=\"-118.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"63.35\" y=\"-114.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q0</text>\n</g>\n<!-- b36964c3-7cac-44c2-80ec-5a57927f24cb->q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>b36964c3-7cac-44c2-80ec-5a57927f24cb->q0</title>\n<g id=\"a_edge1\"><a xlink:title=\"->q0\">\n<path fill=\"none\" stroke=\"black\" d=\"M3.83,-118.5C7.36,-118.5 19.4,-118.5 31.65,-118.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"31.98,-121.48 40.48,-118.5 31.98,-115.53 31.98,-121.48\"/>\n</a>\n</g>\n</g>\n<!-- q3 -->\n<g id=\"node3\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"154.84\" cy=\"-214.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"154.84\" y=\"-210.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q3</text>\n</g>\n<!-- q0->q3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0->q3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M79.53,-134.78C94.06,-150.37 116.11,-174.03 132.43,-191.52\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"130.62,-193.94 138.59,-198.13 134.97,-189.89 130.62,-193.94\"/>\n<text text-anchor=\"middle\" x=\"109.1\" y=\"-172.3\" font-family=\"Times-Roman\" font-size=\"14.00\">c</text>\n</g>\n<!-- q1 -->\n<g id=\"node4\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"154.84\" cy=\"-118.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"154.84\" y=\"-114.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q1</text>\n</g>\n<!-- q0->q1 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q0->q1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M86.47,-118.5C97.53,-118.5 111.08,-118.5 123.13,-118.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"123.48,-121.48 131.98,-118.5 123.48,-115.53 123.48,-121.48\"/>\n<text text-anchor=\"middle\" x=\"109.1\" y=\"-122.3\" font-family=\"Times-Roman\" font-size=\"14.00\">a</text>\n</g>\n<!-- q2 -->\n<g id=\"node5\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"154.84\" cy=\"-22.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"154.84\" y=\"-18.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q2</text>\n</g>\n<!-- q0->q2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q0->q2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M79.53,-102.21C94.06,-86.63 116.11,-62.97 132.43,-45.47\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"134.97,-47.11 138.59,-38.86 130.62,-43.05 134.97,-47.11\"/>\n<text text-anchor=\"middle\" x=\"109.1\" y=\"-76.3\" font-family=\"Times-Roman\" font-size=\"14.00\">b</text>\n</g>\n<!-- q3->q3 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q3->q3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M146.8,-235.88C145.8,-246.17 148.48,-255.25 154.84,-255.25 159.32,-255.25 161.97,-250.76 162.81,-244.52\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"165.79,-244.41 162.89,-235.88 159
|
||
|
|
"text/plain": "<AGraph <Swig Object of type 'Agraph_t *' at 0x7f462469b300>>"
|
||
|
|
},
|
||
|
|
"execution_count": 3,
|
||
|
|
"metadata": {},
|
||
|
|
"output_type": "execute_result"
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"q22b = NFA(\n",
|
||
|
|
" states={'q0', 'q1', 'q2', 'q3', 'q4'},\n",
|
||
|
|
" input_symbols={'a', 'b', 'c'},\n",
|
||
|
|
" transitions={\n",
|
||
|
|
" 'q0': {'a': {'q1'}, 'b': {'q2'}, 'c': {'q3'}},\n",
|
||
|
|
" 'q1': {'a': {'q1', 'q4'}, 'b': {'q1'}, 'c': {'q1'}},\n",
|
||
|
|
" 'q2': {'a': {'q2'}, 'b': {'q2', 'q4'}, 'c': {'q2'}},\n",
|
||
|
|
" 'q3': {'a': {'q3'}, 'b': {'q3'}, 'c': {'q3', 'q4'}},\n",
|
||
|
|
" 'q4': {}\n",
|
||
|
|
" },\n",
|
||
|
|
" initial_state='q0',\n",
|
||
|
|
" final_states={'q4'}\n",
|
||
|
|
")\n",
|
||
|
|
"\n",
|
||
|
|
"# Should be true\n",
|
||
|
|
"t = [\n",
|
||
|
|
" \"aa\",\n",
|
||
|
|
" \"bb\",\n",
|
||
|
|
" \"cc\",\n",
|
||
|
|
" \"aba\",\n",
|
||
|
|
" \"bab\",\n",
|
||
|
|
" \"cac\",\n",
|
||
|
|
" \"aabca\",\n",
|
||
|
|
" \"bcbab\",\n",
|
||
|
|
" \"ccccc\",\n",
|
||
|
|
"]\n",
|
||
|
|
"f = [\n",
|
||
|
|
" \"\",\n",
|
||
|
|
" \"a\",\n",
|
||
|
|
" \"b\",\n",
|
||
|
|
" \"c\",\n",
|
||
|
|
" \"abc\",\n",
|
||
|
|
" \"ab\",\n",
|
||
|
|
" \"bc\",\n",
|
||
|
|
" \"ca\",\n",
|
||
|
|
" \"ac\",\n",
|
||
|
|
" \"ba\",\n",
|
||
|
|
" \"abbbbbc\",\n",
|
||
|
|
" \"aaaaaaaaaaaabbbbbbbbbbbbcccccccccccccccc\",\n",
|
||
|
|
" \"abcabac\",\n",
|
||
|
|
" \"bbbbbbbbbbba\",\n",
|
||
|
|
"]\n",
|
||
|
|
"if debug:\n",
|
||
|
|
" nfa_test(q22b, t)\n",
|
||
|
|
" print('-'*20)\n",
|
||
|
|
" nfa_test(q22b, f)\n",
|
||
|
|
"q22b.show_diagram()"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false,
|
||
|
|
"ExecuteTime": {
|
||
|
|
"end_time": "2024-02-17T00:51:01.425828900Z",
|
||
|
|
"start_time": "2024-02-17T00:51:01.419829300Z"
|
||
|
|
}
|
||
|
|
},
|
||
|
|
"id": "b36d3c2c58fe93b7",
|
||
|
|
"execution_count": 3
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"$\\pagebreak$"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "5a3996c26ce8cfbc"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"# Q23"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "9551c6ce7a0990"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"data": {
|
||
|
|
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.44.0 (0)\n -->\n<!-- Pages: 1 -->\n<svg width=\"404pt\" height=\"214pt\"\n viewBox=\"0.00 0.00 404.34 213.68\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 209.68)\">\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-209.68 400.34,-209.68 400.34,4 -4,4\"/>\n<!-- c6536698-09e6-4b0c-b9c0-932845697f5e -->\n<g id=\"node1\" class=\"node\">\n<title>c6536698-09e6-4b0c-b9c0-932845697f5e</title>\n<g id=\"a_node1\"><a xlink:title=\".\">\n<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-88.19\" rx=\"1.8\" ry=\"1.8\"/>\n</a>\n</g>\n</g>\n<!-- q0 -->\n<g id=\"node2\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"63.35\" cy=\"-88.19\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"63.35\" y=\"-84.49\" font-family=\"Times-Roman\" font-size=\"14.00\">q0</text>\n</g>\n<!-- c6536698-09e6-4b0c-b9c0-932845697f5e->q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>c6536698-09e6-4b0c-b9c0-932845697f5e->q0</title>\n<g id=\"a_edge1\"><a xlink:title=\"->q0\">\n<path fill=\"none\" stroke=\"black\" d=\"M3.83,-88.19C7.36,-88.19 19.4,-88.19 31.65,-88.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"31.98,-91.16 40.48,-88.19 31.98,-85.21 31.98,-91.16\"/>\n</a>\n</g>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"152.84\" cy=\"-120.18\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"152.84\" y=\"-116.48\" font-family=\"Times-Roman\" font-size=\"14.00\">q1</text>\n</g>\n<!-- q0->q1 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0->q1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M85.08,-95.77C96.42,-99.91 110.63,-105.11 123.02,-109.64\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"122.26,-112.53 131.26,-112.65 124.3,-106.94 122.26,-112.53\"/>\n<text text-anchor=\"middle\" x=\"108.1\" y=\"-107.98\" font-family=\"Times-Roman\" font-size=\"14.00\">ε</text>\n</g>\n<!-- q5 -->\n<g id=\"node4\" class=\"node\">\n<title>q5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"152.84\" cy=\"-57.19\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"152.84\" y=\"-53.49\" font-family=\"Times-Roman\" font-size=\"14.00\">q5</text>\n</g>\n<!-- q0->q5 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q0->q5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M85.08,-80.84C96.42,-76.82 110.63,-71.79 123.02,-67.4\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"124.24,-70.12 131.26,-64.48 122.25,-64.51 124.24,-70.12\"/>\n<text text-anchor=\"middle\" x=\"108.1\" y=\"-76.99\" font-family=\"Times-Roman\" font-size=\"14.00\">ε</text>\n</g>\n<!-- q1->q1 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q1->q1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M144.8,-141.57C143.8,-151.85 146.48,-160.93 152.84,-160.93 157.32,-160.93 159.97,-156.44 160.81,-150.2\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"163.79,-150.1 160.89,-141.57 157.84,-150.05 163.79,-150.1\"/>\n<text text-anchor=\"middle\" x=\"152.84\" y=\"-164.73\" font-family=\"Times-Roman\" font-size=\"14.00\">0,1</text>\n</g>\n<!-- q2 -->\n<g id=\"node5\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"257.34\" cy=\"-183.18\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"257.34\" y=\"-179.48\" font-family=\"Times-Roman\" font-size=\"14.00\">q2</text>\n</g>\n<!-- q1->q2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q1->q2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M172.64,-131.74C188.83,-141.68 212.34,-156.14 230.33,-167.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"228.86,-169.78 237.66,-
|
||
|
|
"text/plain": "<AGraph <Swig Object of type 'Agraph_t *' at 0x7f461c387e10>>"
|
||
|
|
},
|
||
|
|
"execution_count": 4,
|
||
|
|
"metadata": {},
|
||
|
|
"output_type": "execute_result"
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"q23 = NFA(\n",
|
||
|
|
" states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'q6', 'q7'},\n",
|
||
|
|
" input_symbols={'0', '1'},\n",
|
||
|
|
" transitions={\n",
|
||
|
|
" 'q0': {'': {'q1', 'q5'}},\n",
|
||
|
|
" 'q1': {'0': {'q1', 'q2'}, '1': {'q1', 'q3'}},\n",
|
||
|
|
" 'q2': {'0': {'q4'}},\n",
|
||
|
|
" 'q3': {'1': {'q4'}},\n",
|
||
|
|
" 'q5': {'0': {'q6'}, '1': {'q6'}},\n",
|
||
|
|
" 'q6': {'0': {'q7'}, '1': {'q7'}},\n",
|
||
|
|
" 'q7': {'0': {'q5'}, '1': {'q5'}}\n",
|
||
|
|
" },\n",
|
||
|
|
" initial_state='q0',\n",
|
||
|
|
" final_states={'q4', 'q7'}\n",
|
||
|
|
")\n",
|
||
|
|
"t = [\n",
|
||
|
|
" '00',\n",
|
||
|
|
" '11',\n",
|
||
|
|
" '01',\n",
|
||
|
|
" '00000',\n",
|
||
|
|
" '11111',\n",
|
||
|
|
" '01010',\n",
|
||
|
|
" '01111100',\n",
|
||
|
|
" '10010111',\n",
|
||
|
|
" '011100',\n",
|
||
|
|
" '10010',\n",
|
||
|
|
" '10001011',\n",
|
||
|
|
"]\n",
|
||
|
|
"f = [\n",
|
||
|
|
" '',\n",
|
||
|
|
" '0',\n",
|
||
|
|
" '1',\n",
|
||
|
|
" '101',\n",
|
||
|
|
" '010',\n",
|
||
|
|
" '0001',\n",
|
||
|
|
" '1110',\n",
|
||
|
|
" '0101',\n",
|
||
|
|
" '0111110',\n",
|
||
|
|
"]\n",
|
||
|
|
"if debug:\n",
|
||
|
|
" nfa_test(q23, t)\n",
|
||
|
|
" print('-'*20)\n",
|
||
|
|
" nfa_test(q23, f)\n",
|
||
|
|
"q23.show_diagram()"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false,
|
||
|
|
"ExecuteTime": {
|
||
|
|
"end_time": "2024-02-17T00:51:01.456829Z",
|
||
|
|
"start_time": "2024-02-17T00:51:01.428830800Z"
|
||
|
|
}
|
||
|
|
},
|
||
|
|
"id": "7055f3d7e013c8bf",
|
||
|
|
"execution_count": 4
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"$\\pagebreak$"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "35ed9908c8809b00"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"# Q24\n",
|
||
|
|
"## (a) \n",
|
||
|
|
"The language for this graph is:\n",
|
||
|
|
"$$L = \\{ w \\in \\{ 0, 1, 2 \\}^* \\ | \\text{ The fourth last symbol in } w \\text{ is } 0 \\text { and the second last symbol in } w \\text{ is } 2 \\}$$\n",
|
||
|
|
"\n",
|
||
|
|
"## (b)\n",
|
||
|
|
"The language for this graph is:\n",
|
||
|
|
"$$L = \\{ w \\in \\{ a, b, c \\}^* \\ | \\ w \\text{ contains the substring } ab \\text { or } w \\text{ contains the substring } ac \\}$$"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "d359a31d044ce735"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"$\\pagebreak$"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "144bcb36426add4a"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"# Q26\n",
|
||
|
|
"## (a)"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "233aa8019cdbe103"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"data": {
|
||
|
|
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.44.0 (0)\n -->\n<!-- Pages: 1 -->\n<svg width=\"530pt\" height=\"290pt\"\n viewBox=\"0.00 0.00 530.48 290.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 286)\">\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-286 526.48,-286 526.48,4 -4,4\"/>\n<!-- 395dc4d0-bf07-4c32-b931-cf10ac1006e5 -->\n<g id=\"node1\" class=\"node\">\n<title>395dc4d0-bf07-4c32-b931-cf10ac1006e5</title>\n<g id=\"a_node1\"><a xlink:title=\".\">\n<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-140.5\" rx=\"1.8\" ry=\"1.8\"/>\n</a>\n</g>\n</g>\n<!-- q00 -->\n<g id=\"node2\" class=\"node\">\n<title>q00</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"69.2\" cy=\"-140.5\" rx=\"28.5\" ry=\"28.5\"/>\n<text text-anchor=\"middle\" x=\"69.2\" y=\"-136.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q00</text>\n</g>\n<!-- 395dc4d0-bf07-4c32-b931-cf10ac1006e5->q00 -->\n<g id=\"edge1\" class=\"edge\">\n<title>395dc4d0-bf07-4c32-b931-cf10ac1006e5->q00</title>\n<g id=\"a_edge1\"><a xlink:title=\"->q00\">\n<path fill=\"none\" stroke=\"black\" d=\"M3.94,-140.5C7.55,-140.5 19.26,-140.5 31.72,-140.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"31.87,-143.48 40.37,-140.5 31.87,-137.53 31.87,-143.48\"/>\n</a>\n</g>\n</g>\n<!-- q00->q00 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q00->q00</title>\n<path fill=\"none\" stroke=\"black\" d=\"M60.61,-167.78C60.22,-178.33 63.09,-187.09 69.2,-187.09 73.49,-187.09 76.18,-182.76 77.27,-176.52\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"80.26,-176.44 77.79,-167.78 74.32,-176.09 80.26,-176.44\"/>\n<text text-anchor=\"middle\" x=\"69.2\" y=\"-190.89\" font-family=\"Times-Roman\" font-size=\"14.00\">a,b,c,d</text>\n</g>\n<!-- q01 -->\n<g id=\"node3\" class=\"node\">\n<title>q01</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"172.39\" cy=\"-253.5\" rx=\"28.5\" ry=\"28.5\"/>\n<text text-anchor=\"middle\" x=\"172.39\" y=\"-249.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q01</text>\n</g>\n<!-- q00->q01 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q00->q01</title>\n<path fill=\"none\" stroke=\"black\" d=\"M88.99,-161.49C105.32,-179.72 129.09,-206.26 146.9,-226.15\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"144.81,-228.28 152.7,-232.62 149.24,-224.31 144.81,-228.28\"/>\n<text text-anchor=\"middle\" x=\"120.79\" y=\"-203.3\" font-family=\"Times-Roman\" font-size=\"14.00\">a</text>\n</g>\n<!-- q02 -->\n<g id=\"node4\" class=\"node\">\n<title>q02</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"172.39\" cy=\"-178.5\" rx=\"28.5\" ry=\"28.5\"/>\n<text text-anchor=\"middle\" x=\"172.39\" y=\"-174.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q02</text>\n</g>\n<!-- q00->q02 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q00->q02</title>\n<path fill=\"none\" stroke=\"black\" d=\"M96.26,-150.28C108.77,-154.98 123.92,-160.67 137.33,-165.71\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"136.42,-168.55 145.42,-168.74 138.5,-162.98 136.42,-168.55\"/>\n<text text-anchor=\"middle\" x=\"120.79\" y=\"-164.3\" font-family=\"Times-Roman\" font-size=\"14.00\">b</text>\n</g>\n<!-- q03 -->\n<g id=\"node5\" class=\"node\">\n<title>q03</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"172.39\" cy=\"-103.5\" rx=\"28.5\" ry=\"28.5\"/>\n<text text-anchor=\"middle\" x=\"172.39\" y=\"-99.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q03</text>\n</g>\n<!-- q00->q03 -->\n<g id=\"edge5\" class=\"edge\">\n<title>q00->q03</title>\n<path fill=\"none\" stroke=\"black\" d=\"M96.26,-130.97C108.67,-126.43 123.69,-120.94 137.02,-116.06\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"
|
||
|
|
"text/plain": "<AGraph <Swig Object of type 'Agraph_t *' at 0x7f461c3a7a20>>"
|
||
|
|
},
|
||
|
|
"execution_count": 5,
|
||
|
|
"metadata": {},
|
||
|
|
"output_type": "execute_result"
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"q26a = NFA(\n",
|
||
|
|
"\tstates={'q00', 'q01', 'q02', 'q03', 'q04', 'q05', 'q06', 'q07', 'q08', 'q09', 'q10', 'q11', 'q12', 'q13'},\n",
|
||
|
|
" input_symbols={'a', 'b', 'c', 'd'},\n",
|
||
|
|
" transitions={\n",
|
||
|
|
" 'q00': {'a': {'q00', 'q01'}, 'b': {'q00', 'q02'}, 'c': {'q00', 'q03'}, 'd': {'q00', 'q04'}},\n",
|
||
|
|
" 'q01': {'a': {'q05'}},\n",
|
||
|
|
" 'q02': {'b': {'q06'}},\n",
|
||
|
|
" 'q03': {'c': {'q07'}},\n",
|
||
|
|
" 'q04': {'d': {'q08'}},\n",
|
||
|
|
"\t 'q05': {'a': {'q09'}},\n",
|
||
|
|
" 'q06': {'b': {'q10'}},\n",
|
||
|
|
" 'q07': {'c': {'q11'}},\n",
|
||
|
|
" 'q08': {'d': {'q12'}},\n",
|
||
|
|
" 'q09': {'a': {'q13'}},\n",
|
||
|
|
" 'q10': {'b': {'q13'}},\n",
|
||
|
|
" 'q11': {'c': {'q13'}},\n",
|
||
|
|
" 'q12': {'d': {'q13'}},\n",
|
||
|
|
" 'q13': {'a': {'q13'}, 'b': {'q13'}, 'c': {'q13'}, 'd': {'q13'}},\n",
|
||
|
|
" },\n",
|
||
|
|
" initial_state='q00',\n",
|
||
|
|
" final_states={'q13'},\n",
|
||
|
|
")\n",
|
||
|
|
"t = [\n",
|
||
|
|
" 'aaaa',\n",
|
||
|
|
" 'bbbb',\n",
|
||
|
|
" 'cccc',\n",
|
||
|
|
" 'dddd',\n",
|
||
|
|
" 'abbbba',\n",
|
||
|
|
" 'acccca',\n",
|
||
|
|
" 'adddda',\n",
|
||
|
|
" 'abbbbabbbba',\n",
|
||
|
|
" 'accccacccca',\n",
|
||
|
|
" 'addddadddda',\n",
|
||
|
|
" 'aaabbbcccdddd',\n",
|
||
|
|
"]\n",
|
||
|
|
"f = [\n",
|
||
|
|
" 'abcd',\n",
|
||
|
|
" 'abdc',\n",
|
||
|
|
" 'acbd',\n",
|
||
|
|
" 'acdb',\n",
|
||
|
|
" 'aaabb',\n",
|
||
|
|
" 'abbbc',\n",
|
||
|
|
" 'abbbd',\n",
|
||
|
|
"]\n",
|
||
|
|
"if debug:\n",
|
||
|
|
" nfa_test(q26a, t)\n",
|
||
|
|
" print('-'*20)\n",
|
||
|
|
" nfa_test(q26a, f)\n",
|
||
|
|
"q26a.show_diagram()"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false,
|
||
|
|
"ExecuteTime": {
|
||
|
|
"end_time": "2024-02-17T00:51:01.510831200Z",
|
||
|
|
"start_time": "2024-02-17T00:51:01.457831400Z"
|
||
|
|
}
|
||
|
|
},
|
||
|
|
"id": "ba55249fa215010e",
|
||
|
|
"execution_count": 5
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"source": [
|
||
|
|
"## (b)"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false
|
||
|
|
},
|
||
|
|
"id": "c55b1fd818f8da4e"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"data": {
|
||
|
|
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.44.0 (0)\n -->\n<!-- Pages: 1 -->\n<svg width=\"494pt\" height=\"226pt\"\n viewBox=\"0.00 0.00 493.83 226.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 222)\">\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-222 489.83,-222 489.83,4 -4,4\"/>\n<!-- 9a93236f-ac2b-4384-8c2a-d9686587f8ad -->\n<g id=\"node1\" class=\"node\">\n<title>9a93236f-ac2b-4384-8c2a-d9686587f8ad</title>\n<g id=\"a_node1\"><a xlink:title=\".\">\n<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-110.5\" rx=\"1.8\" ry=\"1.8\"/>\n</a>\n</g>\n</g>\n<!-- q0 -->\n<g id=\"node2\" class=\"node\">\n<title>q0</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"67.35\" cy=\"-110.5\" rx=\"26.5\" ry=\"26.5\"/>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"67.35\" cy=\"-110.5\" rx=\"30.5\" ry=\"30.5\"/>\n<text text-anchor=\"middle\" x=\"67.35\" y=\"-106.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q0</text>\n</g>\n<!-- 9a93236f-ac2b-4384-8c2a-d9686587f8ad->q0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>9a93236f-ac2b-4384-8c2a-d9686587f8ad->q0</title>\n<g id=\"a_edge1\"><a xlink:title=\"->q0\">\n<path fill=\"none\" stroke=\"black\" d=\"M3.9,-110.5C7.49,-110.5 19.32,-110.5 31.74,-110.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"31.83,-113.48 40.33,-110.5 31.83,-107.53 31.83,-113.48\"/>\n</a>\n</g>\n</g>\n<!-- q1 -->\n<g id=\"node3\" class=\"node\">\n<title>q1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"166.84\" cy=\"-161.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"166.84\" y=\"-157.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q1</text>\n</g>\n<!-- q0->q1 -->\n<g id=\"edge2\" class=\"edge\">\n<title>q0->q1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M91.45,-122.58C105.52,-129.94 123.56,-139.38 138.36,-147.12\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"137.28,-149.91 146.19,-151.22 140.04,-144.64 137.28,-149.91\"/>\n<text text-anchor=\"middle\" x=\"117.1\" y=\"-141.3\" font-family=\"Times-Roman\" font-size=\"14.00\">a</text>\n</g>\n<!-- q5 -->\n<g id=\"node4\" class=\"node\">\n<title>q5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"166.84\" cy=\"-60.5\" rx=\"26.5\" ry=\"26.5\"/>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"166.84\" cy=\"-60.5\" rx=\"30.5\" ry=\"30.5\"/>\n<text text-anchor=\"middle\" x=\"166.84\" y=\"-56.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q5</text>\n</g>\n<!-- q0->q5 -->\n<g id=\"edge3\" class=\"edge\">\n<title>q0->q5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M91.45,-98.65C104.35,-92.04 120.6,-83.7 134.61,-76.52\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"136.36,-78.96 142.57,-72.44 133.65,-73.67 136.36,-78.96\"/>\n<text text-anchor=\"middle\" x=\"117.1\" y=\"-90.3\" font-family=\"Times-Roman\" font-size=\"14.00\">b</text>\n</g>\n<!-- q2 -->\n<g id=\"node5\" class=\"node\">\n<title>q2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"266.34\" cy=\"-195.5\" rx=\"22.5\" ry=\"22.5\"/>\n<text text-anchor=\"middle\" x=\"266.34\" y=\"-191.8\" font-family=\"Times-Roman\" font-size=\"14.00\">q2</text>\n</g>\n<!-- q1->q2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>q1->q2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M188.72,-169.27C195.95,-171.92 204.11,-174.88 211.59,-177.5 219.66,-180.32 228.43,-183.3 236.51,-186.01\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"235.62,-188.85 244.62,-188.71 237.49,-183.2 235.62,-188.85\"/>\n<text text-anchor=\"middle\" x=\"216.59\" y=\"-184.3\" font-family=\"Times-Roman\" font-size=\"14.00\">a</text>\n</g>\n<!-- q3 -->\n<g id=\"node6\" class=\"node\">\n<title>q3</title>\n<ellipse fill=\"none\" stro
|
||
|
|
"text/plain": "<AGraph <Swig Object of type 'Agraph_t *' at 0x7f461c387c90>>"
|
||
|
|
},
|
||
|
|
"execution_count": 6,
|
||
|
|
"metadata": {},
|
||
|
|
"output_type": "execute_result"
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"q26b = NFA(\n",
|
||
|
|
"\tstates={'q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'q6', 'q7', 'q8'},\n",
|
||
|
|
"\tinput_symbols={'a', 'b', 'c'},\n",
|
||
|
|
"\ttransitions={\n",
|
||
|
|
"\t\t'q0': {'a': {'q1'}, 'b': {'q5'}},\n",
|
||
|
|
"\t\t'q1': {'a': {'q2'}, 'b': {'q3'}},\n",
|
||
|
|
"\t\t'q2': {'a': {'q1'}},\n",
|
||
|
|
"\t\t'q3': {'b': {'q4'}},\n",
|
||
|
|
"\t\t'q4': {'b': {'q3'}},\n",
|
||
|
|
"\t\t'q5': {'b': {'q5'}, 'c': {'q6'}},\n",
|
||
|
|
"\t\t'q6': {'c': {'q7'}},\n",
|
||
|
|
"\t\t'q7': {'c': {'q8'}},\n",
|
||
|
|
"\t\t'q8': {'c': {'q6'}},\n",
|
||
|
|
"\t},\n",
|
||
|
|
"\tinitial_state='q0',\n",
|
||
|
|
"\tfinal_states={'q0', 'q3', 'q5', 'q8'},\n",
|
||
|
|
")\n",
|
||
|
|
"t = [\n",
|
||
|
|
" 'ab',\n",
|
||
|
|
" 'aaabbb',\n",
|
||
|
|
" 'aaaaabbbbb',\n",
|
||
|
|
" 'b',\n",
|
||
|
|
" 'bb',\n",
|
||
|
|
" 'bbccc',\n",
|
||
|
|
" 'bbcccccc',\n",
|
||
|
|
"]\n",
|
||
|
|
"f = [\n",
|
||
|
|
" 'a',\n",
|
||
|
|
" 'aaa',\n",
|
||
|
|
" 'aaaa',\n",
|
||
|
|
" 'bba',\n",
|
||
|
|
" 'ca',\n",
|
||
|
|
" 'cb',\n",
|
||
|
|
" 'cc',\n",
|
||
|
|
" 'ccca',\n",
|
||
|
|
" 'bbba',\n",
|
||
|
|
" 'bbbbbc',\n",
|
||
|
|
"]\n",
|
||
|
|
"if debug:\n",
|
||
|
|
" nfa_test(q26b, t)\n",
|
||
|
|
" print('-'*20)\n",
|
||
|
|
" nfa_test(q26b, f)\n",
|
||
|
|
"\n",
|
||
|
|
"q26b.show_diagram()"
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"collapsed": false,
|
||
|
|
"ExecuteTime": {
|
||
|
|
"end_time": "2024-02-17T00:51:01.566831900Z",
|
||
|
|
"start_time": "2024-02-17T00:51:01.509831400Z"
|
||
|
|
}
|
||
|
|
},
|
||
|
|
"id": "b44d21890b7c5fe6",
|
||
|
|
"execution_count": 6
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"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
|
||
|
|
}
|