{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# More general machines" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from tock import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We've seen finite automata, pushdown automata, and Turing machines, but many other kinds of automata can be created by instantiating a `Machine` directly." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "m1 = Machine([BASE, BASE, BASE, BASE], state=0, input=1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first argument is required. This machine has four stores, all of type `BASE` (to be explained below).\n", "\n", "The argument `state=0` means that store 0 is the state. It's this store that is used to define the start and accept conditions, and this store that is used to define the nodes in a state transition diagram.\n", "\n", "The argument `input=1` is required and means that store 1 is the input. When the automaton is run, the input string will be placed on this store.\n", "\n", "As with other kinds of machines, you can define a start state, transitions, and accept states using `set_start_state`, `add_transition`, and `add_accept_state`." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "q1\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "q2\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε,ε,ε → ε,$,$\n", "\n", "\n", "\n", "1\n", "\n", "\n", "q5\n", "\n", "\n", "\n", "2->2\n", "\n", "\n", "a,ε,ε → ε,a,ε\n", "b,ε,ε → ε,b,ε\n", "\n", "\n", "\n", "3\n", "\n", "q3\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "[#] # #,ε,ε → ε,ε,ε\n", "\n", "\n", "\n", "3->3\n", "\n", "\n", "ε,a,ε → ε,ε,a\n", "ε,b,ε → ε,ε,b\n", "\n", "\n", "\n", "4\n", "\n", "q4\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε,$,ε → ε,ε,ε\n", "\n", "\n", "\n", "4->1\n", "\n", "\n", "␣,ε,$ → ε,ε,ε\n", "\n", "\n", "\n", "4->4\n", "\n", "\n", "a,ε,a → ε,ε,ε\n", "b,ε,b → ε,ε,ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "m1.set_start_state('q1')\n", "m1.add_transition('q1, &, &, & -> q2, &, $, $')\n", "m1.add_transition('q2, a, &, & -> q2, &, a, &')\n", "m1.add_transition('q2, b, &, & -> q2, &, b, &')\n", "m1.add_transition('q2, # # #, &, & -> q3, &, &, &')\n", "m1.add_transition('q3, &, a, & -> q3, &, &, a')\n", "m1.add_transition('q3, &, b, & -> q3, &, &, b')\n", "m1.add_transition('q3, &, $, & -> q4, &, &, &')\n", "m1.add_transition('q4, a, &, a -> q4, &, &, &')\n", "m1.add_transition('q4, b, &, b -> q4, &, &, &')\n", "m1.add_transition('q4, _, &, $ -> q5, &, &, &')\n", "m1.add_accept_state('q5')\n", "m1" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
q1[a] a b # # # a a bεε
q2[a] a b # # # a a b$$
q2[a] b # # # a a b[a] $$
q2[b] # # # a a b[a] a $$
q2[#] # # a a b[b] a a $$
q3[a] a b[b] a a $$
q3[a] a b[a] a $[b] $
q3[a] a b[a] $[a] b $
q3[a] a b$[a] a b $
q4[a] a bε[a] a b $
q4[a] bε[a] b $
q4bε[b] $
q4εε$
q5εεε
\n" ], "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "run(m1, 'a a b # # # a a b').shortest_path()" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "run(m1, 'a a b # # # b a a').has_path()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is something like a 2-stack PDA that recognizes the language $\\{w\\#\\#\\#w\\}$. It works by transferring the first half of the input to the first stack, transferring the first stack to the second stack (reversing it), then checking the second half of the input against it.\n", "\n", "This example also demonstrates that we can read three `#` signs in one transition." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Store types\n", "\n", "### BASE" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Our example above demonstrated the BASE store type. We used a BASE store like a stack, and showed that if the lhs of a transition has more than one symbol, it pops that many symbols. Likewise, if the rhs of a transition has more than one symbol, it pushes that many symbols.\n", "\n", "Additionally, a BASE store has a head like a Turing machine; it just happens that we left the head in position 0. If the rhs is `^ v`, where `v` is a string, the head moves to the cell to the left of `v`; if the rhs is `v ^`, the head moves to the cell to the right of `v`.\n", "\n", "For more information, see the reference section on [Internals](../reference/internals.rst)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### STREAM\n", "\n", "The above example looked different from a standard PDA because the right-hand sides of transitions explicitly popped input symbols as they were read. And it had to explicitly check for a blank (`_`) indicating the end of the string before accepting. To make the input look more like a finite or pushdown automaton's, use the store type STREAM.\n", "\n", "A store of type STREAM (which only really makes sense for the input store) has two properties.\n", "\n", "- Transitions do not have an entry in their right-hand side for STREAMs; it is implicitly `&`.\n", "\n", "- The input must be entirely consumed in order for the machine to accept the input string." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "q1\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "q2\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε,ε → $\n", "\n", "\n", "\n", "1\n", "\n", "\n", "q4\n", "\n", "\n", "\n", "2->2\n", "\n", "\n", "a,ε → a\n", "\n", "\n", "\n", "3\n", "\n", "q3\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "ε,ε → ε\n", "\n", "\n", "\n", "3->1\n", "\n", "\n", "ε,$ → ε\n", "\n", "\n", "\n", "3->3\n", "\n", "\n", "b,a → ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "m2 = Machine([BASE, STREAM, BASE], state=0, input=1)\n", "m2.set_start_state('q1')\n", "m2.add_transition('q1, &, & -> q2, $')\n", "m2.add_transition('q2, a, & -> q2, a')\n", "m2.add_transition('q2, &, & -> q3, &')\n", "m2.add_transition('q3, b, a -> q3, &')\n", "m2.add_transition('q3, &, $ -> q4, &')\n", "m2.add_accept_state('q4')\n", "m2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This looks just like a pushdown automaton." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### TAPE\n", "\n", "The caret (`^`) notation above can be used to move the head as in a Turing machine, but to get more standard notation, use a store of type `TAPE`. Then the right-hand-side of a transition has two entries for that store, a write and a move (which can be `L` or `R`)." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "1\n", "\n", "q1\n", "\n", "\n", "\n", "_START->1\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "\n", "q2\n", "\n", "\n", "\n", "1->0\n", "\n", "\n", "a → b,R\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "m3 = Machine([BASE, TAPE], state=0, input=1)\n", "m3.set_start_state('q1')\n", "m3.add_transition('q1, a -> q2, b, R')\n", "m3.add_accept_state('q2')\n", "m3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Low-level interface\n", "\n", "Instead of creating an automaton using `set_start_state`, `add_transition`, and `add_accept_state`, you can also directly access the members `start_config`, `transitions`, and `accept_config`.\n", "\n", "This interface completely ignores store types. Transitions are created as for BASE stores:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "q1,a → q2,b ^\n" ] } ], "source": [ "for t in m3.transitions: print(t)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "q1,a → q2,b ^\n", "q1,b → q2,c ^\n" ] } ], "source": [ "m3.transitions.append(machines.Transition('q1, b -> q2, c ^'))\n", "for t in m3.transitions: print(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`start_config` specifies an initial value for every store (not just the state). The initial value for the input is ignored, as it will be replaced by the input string." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/html": [ "q1,ε" ], "text/plain": [ "Configuration(stores=(Store(values=('q1',), position=0), Store(values=(), position=0)))" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m3.start_config" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/html": [ "q2,ε" ], "text/plain": [ "Configuration(stores=(Store(values=('q2',), position=0), Store(values=(), position=0)))" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m3.start_config = machines.Configuration('q2, &')\n", "m3.start_config" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`accept_configs` is a set of configurations, each which specifies a pattern for every store (not just the state)." ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "q2,ε\n" ] } ], "source": [ "for c in m3.accept_configs: print(c)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "# accept in state q3 if current symbol is a\n", "m3.accept_configs.add(machines.Configuration('q3, a')) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is how STREAM stores are able to require that the input is fully consumed -- by making the accept configuration for the input store to default to a blank (`_`)." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "q4,␣,ε\n" ] } ], "source": [ "for c in m2.accept_configs: print(c)" ] } ], "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.8.1" } }, "nbformat": 4, "nbformat_minor": 1 }