ITEC 420 2020fall ibarland

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

Turing Machines
hw06

• Due 2020-Nov-09 (Mon) 10:00 (start of class).
• Reading: §§17.1– 17.3, and §§17.6– 17.7.
• Please put your solutions in order and clearly label each with the problem number.
• Submit a .pdf, containing any pictures and handwritten work. You are welcome to try to keep the file-size small by providing the lowest-resolution images, so long as I can still read all the transitions.

Turing Machine instructions

• Use turingmachine.io to create your Turing Machines.
• Your file should declare blank = '_'.
• Note: that site already uses the convention that the tape-head starts on the first (non-blank) character of the input (or which is blank if the input is empty).
• For a machine that computes a function, have your machine finish so with the read-head back on the first (non-blank) character of the result.
• For a decider, finishing in a state whose named accept (or, starts with the accept if you want multiple accept-states) to indicate acceptance. Finishing in any other state will be interpreted as rejecting the input. (The tape-contents are irrelevent.)
• As always, make sure that you correctly handle the empty-string as input.
• For each TM, submit on D2L a plain-text file named username-hw06-#i-tm.yaml (for example: ibarland-hw06-#3-tm.yaml). That file should be the contents of the text-pane of your machine on turingmachine.io. It should include:
  • Be sure to verify you can use turingmachine.io » Import » Choose Files to upload your file.
    (This is how I'll view your file. Be aware that the file is indentation-sensitive!)
  • Your username and problem# near the top, as well as this hw URL (www.radford.edu/itec420/2020fall-ibarland/Homeworks/hw06.html).
  • The URL https://turingmachine.io/?import-gist=ID (where the ID is numeric-only). Verify that the link works (even if you've logged out of github).
• If able, please save your file by creating a gist at gist.github.com. (Be sure you save the the file as found via turingmachine.io » Share » Copy to Clipboard; it includes your diagram-info in addition to the machine-instruction-file.)
• Feel free to use the duplicate-a-string example from lecture as an example/template.

1. Write a Turing Machine to decide L={x-y=z : x,y,z ∈ 1*}.
   

   To clarify: The input alphabet for this language is Σ={-,=,1}, and (for example) 11-111=1∈ L. (That is, are checking just the syntax of unary-subtraction.)

   note: This definition allows any/all of x,y,z can have zero 1s.

   yaml gotcha: You must include single-quotes around -. (However they are not needed for =.)

2. Write a Turing Machine to decide L = {x-y=z : x,y,z ∈ 1*, and |x| - |y| = |z|}.
   (That is, we verify semantics of unary-subtraction.)

   Note: Start with a copy of your answer to the previous problem. (Be sure to save that one first!)

   tip: If you are decrementing both x and y: Remove a 1 from y before finding a corresponding 1 in x. (That way, in case y has reached zero (ε), you don't need to go back to un-change a decrement to &vx.;)

   Note: My solution used 4 phases; each phase had about 4-5 states.

   Note: My solution removed 1s from the right edge of y and z (but the left edge of x). I think this might help keep a solution slightly simpler?

3. Write a TM to compute function f where f(w) = wy$, w ∈ {a,b}*, y ∈ {_}*, and |y| = 2|w|.

   Note: This is similar to our example of duplicating a string (u to uu) except that the duplicated-bits are all spaces (and then followed by '$').

   Note: We use the fact that this machine exists in passing, in the Ch17b slides, writing a non-deterministic decider for composite numbers.

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

This page licensed CC-BY 4.0 Ian Barland Page last generated

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu