## Description

## 1. State of the Art [Online] (10 points)

For each of the following, create an NFA that recognizes exactly the language described.

(a) [5 Points] Binary strings with at least three 1s or an odd number of 0s.

(b) [5 Points] Binary strings with at least three 1s and ending in 010.

Submit and check your answers to this question here:

https://grinch.cs.washington.edu/cse311/fsm

Think carefully about your answer to make sure it is correct before submitting.

You have only 5 chances to submit a correct answer.

## 2. Regular as Clockwork [Online] (10 points)

For each of the following regular expressions, create an NFA that recognizes the same language.

(a) [5 Points] ((0 ∪ 11)∗00)∗

(b) [5 Points] (1 ∪ 01 ∪ 001)∗

(ε ∪ 0 ∪ 00)

Submit and check your answers to this question here:

https://grinch.cs.washington.edu/cse311/fsm

Think carefully about your answer to make sure it is correct before submitting.

You have only 5 chances to submit a correct answer.

1

## 3. State’s Evidence [Online] (20 points)

Use the construction from lecture to convert each of the following NFAs to DFAs.

Label each state of the DFA with the corresponding states of the NFA. For example, if the state corresponds

to {q0, q1, q3}, then label the state “q0, q1, q3”. The empty state can be labeled “empty set” or similar.

(a) [10 Points] The NFA below, which we get by applying the construction described in class1

to the regular

expression (ε ∪ 0)(1 ∪ 00)∗

:

A

B

C D

E F

G H

I J K

ε

ε

0

ε

ε

ε

ε

ε

1

0 0

ε

ε

(b) [10 Points] The NFA below:

C

A

D

E

B

1 ε

1

ε

0

0

0

1 1

ε

## Submit and check your answers to this question here:

https://grinch.cs.washington.edu/cse311/fsm

Think carefully about your answer to make sure it is correct before submitting.

You have only 10 chances to submit a correct answer.

1The only simplification performed was using three states rather than four to represent the sub-expression 00.

2

## 4. Enemy of the State (20 points)

Use the algorithm for minimization that we discussed in class to minimize the each of the following DFAs.

(a) [10 Points] Your solution to Problem 3 (a), which should be a DFA. (Make sure you first submit your

solution to that problem and ensure that it is correct before solving this problem.)

You may want to start by renaming the states of that machine since we originally gave them large

names, corresponding to the subset of NFA states that they represent.

(b) [10 Points]

A

[0]

B

[0]

C

[0]

D

[1]

E

[0]

G

[1]

F

[0]

1

0

1

0

1

0

1

0

1

0

1

0

1

0

### Submit and check your answers to this question here:

https://grinch.cs.washington.edu/cse311/fsm

Think carefully about your answer to make sure it is correct before submitting.

You have only 10 chances to submit a correct answer.

3

## 5. Not Again (25 points)

Let A = {. . . , p, q, r, . . .} be a fixed set of atomic propositions. We then define the set Prop as follows:

Basis Elements For any p ∈ A, Atomic(p) ∈ Prop.

Recursive Step If A, B ∈ Prop, then NOT(A) ∈ Prop and XOR(A, B) ∈ Prop.

The set Prop represents parse trees of propositions that use only the operations of negation (represented by

NOT) and exclusive or (represented by XOR).

Next, we define a function T that takes a parse tree (an element of Prop) as input and returns the

proposition that it represents. Formally, we define

T (Atomic(p)) = p for any p ∈ A

T (NOT(A)) = ¬T (A) for any A ∈ Prop

T (XOR(A, B)) = (T (A)) ⊕ (T (B)) for any A, B ∈ Prop

(Note that this setup is very similar to that of Problem 5 from Section 8. The only differences are that these

parse trees support “⊕” rather than “∧” and “∨”.)

Now, let p ∈ A be any atomic proposition. The function negp

takes a parse tree as input and returns another

parse tree with all nodes representing p replaced by nodes representing ¬p instead:

negp

(Atomic(q)) = NOT(Atomic(q)) if q = p

negp

(Atomic(q)) = Atomic(q) for any q ∈ A with q 6= p

negp

(NOT(A)) = NOT(negp

(A)) for any A ∈ Prop

negp

(XOR(A, B)) = XOR(negp

(A), negp

(B)) for any A, B ∈ Prop

### (a) [15 Points] Prove the following:

for any A ∈ Prop and any p ∈ A, we have either T (negp

(A)) ≡ T (A)

or T (negp

(A)) ≡ ¬T (A).

Note that some facts proven in Problem 4 of Section 2 may be useful here.

(b) [5 Points] Let A ∈ Prop be an expression using only the atomic variables p, q ∈ A. What do we know

about the truth table of T (A) in the case that T (negp

(A)) = T (A)? How about if T (negp

(A)) = ¬T (A)?

(c) [5 Points] We saw in lecture that ¬, ∨, and ∧ together can express any proposition (e.g., by writing it in

sum-of-products form). De Morgan’s Law tells us that ∧ can be written instead with ∨, so any proposition

can be expressed with only ¬ and ∨. Prove that the same is not true of ¬ and ⊕.

Specifically, use the results of the earlier parts to show that p ∧ q cannot be represented by any

expression using only ¬ and ⊕.

4

## 6. Just Irregular Guy (30 points)

Use the method described in lecture to prove that each of the following languages is not regular.

(a) [15 Points] The set of binary strings of the form {0

x1

m0

y

| x, m, y > 1 and x ≡ y (mod m)}.

(b) [15 Points] Unicode strings that are syntactically valid Java Script Object Notation (JSON).

(This simple language does not include arithmetic expressions but is already irregular.)

## 7. Extra Credit: Pratt-Pratt-Pratt (0 points)

Suppose we want to determine whether a string x of length n contains a string y = y1y2 . . . ym with m n.

To do so, we construct the following NFA:

s0 s1 s2

… sm−1 sm

y1 y2 y3 ym−1 ym

0, 1 0, 1

(where the . . . includes states s3, . . . , sm−2). We can see that this NFA matches x iff x contains the string y.

We could check whether this NFA matches x using the parallel exploration approach, but doing so would

take O(mn) time, no better than the obvious brute-force approach for checking if x contains y. Alternatively,

we can convert the NFA to a DFA and then run the DFA on the string x. A priori, the number of states in

the resulting DFA could be as large as 2 m, giving an Ω(2m + n) time algorithm, which is unacceptably slow.

## However, below, you will show that this approach can be made to run in O(m2 + n) time.

(a) Consider any subset of states, S, found while converting the NFA above into a DFA. Prove that, for each

1 ≤ j < m, knowing sj ∈ S functionally determines whether si ∈ S or not for each 1 ≤ i < j.

(b) Explain why this means that the number of subsets produced in the construction is at most 2m.

(c) Explain why the subset construction thus runs in only O(m2

) time (assuming the alphabet size is O(1)).

(d) How many states would this reduce to if we then applied the state minimization algorithm?

(e) Explain why part (c) leads to a bound of O(m2 + n) for the full algorithm (without state minimization).

(f) Briefly explain how this approach can be modified to count (or, better yet, find) all the substrings matching

y in the string x with the same overall time bound.

Note that any string matching algorithm takes Ω(m + n) = Ω(n) time in the worst case since it must read the

entire input. Thus, the above algorithm is optimal whenever m2 = O(n), or equivalently, m = O(

√

n), which

is the case for normal inputs circumstances.

5