CMSI 3801: Midterm

(8 pts) Give a grammar for the language over alphabet $\{a, b\}$ consisting of all strings with at least five $a$'s.

(7 pts) Match the descriptors to the language families below by writing the number of the descriptor next to the corresponding family.

R        _______     1. Stack Memory
RE       _______     2. No memory needed
Type-1   _______     3. Can be described finitely
CF       _______     4. # strings in language not infinite
REG      _______     5. Recognizers always halt
FIN      _______     6. TM single tape bounded on both ends
FD       _______     7. Unrestricted TM

(8 pts) Give the state diagram of a transducer TM over alphabet $\{A \ldots Z\}$ whose input is a single string and whose output is (regardless of input) the string $SLAY$.
(8 pts) Which of the following transducing Turing Machines implements the function “compute the length of the input and write the answer as a unary number”?
- ```
S,0,1,R,S
S,1,#,R,H
```
- ```
S,0,1,R,S
S,1,1,R,S
```
- ```
S,0,0,R,S
S,1,1,R,S
S,#,#,L,F
F,0,0,1,L
F,1,1,0,L
F,#,#,R,H
```
- ```
S,0,#,R,S
S,1,1,R,H
```
(8 pts) What is the language decided by this TM? (Give your answer as precise as you can. Use real mathematical notation.)
(9 pts) Complete the table for the deterministic TM whose state diagram is:

0 1 2

A

B

C
(5 pts) After running this 3AC program, what will be in r0? (Here decjnz means "decrement the register and then if it is not zero, jump")
```
copy r0, 1
copy r1, 5
mul r0, r0, r1
decjnz r1, -1
```
(5 pts) Suppose we added the instruction DUP to our stack machine, which pushes to the stack whatever is currently on top of the stack. What then, would be the meaning of load x; dup; mul; load y; dup; mul; add; sqrt?
- Dot product
- Hypotenuse
- $\sqrt{2x + 2y}$
- Sum of squares
- An error
(4 pts) What is traditionally the first language to be shown unrecognizable in most presentations of computability theory?
(4 pts) What did Phil Wadler compare to busses in the video assigned in this course?
(4 pts) In eight words or less, what is the Church-Turing thesis?
(6 pts) When Turing was at Cambridge, he was trying to prove _______ wrong about the ________?
```
Who  _______________________________
What _______________________________
```
(5 pts) Of which of the following sets is the function $\lambda n. 7n \log n + 3n^4$ a member?
- $O(1)$
- $O(n \log n)$
- $O(n^4)$
- $O(n^5)$
- $O(2^n)$
- $\Omega(1)$
- $\Omega(n \log n)$
- $\Omega(n^4)$
- $\Omega(n^5)$
- $\Omega(2^n)$
- $\Theta(1)$
- $\Theta(n \log n)$
- $\Theta(n^4)$
- $\Theta(n^5)$
- $\Theta(2^n)$
(8 pts) Draw a nested circles diagram for the six complexity classes log time, polynomial time, exponential time, log space, polynomial space, and exponential space. In your diagram, you must use the traditional names of the classes.
(6 pts) In class we saw the size, depth, and fan-in of a 4-bit adder. What would be the size, depth, and fan-in of an n-bit adder?.
```
Size    _________
Depth   _________
Fan-in  _________
```
(5 pts) At what point does the function $2^n$ overtake $1000000\log{n}$?