Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework 3 – ECS 120, Winter 2023

Auto-graded problems

Each problem below appears as a separate “Assignment” in Gradescope, beginning with “HW3:”.

Turing machines

The next set of problems require you to submit to Gradescope a .tm file for a TM doing the given task. It is suggested to use multitape TMs. These problems are not randomized, so there is no need to submit a req file.

Use the simulator to test the TMs: http://web.cs.ucdavis.edu/~doty/automata/.

TM #0 = #1: Design a TM to decide the language {x ∈ {0, 1} ∗ | #(0, x) = #(1, x)}.

TM assembly: Design a TM to execute programs written in a simplified assembly-like language.

There are just four instructions: L, Mx, My, and A operating on three registers x, y, and z each holding a nonnegative integer.

• L instructions load a certain constant number, represented in binary, into register z. For example, the instruction L00000101 loads the integer 5 (represented by the bits 00000101) into z. Other bit strings can be specified. The number of bits may be arbitrary, but you may assume it is the same for all load instructions in the program. For instance, if the first instruction is L0011001100110011, then all remaining L instructions will be followed by exactly 16 bits.

• Mx and My instructions move the value from z into x or y, respectively. (Actually, it’s more like “copy” since the value in z is not erased, but “move” is the traditional assembly language name for this instruction.)

• A instructions add the values in registers x and y and store the result in register z. If the result overflows, the new most significant 1 is simply omitted; i.e., the result is taken mod 2k , where k is the number of bits specified in the first load instruction. For example, adding 11111111 (255) to 00000001 (1) results in 00000000 (0), and adding 11111010 (250) to 00001001 (9) results in 00000011 (3). (This might sound difficult, but actually the straightforward way to implement addition will automatically achieve this.)

If an instruction needs to read a register (add must read x and y, and move must read z), then you may assume that register has already had a value written to it.

The input will be a ˆ followed by a list of instructions, each followed by a :, such as

^L00000110:Mx:L00000111:My:A:Mx:L00001001:My:A:

The above program does the following

• load the value 6 into z and then move it into x,

• load the value 7 into z and then move it into y,

• add x and y and store the result (13) in z,

• move the value in z (13) into x,

• load the value 9 into z and move it into y,

• add x and y and store the result (22) in z.

Your TM should produce a string output equal to the value of register z (represented as a binary string) after the last instruction executes. So the correct output above is 00010110. Furthermore, your TM should halt in the accept state.

You may assume only input strings matching the above description will be supplied. (Your TM does not have to detect syntax errors in the assembly language program.)

Hint: It helps to use one worktape per register, and to write special marker symbols at the start of each of them to help identify when the tape head is scanning the leftmost tape cell. It is also recommended to use wildcards in the transition rules; for detailed instructions on their use, see http://web.cs.ucdavis.edu/~doty/automata/help.html.

There will be 5 points extra credit for any correct TM with strictly fewer than 30 total transitions, and 5 points additional extra credit for the TM(s) with the smallest number of transitions.

Computational complexity

This problem is randomized and requires submitting a file named req to request a problem, then submitting a file ending in .txt with the solution. See Homework 0 for detailed instructions on randomized problems.

ranking time bounds: (randomized) Rank various time bounds (functions of input size n, e.g., n2, 2n ) in order of their asymptotic growth rates. The functions will be given as LATEX code, e.g.,

(0) log n

(1) 2 log n

(2) 1

(3) 2^n

Rank them by uploading a plain text file with the proper nondecreasing order of asymptotic growth rates. Assume all logarithms are base 2. Some time bounds may have the same asymptotic growth rate, in which case listing them in either relative order would be considered correct. More precisely, a correct ordering f1, f2, . . . satisfies f0 = O(f1), f1 = O(f2), f2 = O(f3), . . .. In the above example, since 1 = o(log n), log n = Θ(2 log n), and log n = o(2n ), there are two correct solutions:

2 0 1 3

and

2 1 0 3

Required written problems

Please complete the written portion of this homework on Gradescope, in the assignment titled “HW3 written”. There, you will find the problem statements for the written portion. Please type solutions directly into Gradescope.

Your written solutions will be checked for completeness but not for correctness. To receive credit, you must make a serious attempt at all problems.

For problems asking for an algorithm of some type, you may write either real code in some language, or pseudocode. However, it is easy to fool yourself with pseudocode; be sure that each “command” can really be implemented with code, and has the claimed running time. If you aren’t sure whether something is “allowed” in pseudocode, then the best way to resolve that question is to implement it in real code.

Optional challenge problems

Please read the syllabus for a discussion of optional challenge problems. Briefly, you don’t have to submit a solution to these, and they aren’t worth any points. But, if you find any interesting, and if you think you have a solution, please email it directly to me: [email protected].

1. A 1-tape TM is a finite automaton with a “linked-list” memory: the tape can be traversed both left and right, and new cells can be added to one end. Show that the following model of computation is as powerful as a TM: a finite automaton with a “first-in, first-out queue” memory. On input x ∈ Σ ∗ , the queue starts with |x| nodes, each containing a symbol of x, and the finite automaton can: 1) read the element at the left end of the queue, 2) delete the leftmost element of the queue, or 3) add a new element to the right end of the queue.

2. Show that P is closed under ∗ .

3. The procedure given in lecture for converting an NFA to a regex takes time exponential in n, the number of states in the NFA. The main reason for this slowness is that the output regex itself is so long that it takes at least that much time to write down.

Show either 1) that this is necessary: some NFA with n states has the property that the smallest equivalent regex has length at least exponential in n, or 2) for every NFA with n states, there is an equivalent regex with length at most polynomial in n.