CSE311-Homework 7 Solved

1.     Up the Ladder to the Proof
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
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.

3.     Grammar School
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 xR (i.e., it is xR 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
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.

5.     All Your Base
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)     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)    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)     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)    ] 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.

6.     Acting Up
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)      (a,b) ∈ R iff a and b were in the same movie.

(b)     (a,b) ∈ R iff a and b were in none of the same movies.

(c)      (a,b) ∈ R iff a and b were in all of the same movies.

(d)     (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]
For each of the following, create a DFA that recognizes exactly the language given.

(a)  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)      Binary strings with at least two 1s.

(d)    Binary strings with at least two 1s or at most two 0s but not both.

(e)     Binary strings not containing the substring 1011.