CSE 105 Summer Session 1 2024

Homework 1

Due date: Sunday July 7 at 11:59pm

Instructions

One member of the group should upload your group submission to Gradescope. During the submission process, they will be prompted to add the names of the rest of the group members. All group members’ names and PIDs should be on each page of the submission.

Your homework must be typed. We recommend that you submit early drafts to Gradescope so that in case of any technical difficulties, at least some of your work is present.  You may update your submission as many times as you’d like up to the deadline.

Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning.  Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported.  Your goal should be to convince the reader that your results and methods are sound.

Reading Sipser Chapter 0, 1

Key Concepts Sets, integers, sequences, functions, relations, predicates, graphs,  trees, strings, boolean logic, proof by construction, proof by contradiction, proof by induction. DFAs, regular expressions.

Question 1. (15 points) Let A = {aa, bb, ab, ε}, B  = {a, b}, C = {ab,abab, ababab}.  For each set, write out each of its elements.

a. (A ∪ B ∪ C)

b. (A ∩ C) × (B ∪ C)

c. A O C (set concatenation)

d. P(C) (the power set of C)

e. A × C

f. C*  (this is an infinite set so you only have to write the first 6 elements in standard string order.)

g. A*  (this is an infinite set so you only have to write the first 6 elements in standard string order.)

Question 2. (20 points) CSE 105 is a fairly proof heavy class. The goal of this problem is to help refresh your memory on diferent proof techniques: proof by induction, closure proofs and set equality proofs.

For each part of this question, complete the proofs by filling in the blanks.

Note: there may be alternate correct proofs to each of these claims. The point of this question is to practice  certain proof strategies.

a. Definition: Consider the recursively defined set S defined recursively as follows:

(1) a ∈ S

(2) For any string x ∈ S, then x O x ∈ S.

Claim: For each n ≥ 0, there exists a string w in S such that |w| = 2n. Prove this claim.

b. Prove that if A ≤ R is closed under multiplication and B ≤ R is closed under multiplication then

A ∩ B is closed under multiplication and A ∪ B is not necessarily closed under multiplication.

[Note: “A is closed under multiplication” means that for all x and y in A, xy is also in A.] A ∩ B is closed under multiplication.

Let x,y be elements of A ∩ B. (Show that xy ∈ A ∩ B.)

A ∪ B not necessarily closed under multiplication.

Find a counterexample of a pair of subsets of the real numbers, A  and B  each closed under multiplication but their union is not closed under multiplication.

c. Consider the sets:

A = {w ∈ {0, 1}* |  10 is a substring of w}

B = {0n 1m |n, m ≥ 0}

Fill in the blanks to show that A = B.

In order to prove set equality, we must prove A ≤ B and B ≤ A.

– A ≤ B.

Suppose that w  ∈                                .  Then w  does not have any 2-element sub- strings of the form 10.  This means that there can never be a

before a                            in w.  So all 0’s must come before all 1’s and so w has the form                            and w ∈ B.

– B ≤ A.

Suppose that w  ∈                                .   Then w  must have the form 0n 1m .  The only possible 2-element substrings of w are:                         I, l                                                                             ,

.  Therefore                            is not a substring of w  and so

w ∈ A.

Question 3 (15 points) Draw the DFA that is described by the formal definition: ({q0, q1, q2, q3}, {0, 1}, δ, q0, {q2})

with δ given by the table

1. Draw the state diagram of your DFA in JFLAP or flap.js, export the image as a png or jpg file, and include it as part of your submission. (no justification necessary.)

2. Describe the language recognized by this DFA. (you can describe it in words or by using a regular expression (or both.))

3. Is it possible to construct a DFA that recognizes this language with fewer states? If not, explain why not. If so, then draw it using JFLAP or flap.js.

Question 4

(10 points) Consider the DFA, M, whose state diagram is given by:

1. Describe the language L(M).

2. If w ∈ L(M), will the string obtained by flipping bits in w  (changing 0 to 1 and 1 to 0) also be in L(M)? Explain your answer.

3. If w ∈ L(M), will the string wR  (the reverse of w) also be in L(M)? Explain your answer

4. Describe in your own words the “role” of each of the states.

5. Write a regular expression that describes L(M). (please explain your reasoning.)

Question 5

(12 points )

For the DFA design problems, draw the state diagram in JFLAP or or flapjs.web.app, save the drawing as a png or jpg file and include it as part of your submission.

(no justification necessary.)

1. Design a DFA that recognizes the language:  {w ∈ {0; 1}*  |   the sum of all bits of w is even.} (e.g., the sum of the bits of 011100 is 3 since there are three ones. the sum of the bits of 0101011 is 4 since there are four ones.)

(Note: this set includes the empty string.)

2. Design a DFA that recognizes the language: {w ∈ {0; 1}*   |  the alternating sum of bits of w is a multiple of 4.}

(e.g. the alternating sum of 111101 is 1-1+1-1+0-1= -1. The alternating sum of 00101 is 0-0+1-0+1 = 2.)

(Note: this set includes the empty string.)

3. Design a DFA that recognizes the language:

{w ∈ {0; 1}*    |   w has at least length 4 and its third and fourth bits are both 0.}