Homework 7: Strings are Strings

1. Strings are Strings [Online] (20 points)
For each of the following, construct regular expressions that match the given set of strings:
(a) [5 Points] The set of all binary strings that end with 0 and have even length, or start with 1 and
have odd length.
(b) [5 Points] Binary strings where the number of 0s is congruent to 2 modulo 3.
(c) [5 Points] The set of all binary strings that contain at least two 1’s and at most two 0’s.
(d) [5 Points] The set of all binary strings that don’t contain 001.
You must submit and check your answers to this question using
https://grinch.cs.washington.edu/cse311/regex.
Each part has a (possibly different) limit on the number of submissions.
Your last submission prior to this threshold will be graded.
2. Constructing Four Grammars [Online] (30 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 were:
S ! E j O
E ! EE j CC
O ! EC
C ! 0 j 1
We would expect you to say “E generates (non-empty) even length binary strings; O generates odd
length binary strings; C generates binary strings of length one.”
(a) [5 Points] The set of all binary strings that are of odd length and have 1 as their middle character.
1(b) [5 Points] f1m0n1m+n : m; n ≥ 0g
(c) [10 Points] All binary strings that contain at least two 0’s and at most two 1’s.
(d) [10 Points] f1m0n1p : m; n; p ≥ 0 and p ≡ m + n (mod 2)g
You must submit and check your answers to this question using
https://grinch.cs.washington.edu/cse311/cfg.
Each part has a (possibly different) limit on the number of submissions. Your last submission prior to
this threshold will be graded. You must also upload your explanation and the grammar to Canvas.
3. Relations warmup (12 points)
Consider the set of all twitter users. In each part of this problem we define a relation R on this set.
Determine whether R is reflexive, symmetric, antisymmetric, and/or transitive:
(a) [4 Points] (a; b) 2 R if there are no common followers of a and b.
(b) [4 Points] (a; b) 2 R if there is a user c who is a follower of both a and b.
(c) [4 Points] (a; b) 2 R if every user who is a follower of a is also a follower of b.
4. Set Up To Relate (18 points)
Let A be a set. Let R and S be transitive relations on A.
(a) [9 Points] Is R [ S necessarily transitive? Prove your answer.
(b) [9 Points] Is R \ S necessarily transitive? Prove your answer.
5. Symmetry and Power (20 points)
Let R be a symmetric relation on a set A. Use induction to show that Rn is symmetric for all integers
n ≥ 1.
26. EXTRA CREDIT: Ambiguity (-NoValue- points)
Consider the following context-free grammar.
hStmti ! hAssigni j hIfTheni j hIfThenElsei j hBeginEndi
hIfTheni ! if condition then hStmti
hIfThenElsei ! if condition then hStmti else hStmti
hBeginEndi ! begin hStmtListi end
hStmtListi ! hStmtListihStmti j 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 different meanings).
(a) [-NoValue- Points] Show an example of a string in the language that has two different parse trees.
(b) [-NoValue- Points] Give a new grammar for the same language that is unambiguous in the sense
that every string has a unique parse tree.
3