Binary Review

We first discussed binary representations today. Binary is great for this class because it will give us a lot of interesting CS relevant examples to play with, so it is worth learning well.

As you recall, instead of 10 digits in each place and powers of 10 in each place, binary numbers have only 0s and 1s as digits and powers of 2. In particular, we have the 1s place, the 2s place, the 4s place, the 8s place, the 16s place, etc.

I've coded up a few applets below so you can practice representing binary numbers. The first two are drills on converting back and forth between binary and base 10, and the last one shows binary addition step by step. Do these until you feel comfortable. If you are totally new to binary, you should have a look at Wiki How's articles on reading binary and adding binary (sections 1 and 2) before you do the drills.

Binary To Base 10 Drills

New Example

Binary
Base 10 Check
Answer

Base 10 To Binary Drills

New Example

Base 10
Binary Check
Answer

Binary Addition Animation

New Example

Binary Clock

Below is an example of a binary clock, which I have in my office. Top row is hours in military time (24 hour scale), middle row is minutes, bottom row is seconds

---

JFLAP Exercises

Next, we got JFLAP installed and we practiced designing and testing DFAs in JFLAP. Click here to review detailed instructions on how to create and test DFAs in JFLAP.

Example 1

As a first example, we created a DFA to accept binary strings with at most three 1s. Below is a solution (Click here to download the JFLAP file)

Example 2

We also designed a DFA that accepts binary strings corresponding to even numbers. We saw that reading in the binary strings from left to right was tricky because we never knew quite where we would end (we'll address this later with something called an NFA), so we decided to read the binary strings from right to left to make it easier; that is, we'll start at the 1s place, then go to the 2s place, then go to the 4s place, etc.

Binary representations are very convenient for spotting even numbers, as the only rule is the 1s place has to have a zero. This is because all other places are even numbers, so we can only make an odd number 2k + 1 by having a one in the 1s place. The machine below implements a right to left even binary detector (Click here to download the JFLAP file)

Example 3

As a challenge, we wanted to see how to design a DFA that would accept binary numbers that, when read from left to right, were evenly divisible by 3 (note that this includes 0), and which would reject all others. We didn't have much time to tackle this in class, but as participation credit for the week, students should submit a JFLAP file on Canvas with an attempt to this problem before class on Monday. It doesn't matter if it's correct, but do spend somewhere between 10 and 20 minutes thinking about it. We'll discuss a solution on Monday, which will help prepare you for problems 1.3 and 2.3 on homework 2.

Here are two hints

• A number which is divisible by 3 has a remainder of 0 when dividing by 3. A number which is not divisible by 3 has a remainder of either 1 or 2.
• When the digits of a binary number are shifted to the left, this multiplies the number by 2. For example, the number 111 is 7, the number 1110 is 14, and the number 11100 is 28.

Below are some tests you can use to test this, along with the result that they should give. Click here to download these tests as a file which you can load into the multiple run tester in JFLAP.

Decimal Number	Input	Result
72	1001000	Accept
12	1100	Accept
5	101	Reject
0	0	Accept
28	11100	Reject
27	11011	Accept
71	1000111	Reject
75	1001011	Accept
85	1010101	Reject
47	101111	Reject