LMU ☀️ CMSI 3801
THEORIES OF COMPUTER AND HUMAN LANGUAGES
Quiz 3
  1. What is the difference between a transducer and a recognizer (10 words or less)?
  2. What is the difference between a recognizer and a decider (10 words or less)?
  3. What is the difference between the Harvard and von Neumann architectures (10 words or less)?
  4. What family of languages are recognized by always-halting Turing machines?
    • Type-1
    • Type-2
    • Recursive
    • Type-3
    • Finite
  5. Complete the standard 5-column table for the following TM. In your table write $S$ for the scanning state, $F$ for the flipping state, and $I$ for the incremented state:

    tmIncrementStandard.png

    In StateLooking AtWriteMoveNext State
     
     
     
     
     
     
  6. Which of the following have strictly less computing power than Turing Machines? Choose all that apply.
    • Turing Machine with the tape infinite in only one direction
    • Finite Automata
    • Pushdown Automata
    • Queue Automata
    • Rewrite Machines
    • Deterministic Turing Machines (only one choice can be made for each state+current_symbol pair)
  7. After running this 3AC program, what will be in r0? 
    copy r0, 1
copy r1, 5
mul r0, r0, r1
jzdec r1, -1
  8. Write, in Python, or any other mainstream programming language, the statement corresponding to the stack machine code
    load y
load 2
load z
add
mul
store x