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
