Overview / Logistics

The purpose of this problem set is to give you practice with DFAs

Part 1: Constructing DFAs 🚧 🏗️ 👷🏽‍♀️

For all of the problems below, you should save your JFLAP file as "DFAx.jff", where x is the problem number, and then upload them to canvas.

Problem 1.1 (3 Points)

Construct a DFA in JFLAP that accepts the language over Σ = {0, 1} of strings with an odd number of 1's or an even number of 0's. Running your DFA on the following test file should give these results (you should come up with your own tests as well to convince yourself it's working)

Input	Result
10001000000	Reject
10001111001	Reject
10001111101	Accept
10010100100	Reject
10101001111	Accept
11001010110	Reject
11010010111	Accept
11100000010	Reject
11111110111	Reject
110000000100	Accept
00000000	Accept

Hint: You may want to use more than one accept state in your DFA.

Problem 1.2 (3 Points)

Construct a DFA in JFLAP that accepts the language over Σ = {a, b} of strings that start with a nonzero and even number of a's, followed by at least one b, followed by zero or an odd number of a's. Running your DFA on the following test file should give these results (you should come up with your own tests as well to convince yourself it's working)

Input	Output
aaaaaa	Reject
aaaab	Accept
aaaabbbbbb	Accept
aaaabbbbbba	Accept
aaaabbbbbbaa	Reject
aaaabbbbbbaaa	Accept
abbb	Reject
bbb	Reject
b	Reject
bb	Reject
ab	Reject
aabab	Reject
babab	Reject
baab	Reject

Problem 1.3 (3 Points)

Construct a DFA in JFLAP that accepts the language over Σ = {0, 1} of all binary digits of natural numbers that are evenly divisible by 5, when read from left to right. Running your DFA on the following test file should give these results (you should come up with your own tests as well to convince yourself it's working)

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

Problem 1.4 (3 Points)

You should review how binary addition works before you start this problem

In this problem, you will create a DFA that recognizes the language of binary strings that have been correctly added together. Since we can only feed a single symbol to a DFA at a time, we will have to setup a slightly more intricate alphabet than we have so far with 8 elements

Each element of the alphabet is a column with three numbers: the top one is a digit in the first binary number, the middle one is the corresponding digit in the second binary number, and the third is the corresponding digit in the result that we're checking. You can assume that your DFA is reading the binary digits from right to left (this is easier than left to right actually, and it matches the way the binary addition app works). For instance, to check the result 1011101₂ + 101100₂ = 10001001₂

you would input the sequence

And your machine should accept. Not every binary addition result will be correct, though. So if you see, for example, a sequence like this

The machine should reject, because that would be like saying 10₂ + 01₂ = 10₂, which is false; the result should be 11₂.

Create a DFA in JFLAP to recognize the language of correctly added binary numbers. You can unroll the inputs in "column major order" so that your language consists of symbols of 3 binary digits back to back. So, for instance, the input

would be inputted to JFLAP as 101000110.

This one is particularly tedious to create test cases for, so click here to download some tests for JFLAP. You should get the following results:

Input	Result
011011011000011011110001	Accept
111100101111010010111001	Reject
101000110111100111100001	Accept
000110111010100010010001	Accept
110001000101011101101000	Accept
101110100010100111100001	Accept
111000111001110110100000	Reject
100110001101111001111001	Reject
100000001110001001111001	Reject
100001011100011011011001	Reject

Below is a video where I talk through the format here

---

Part 2: Formal DFA Descriptions 👔 👠 🎩

The only problem you need to submit a JFLAP file for is 2.1. The other two are pen and paper (or better yet, LaTeX)

Problem 2.1 (3 Points)

Convert the following formal description into a DFA in JFLAP, and submit your JFLAP file

• Q = { q0, q1, q2, q3, q4 }

• Σ = {0, 1}

• δ =	0 1 q0 q0 q1 q1 q2 q1 q2 q0 q3 q3 q4 q1 q4 q4 q4

• q = q0
• F = {q0, q1, q2, q3}

What language does this DFA recognize?

Hint: You may want to consider the DFA that accepts the opposite of what this one does (i.e. everything is the same except F = {q4}). Then you can build a set which is the complement of whatever set is accepted by the opposite DFA

Problem 2.2 (3 Points)

Provide a formal description of the following DFA (Click here to download the corresponding JFLAP file)

That is, define all of the symbols in the 5-tuple (Q, Σ, δ, q, F), as we talked about in class and as is discussed in Sipser 1.1. What language does this DFA recognize?

Problem 2.3 (3 Points)

Given a fixed N > 0, prove by construction that the language of binary strings corresponding to numbers divisible by N is regular. In other words, provide a general specification for (Q, Σ, δ, q, F) for a particular N. Note that problem 1.3 was a specific example of such a regular language with N = 5.

Hint

Feel free to use the mod (%) function when defining the transition function δ

Problem 2.4 (4 Points)

Have a look at the code for describing DFAs and evaluating them on inputs at this link. In this exercise, create a python program div3.py that specifies the DFA for binary strings divisible by 3 using dictionaries and sets. Then, evaluate this DFA on the binary strings from 0 to 99 and print out which strings are divisible by 3. Do not use the mod operation; this should work simply by evaluating your DFA and seeing if each string brings you to an accept state. Feel free to use online-python or any other python IDE you'd like to do this.

Hint

To loop through the binary digits from 0 to 99, use the following code: