Answered step by step
Verified Expert Solution
Link Copied!

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, i.e. is the same as when read backwards. The input tape consists of zero or more zeros and ones, followed by blanks. The output is 1 if the input is a palindrome, otherwise 0.
You are to write the transition table for the Turing machine. Organise the transitions by state or by the order they're executed.
RIGHT =1
LEFT =-1
STAY =0
MAX_STEPS =100
def run_TM(tm: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 MAX_STEPS.
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 =0
if tape ==[]:
tape =[None]
symbol = tape[head]
state = 'start'
step =0
if debug:
print(step, state, tape[:head], symbol, tape[head+1:])
while step < MAX_STEPS and (state, symbol) in tm:
actions = tm[(state, symbol)]
tape[head]= actions[0] # write symbol (may be the same)
head = head + actions[1] # move left, right or stay
state = actions[2] # next state (may be the same)
step = step +1
if head <0:
print('Moved left past the start of the tape')
head =0
step = MAX_STEPS # force loop to finish
elif head == len(tape):
tape.append(None) # extend tape when needed
symbol = tape[head]
if debug:
print(step, state, tape[:head], symbol, tape[head+1:])
output = tape[head:]
while output !=[] and output[-1]== None:
output.pop()
return output
# Transition table
palindrome ={
# write the transitions here in the form
# (state, symbol): (new_symbol, LEFT or RIGHT or STAY, new_state),
}
palindrome_tests =[
# case, TM, input tape, debug, output tape
('palindrome', palindrome, [1,0,1], False, [1]),
('not palindrome', palindrome, [1,0], False, [0]),
# Test cases for even palindromes
('even palindrome 1', palindrome, [1,0,0,1], False, [1]),
('even palindrome 2', palindrome, [0,1,1,0], False, [1]),
('even palindrome 3', palindrome, [1,1,1,1], False, [1]),
('even palindrome 4', palindrome, [0,0,0,0], False, [1]),
# Test cases for odd palindromes
('odd palindrome 1', palindrome, [0,1,0], False, [1]),
('odd palindrome 2', palindrome, [1,1,0,1,1], False, [1]),
('odd palindrome 3', palindrome, [0,1,1,1,0], False, [1]),
# Test cases for even non-palindromes
('not palindrome 1', palindrome, [1,0,0,0], False, [0]),
('not palindrome 2', palindrome, [1,1,0,0], False, [0]),
# Test cases for odd non-palindromes
('not palindrome 3', palindrome, [0,1,1,0,1], False, [0]),
('not palindrome 4', palindrome, [1,0,1,0,1], False, [0]),
]
test(run_TM, palindrome_tests)

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Internals A Deep Dive Into How Distributed Data Systems Work

Authors: Alex Petrov

1st Edition

1492040347, 978-1492040347

More Books

Students also viewed these Databases questions