Comp 200 Homework 7

Due in class Wed 17 Apr 2002

  1. For each of the following languages, construct (1) a DFA (Deterministic Finite Automaton) that recognizes the language, and (2) a regular expression for that language. In all cases, the alphabet is {0,1}.

    1. All strings that contain at least two 1s
    2. All strings that, when viewed as binary numerals, are divisible by four
    3. All strings that contain an even number of 0s

  2. Recall the vending machine finite automaton from class. It didn't give change. Let's say that we now want to write a Turing machine with the same quarter, nickel, and dime alphabet that DOES give change. The input alphabet is {Q,N,D}, and the tape alphabet is {Q,N,D,#} where # denotes a blank. Assume that the Qs, Ns, and Ds that are left on the tape when the Turing machine halts represent the change that will be given. The Snapple costs 25 cents a bottle, don't forget. Diagram the states and transitions for this Turing Machine. (For example: The tape starts with ...###DNNDQ###... on the tape with the read/write head on the first D. The machine should accept with ...###QN###... or ...###NQ###..., etc. on the tape with the read/write head on the first symbol. If there's not 25 cents worth of coins, then the machine should reject, returning the same amount of change that was provided.)

  3. Circuit to compare numbers.

    1. Draw a circuit (using AND, OR, and NOT gates) which has two input wires a and b, and one output wire which is 1 if and only if a = b (that is, the output is one iff ((a is 0 and b is 0), or (a is 1 and b is 1))).

      Remember the approaches to writing circuits: (1) Go to an English description using only the words "and","or","not", and any other circuits we know of; hopefully you can transliterate that description directly into a circuit. (For this problem, I've already tacked on with the suitable English description.) (2) For a simpler circuit, first create a truth table and attempt to form generalizations based on the common elements of "yes" inputs and "no" inputs, trying to come up with the simplest English sentence (or Scheme expression) that does the trick.

    2. Intel has taken the circuit you just created, and mass-produced it as a new gate, EQ. Draw a circuit which takes two four-bit data (a1,a2,a3,a4 and b1,b2,b3,b4) as input, and outputs 1 iff each ai = bi (for i = 1,...,4). You may use AND, OR, NOT, and EQ gates.

  4. Consider an "if" circuit, which has three inputs: a "choice" c, and two other inputs i1, and i2 (each of these being on/off (+0V/+5V)). There is one output, which computes (if c i1 i2). That is, were you to replace 0/1 with false/true, the desired "if" circuit gives the same answer as the scheme function "if". (Of course, scheme's if isn't restricted to *just* having booleans for i1 and i2, as we are in this circuit version.)

    1. Example: what should the output wire be, when the input wires are 0,1,1? When the are 1,0,1?
    2. Give an English sentence, which describes when the output wire should be on (+5V), using "and", "or", "not", "c", "i1", and "i2", but not using the word "if".
    3. Design the circuit, based on the sentence from the previous part. 2

² Note that the parts of this program are the first steps of the design recipe for programs: give example test cases, and write down the english comment for the function. This isn't coincidence; circuits are just another programming language. (back)