Answered step by step
Verified Expert Solution
Question
1 Approved Answer
We want a Turing machine that checks if a string is a palindrome, i . e . is the same as when read backwards. The
We want a Turing machine that checks if a string is a palindrome, ie is the same as when read backwards. The input tape consists of zero or more zeros and ones, followed by blanks. The output is if the input is a palindrome, otherwise
You are to write the transition table for the Turing machine. Organise the transitions by state or by the order they're executed.
RIGHT
LEFT
STAY
MAXSTEPS
def runTMtm:dict, tape:list, debug:bool list:
Run Turing machine tm on tape and return the resulting output.
The machine runs from state 'start' until it halts or has done MAXSTEPS.
The output is the tape's content from the head onwards.
If debug is True, print each configuration.
Preconditions:
tm maps state symbol pairs to symbol movement, state triples
states are represented by strings
symbols are of any hashable type
movement is one of RIGHT, LEFT, STAY
tape is a list of symbols
the blank symbol is represented as None
head
if tape :
tape None
symbol tapehead
state 'start'
step
if debug:
printstep state, tape:head symbol, tapehead:
while step MAXSTEPS and state symbol in tm:
actions tmstate symbol
tapehead actions # write symbol may be the same
head head actions # move left, right or stay
state actions # next state may be the same
step step
if head :
printMoved left past the start of the tape'
head
step MAXSTEPS # force loop to finish
elif head lentape:
tape.appendNone # extend tape when needed
symbol tapehead
if debug:
printstep state, tape:head symbol, tapehead:
output tapehead:
while output and output None:
output.pop
return output
# Transition table
palindrome
# write the transitions here in the form
# state symbol: newsymbol, LEFT or RIGHT or STAY, newstate
palindrometests
# case, TM input tape, debug, output tape
palindrome palindrome, False,
not palindrome', palindrome, False,
# Test cases for even palindromes
even palindrome palindrome, False,
even palindrome palindrome, False,
even palindrome palindrome, False,
even palindrome palindrome, False,
# Test cases for odd palindromes
odd palindrome palindrome, False,
odd palindrome palindrome, False,
odd palindrome palindrome, False,
# Test cases for even nonpalindromes
not palindrome palindrome, False,
not palindrome palindrome, False,
# Test cases for odd nonpalindromes
not palindrome palindrome, False,
not palindrome palindrome, False,
testrunTM palindrometests
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started