This week we talked about decidability (4.1) and the basics of finite state machines (5.1-5.4). We built several machines, including a binary adder (slightly simplified), as described on page 25 of the book. Next week we will finish chapter 5 (5/4-5/8).
Homework is due at the beginning of next class for in-class students and by midnight for OL students.
Submission: you can submit the homework by hardcopy in class or by sending it to me as an email.
1. [Reading Assignment] Read Sections 5.1-5.3 of the book.
2. [Finite State Automaton, 5pt] Install jflap (or use the applet version). Download the mystery finite automaton. What language does it accept?
3. [Deterministic finite automata, 16pt] Build deterministic finite automata for the following languages:
Create a test-suite of strings and run your automaton on those strings, and submit a screenshot of your automaton with those test-runs (use the Input/Multiple run feature).
4. [Nondeterministic finite automata, 10pt] Build nondeterministic finite automata for the following languages:
5. [Regular Languages, 5pt] Show that the language {w in {a,b}^{*}: more than half the letters in w are a} is not regular. Hint: use a similar argument as the one we used for the missing letter language. Assume there is a finite automaton M with n states; show that there are two strings b^{k} and b^{m}, k<m, that leave M in the same state (starting with s, the starting state). Why is that sufficient?
6. [Extra Credit] Prove or disprove: any sequence of three decimal digits contains a non-empty subsequence which represents a number divisible by 3. E.g. 842 contains the subsequence 42 which is divisible by 3.