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.

Theory of computation

We offer the best custom writing paper services. We have answered this question before and we can also do it for you.

GET STARTED TODAY AND GET A 20% DISCOUNT coupon code DISC20

Why Choose Us

  • 100% non-plagiarized Papers
  • 24/7 /365 Service Available
  • Affordable Prices
  • Any Paper, Urgency, and Subject
  • Will complete your papers in 6 hours
  • On-time Delivery
  • Money-back and Privacy guarantees
  • Unlimited Amendments upon request
  • Satisfaction guarantee

How it Works

  • Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
  • Fill in your paper’s requirements in the "PAPER DETAILS" section.
  • Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
  • Click “CREATE ACCOUNT & SIGN IN” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.
  • From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.