TOC 1.1 (pp. 31-44) DFA
- Due Sep 13, 2021 by 11:59pm
- Points 15
- Submitting a file upload
- File Types pdf
Goals
- Intro to DFA
- Gain a high level glimpse of computation
Tasks
1. What are the 5 parts of a DFA? p. 35 (5 sentences)
2. We can make a DFA model for the volume knobs on guitars that have hard "clicks" for each volume level. Assume that turning the knob always locks it into given volume integer 1 <= x <= 10 and our hands provide input strings from (RL)* -- finite sequences of zero or more R's and L's. Do these clicky volume knobs satisfy the definition of computation (pp 40), and are these clicky volume knobs computers? Why? (3-5 sentences)
For 3 and 4
A. Grill (mechanical/physical) thermometer at the dorm cookout
B. Scoreboard or score cards used in Odle
C. Gear shifting (manual/auto) on a bike used for getting around campus
3. Pick an option above that could be modeled with a DFA. Specify how it could be modeled using the 5 parts you described in number 1, and any given constraints necessary.
4. Pick a variant of an option above that cannot be modeled with a DFA, describe why it cannot (peek also at p. 40).
5. This hotel safe happens to have an I/O port -- with the help of a root kit you picked up off a large internet auction website, you were able to dump the last jump table from memory in the safe.
Below is a diagram of the jump table. What is the safe's password?
6. Whoops that was the just the default password. Trying again, this is the actual dump. What is the password, and what does the safe allow in terms of pressing wrong keys before and after the password?
Submission
Please turn in the assignment in Canvas.