Theory of computation

CS440 Week 2 Homework (due Thursday 4/18 by midnight) Team Member 1: _________________________________________ Team Member 2: _________________________________________ Please submit this homework as a PDF. You may use LaTeX (in which case https://madebyevan.com/fsm/ may be useful), or by printing this and hand-writing (using additional pages if necessary). If you work with a partner, please make sure you both have a copy to keep (at least a scan), and email Professor Gordon to set up a time to come do the “independent understanding check” by the deadline (the check can be after the deadline, but get scheduling started). If you start working with a partner, you must continue working with that partner and cannot switch before the next assignment. Activity 1: Consider the problem of adding integers in binary. Create a finite automaton to check that given 3 number x, y, and z, in a special binary format, x+y=z. The format is this: x, y, and z are in binary (two’s complement), but: • • • They are provided least-significant-bit first, most significant last They are provided interleaved: the first 3 letters of the input are the least-significant bits of x, y, and z, respectively. The next 3 letters of the input are the second-least-significant bits of x, y, and z. So when checking that x=0101 + y=0010 is z=0111, the string the automaton will see is 101011101000, and that should be accepted. Note that the backwards order, while weird to think about, means carrying can be implemented (or rather, checked). x and y will always have an explicit 0 for the most significant bit (the last bits of x and y that the automaton will process. If this is violated, reject. Generally people find it much easier to do this as a DFA. General hint: recall that when adding two’s complement numbers, you either do or don’t need to carry to the next most significant bit. Distinctions like this should show up in the state space of your automaton: there should be a bunch of states that deal with adding when there’s a value to carry in, and a bunch of states that deal with adding when there’s nothing to carry, and the automaton should be able to move back and forth between these two “regions” of the automaton. Activity 2: Write a regular expression describing the accepted sequences of bits. Activity 3: Prove by induction on runs that if you have two runs ρ1 (from q to q’, labelled by w) and ρ2 (from q’ to q’’, labelled by w’), then there exists a run ρ from q to q’’ labelled by ww’ (the concatenation, in order, of w and w’). Hint: back-to-front induction on ρ1. Activity 4: Prove that given two NFAs A and B, the construction shown for composing them in sequence accepts the language L(A)L(B) (i.e., the concatenation of any word from L(A) with any word from L(B)). Hint: Use runs. Use what you proved for Activity 3 as a lemma to prove this, don’t do a new induction in this activity. The only extra bit is dealing with the epsilon transition discussed in class.