LMU ☀️ CMSI 3801
THEORIES OF COMPUTER AND HUMAN LANGUAGES
Midterm Answers
  1. (8 pts) Give a grammar for the language over alphabet $\{a, b\}$ consisting of all strings with at least five $a$'s.
    $\begin{array}{l} s \longrightarrow x \;\texttt{"a"}\; x \;\texttt{"a"}\; x \;\texttt{"a"}\; x \;\texttt{"a"}\; x \;\texttt{"a"}\; x \\ x \longrightarrow (\texttt{"a"} \mid \texttt{"b"})^* \end{array}$
  2. (7 pts) Match the descriptors to the language families below by writing the number of the descriptor next to the corresponding family. 
    R         5      1. Stack Memory
RE        7      2. No memory needed
Type-1    6      3. Can be described finitely
CF        1      4. # strings in language not infinite
REG       2      5. Recognizers always halt
FIN       4      6. TM single tape bounded on both ends
FD        3      7. Unrestricted TM
  3. (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$.
    σ#R #SR #LR #AR #YR
  4. (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
  5. (8 pts) What is the language decided by this TM? (Give your answer as precise as you can. Use real mathematical notation.)

    tmFirstLast.png

    $\{ w \in \{a,b\}^* \mid w \text{ starts and ends with the same symbol} \}$
  6. (9 pts) Complete the table for the deterministic TM whose state diagram is:

    bb33.png

     012
    A0RB2LA1RA
    B1LA2RB1RC
    C—1LB1LC
  7. (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
    120
  8. (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
  9. (4 pts) What is traditionally the first language to be shown unrecognizable in most presentations of computability theory?
    $\{\langle M\rangle \mid \langle M\rangle\ \not\in L(M)\}$
  10. (4 pts) What did Phil Wadler compare to busses in the video assigned in this course?
    Definitions of algorithm
  11. (4 pts) In eight words or less, what is the Church-Turing thesis?
    Effectively calculable = Turing computable
  12. (6 pts) When Turing was at Cambridge, he was trying to prove _______ wrong about the ________? 
    Who  David Hilbert
What Entscheidungsproblem
  13. (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)$
  14. (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.
    EXPSPACE
    EXPTIME
    PSPACE
    P
    L
    DLOGTIME
  15. (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    2 + 5(n-1)   (also 5n-3)
Depth   1 + 2(n-1)   (also 2n-1)
Fan-in           3
  16. (5 pts) At what point does the function $2^n$ overtake $1000000\log{n}$?
    23