Description
1. Up the Ladder to the Proof (20 points)
Consider the following grammar
S → SS | 0S1 | 1S0 | ε
It is not hard to check that every string generated by this grammar has an equal number of 0s and 1s. (This is
easy to prove using structural induction.) In this problem, you will prove that every string with an equal number
of 0s and 1s can be generated by this grammar. Those two facts, together, say that the language defined by
this grammar is exactly the set of binary strings with an equal number of 0s and 1s.
Prove, by strong induction, that every binary string of length n with an equal number of 0s and 1s can be
generated by the grammar above. (If true for all n, then every binary string with an equal number of 0s and 1s
can be generated by the grammar since every string has some length n.)
Notation: The string x is generated by the grammar above iff there is a sequence of substitutions S ⇒
· · · ⇒ x turning the string “S” into x. Feel free to use the “⇒ · · · ⇒” notation in your proof if it helps.
Extended Hint
For this proof, some machinery may be helpful. Let x ∈ {0, 1}
∗ be a string with an equal number of 0s and
1s. Write the string in terms of its individual characters as x = x1x2 · · · xn, where each xi ∈ {0, 1} and n is the
length of x. We then define the function fx(k) to be the number of 1s minus the number of 0s in x1x2 · · · xk
(the length k prefix of x). Observe that fx(0) = 0, since x1x2 · · · xk = ε when k = 0, and that fx(n) = 0,
since x1x2 · · · xn = x has an equal number of 0s and 1s (by assumption).
Hint 1: Prove the Inductive Step in three cases. The first case is ∀j ∈ [k] (fx(j) > 0), the second case is
∀j ∈ [k] (fx(j) < 0), and the third case is when neither of those holds.
Hint 2: You may use without proof the following fact about any function g with integer inputs and outputs
and the property that |g(k) − g(k + 1)| ≤ 1 for all k: if there exists an i such that g(i) < 0 and a j such that
g(j) > 0, then there exists an `, between i and j, such that g(`) = 0. (Note that the function fx, above, has
this property for any string x: it increases by 1 if xk+1 = 1 and decreases by 1 if xk+1 = 0. So this fact tells
us that, if fx is negative at some point and positive at another, then it must be zero somewhere in between.)
2. Extra Credit 1: Zero Hour (0 points)
Prove the fact you were allowed to use in Problem 1: for any function g : N → Z with the property that
|g(k) − g(k + 1)| ≤ 1 for all k ∈ N, if there exists an i such that g(i) < 0 and a j such that g(j) > 0, then
there exists an ` such that g(`) = 0.
1
3. Grammar School (18 points)
For each of the following, construct context-free grammars that generate the given set of strings.
If your grammar has more than one variable, we will ask you to write a sentence describing what sets of
strings you expect each variable in your grammar to generate. For example, if your grammar was:
S → E | O
O → EC
E → EE | CC
C → 0 | 1
You could say “C generates binary strings of length one, E generates (non-empty) even length binary strings,
and O generates odd length binary strings.” It is also fine to use a regular expression, rather than English, to
describe the strings generated by a variable (assuming such a regular expression exists).
(a) [6 Points] Binary strings matching the regular expression “000(1 ∪ 01 ∪ 001)∗
”.
Hint:
You can use the procedure described in lecture to convert the RE to a CFG.
(b) [6 Points] All strings over {0, 1, 2} of the form x2y, with x, y ∈ {0, 1}
∗
and y a subsequence of x
R (i.e.,
it is x
R with some characters possibly removed).
(c) [6 Points] All strings over {0, 1, 2} where the number of 0s is the same as the number of 1s and there is
exactly one 2.
Hint: Try modifying the grammar from problem 1. (You may need to introduce new variables.
4. Extra Credit 2: As If (0 points)
Consider the following context-free grammar.
hStmti → hAssigni | hIfTheni | hIfThenElsei | hBeginEndi
hIfTheni → if condition then hStmti
hIfThenElsei → if condition then hStmti else hStmti
hBeginEndi → begin hStmtListi end
hStmtListi → hStmtListihStmti | hStmti
hAssigni → a := 1
This is a natural-looking grammar for part of a programming language, but unfortunately the grammar is
“ambiguous” in the sense that it can be parsed in different ways (that have distinct meanings).
(a) [0 Points] Show an example of a string in the language that has two different parse trees that are
meaningfully different (i.e., they represent programs that would behave differently when executed).
(b) [0 Points] Give two different grammars for this language that are both unambiguous but produce different
parse trees from each other.
2
5. All Your Base (21 points)
Recall our definition of the set Lists from Homework 6:
Basis Elements: null ∈ Lists.
Recursive Step: for any x ∈ Z, if L ∈ Lists, then Node(x, L) ∈ Lists.
In this problem, we consider using these lists to store arbitrary-size integers. Specifically, we will store the
individual digits of the base-b representation of the number in a list.1
The following function, valueb, takes a list containing the digits of some number, written in base b, and
returns its actual value as an integer:
valueb(null) = 0
valueb(Node(x, L)) = x + b · valueb(L) for any x ∈ Z and L ∈ Lists
(a) [3 Points] Calculate value10(Node(1, Node(9, Node(3, null)))). Show your work.
Next, we consider functions that perform arithmetic on numbers stored in lists. The function addb(L, y) takes
the number whose base-b digits are stored in the list L and an arbitrary integer y and returns a list containing
the base-b digits of their sum. The function multb(L, r) similarly returns a list containing the base-b digits of
the product of the number stored in L and the integer r.
Rather than defining these (familiar) functions, we instead describe properties that they should have:
valueb(addb(L, y)) = valueb(L) + y for any y ∈ Z and L ∈ Lists (Fact A)
valueb(multb(L, r)) = valueb(L) · r for any r ∈ Z and L ∈ Lists (Fact B)
(b) [1 Point] Briefly explain why any correct implementation of addb and multb should satisfy Facts A-B.
Below, we will define a function, convertb→c, that converts a number stored as its base-b digits into the same
number stored as its base-c digits.
(c) [1 Point] Briefly explain why a correct implementation of convertb→c should have the property that
valuec(convertb→c(L)) = valueb(L) for all L ∈ Lists.
Now, we define convertb→c as follows:
convertb→c(null) = null
convertb→c(Node(x, L)) = addc(multc(convertb→c(L), b), x) for any x ∈ Z and L ∈ Lists
(d) [16 Points] Let b, c ≥ 2 be integers. Prove that valuec(convertb→c(L)) = valueb(L) for all L ∈ Lists. You
may assume that add and mult are implemented correctly, so they satisfy Facts A-B.
1Here and below, all bases are integers greater than or equal to 2.
3
6. Acting Up (16 points)
Consider the set of all actors and actresses listed in the Internet Movie Database (IMDB). In each part of this
problem, we define a relation R on this set. For each one, state whether R is or is not reflexive, symmetric,
antisymmetric, and/or transitive. (No proofs.)
(a) [4 Points] (a, b) ∈ R iff a and b were in the same movie.
(b) [4 Points] (a, b) ∈ R iff a and b were in none of the same movies.
(c) [4 Points] (a, b) ∈ R iff a and b were in all of the same movies.
(d) [4 Points] (a, b) ∈ R iff the total (sum) of the box office revenues from every movie a was in was greater
than the total box office revenues from every movie b was in.
7. Machine Shop [Online] (25 points)
For each of the following, create a DFA that recognizes exactly the language given.
(a) [5 Points] Binary strings such that none of the substrings of adjacent 1s (i.e. “11 · · · 1”) have odd length.2
(b) [5 Points] Binary strings that have at least one 1 and an even number of 0s.
(c) [5 Points] Binary strings with at least two 1s.
(d) [5 Points] Binary strings with at least two 1s or at most two 0s but not both.
(e) [5 Points] Binary strings not containing the substring 1011.
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.
2Here, I mean only substrings containing all the adjacent 1s. For example, “011110” is included because the substring of adjacent
1s has length 4. Technically, it also has “111” as a substring, but that substring does not contain all (four) adjacent 1s.
4
