{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Set 6: TM\n", "\n", "csc427: Theory of Automata and Complexity. \n", " \n", "university of miami\n", " \n", "spring...

turing machine


{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Set 6: TM\n", "\n", "csc427: Theory of Automata and Complexity. \n", " \n", "university of miami\n", " \n", "spring 2021.\n", " \n", "Burton Rosenberg.\n", " \n", " \n", "created: 6 April 2021\n", " last update: 14 April 2021\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "\n", "### Student name:\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### TuringMachine class" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import string\n", "import sys\n", "import os\n", "import argparse\n", "import re\n", "\n", "#\n", "# tm-sim.py\n", "#\n", "# author: bjr\n", "# date: 21 mar 2020\n", "# last update: 22 mar 2020\n", "# 16 mar 2021, updated \n", "# 3 apr 2021, return conventions for accept/reject\n", "# verbose_levels reimplemented\n", "# character # is not allowed as a tape symbol\n", "# for magical reasons, then \" is also not allowed\n", "# added class method help()\n", "# \n", "#\n", "# copyright: Creative Commons. See http://www.cs.miami.edu/home/burt\n", "#\n", "\n", "# GRAMMAR for the TM description\n", "\n", "# Comments (not shown in BNF) begin with a hash # and continue to the end\n", "# of the line\n", "# The ident tokens are states\n", "# The symbol tokens are tape symbolss\n", "# The StateTransition semantics is:\n", "# tape_symbol_read tape_symbol_written action new_state\n", "# The underscore _ is a tape blank:\n", "# The : in a transition rule is the default tape symbol match when there is no\n", "# exactly matching transition rule; in the target section of the rule it \n", "# is the value of the matchined tape symbol.\n", "\n", "# A missing transition is considered a reject, not an error\n", "\n", "class TuringMachine:\n", " \n", " verbose_levels = {'none':0,'verbose':1,'explain':2, 'debug':3}\n", " result_reasons = ['ok', 'transition missing', 'time limit']\n", "\n", " grammar = \"\"\"\n", " M-> (Stanza [emptyline])*\n", " Stanza-> StartStanza | AcceptStanza | RejectStanza | StateStanze\n", " StartStanza-> \"start\" \":\" ident\n", " AcceptStanza-> \"accept\" \":\" ident ([newline] [indent] ident])*\n", " RejectStanza-> \"reject\" \":\" ident ([newline] [indent] ident])*\n", " StateStanze-> \"state\" \":\" ident ([newline] [indent] StateTransition)+\n", " StateTransition-> (symbol|special) (symbol|special) action ident\n", " action-> l|r|n|L|R|N\n", " symbol-> \\w[!$-/] # note: a tape symbol\n", " special-> \":\"\n", " ident-> \\w+ # note: name of a state\n", "\n", " \"\"\"\n", "\n", " def __init__(self):\n", " self.start_state = \"\" # is an state identifier\n", " self.accept_states = set() # is a set of state identifiers\n", " self.reject_states = set() # is a set of state identifiers\n", " self.transitions = {} # is a map of (state,symbol):(state,symbol,action)\n", " self.current_state = \"\" \n", " self.step_counter = 0\n", " self.all_actions = [\"r\",\"l\",\"n\"]\n", " self.tape = ['_'] # is a list of symbols\n", " self.position = 0\n", " self.verbose = 0\n", " self.result = 0\n", "\n", " def set_start_state(self,state):\n", " self.start_state = state\n", "\n", " def set_tape(self,tape_string):\n", " self.tape = ['_' if symbol==':' or symbol==' ' else \n", " symbol for symbol in tape_string]\n", "\n", " def add_accept_state(self,state):\n", " self.accept_states.add(state)\n", "\n", " def add_reject_state(self,state):\n", " self.reject_states.add(state)\n", " \n", " def get_current_state(self):\n", " return self.curent_state\n", "\n", " def add_transition(self,state_from,read_symbol,\n", " write_symbol,action,state_to):\n", "\n", " if action.lower() not in self.all_actions:\n", " # return something instead, nobody likes a chatty program\n", " return \"WARNING: unrecognized action.\"\n", " x = (state_from, read_symbol)\n", " if x in self.transitions:\n", " # return something instead, nobody likes a chatty program\n", " return \"WARNING: multiple outgoing states not allowed for DFA's.\"\n", " self.transitions[x] = (state_to,write_symbol,action)\n", " return None\n", "\n", " def restart(self,tape_string):\n", " self.current_state = self.start_state\n", " self.position = 0\n", " if len(tape_string)==0 :\n", " tape_string = '_'\n", " self.set_tape(tape_string)\n", " self.step_counter = 1\n", "\n", " def step_transition(self):\n", " c_s = self.current_state\n", " x = (c_s,self.tape[self.position])\n", " \n", " if x in self.transitions:\n", " (new_state, symbol, action ) = self.transitions[x]\n", " elif (c_s,':') in self.transitions:\n", " # wildcard code\n",