## 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