A printable PDF is also available.
Note 1: This page (and other assignments and materials) use MathML for formatting mathematics. This uses special fonts for mathematics, which usually works but seems to be missing on some computers. The best “check” for this is to look at question 2d below – the final “x” inside the set notation should have a superscript that is a calligraphic R. If you see that, great! If you don’t see it (e.g., just see a box) then you should investigate how to install MathML fonts!
Note 2: Since standard word processors are pretty horrible at writing mathematics, don’t expect a cut-and-paste from this page into a word processor to be correct. If you use LaTeX (recommended!) you can download the LaTeX source for this assignment.
One of the constructions in this class will take a set of states \(Q\) for one machine and create a new machine which uses a set of states \(R\) which is the set of all subsets of \(Q\) (you don’t need to know what a “machine” or “state” really is in this – it’s all about the sets).
What is the mathematical terminology? In other words, \(R\) is the ___________________ of \(Q\).
If \(Q=\{a,b,c\}\), what is \(R\)?
Prove that for any set \(Q\), the size of \(R\) satisfies \(|R|=2^{|Q|}\).
Describe each of the following sets in high-level plain English (no formulas!). For example, the set \(\{x\,|\,x=2k+1\) for \(k\geq 1\}\) is “The set of odd integers greater than or equal to 3.” Do not simply restate things as written here (in other words, do not say “The set of integers \(x\) for which \(x=2k+1\) and \(k\geq 1\)”).
The sets below are all sets of binary strings (note that \(\{0,1\}^*\) denotes the set of all binary strings), and in addition to the notation in the book (pages 13–14) we define \(c_0(x)\) to be the number of \(0\)’s in string \(x\), and \(c_1(x)\) to be the number of \(1\)’s in \(x\). For example, if \(x=\texttt{011010001}\) then \(c_0(x)=5\) and \(c_1(x)=4\).
\(\{x\,|\,x\in\{0,1\}^*\) and \(|x|=2k\) for some integer \(k\}\)
\(\{x\,|\,x\in\{0,1\}^*\) and \(c_0(x)=c_1(x)\}\)
\(\{x\,|\,x\in\{0,1\}^*\) and \(c_1(x)=2k+1\) for some integer \(k\}\)
\(\{x\,|\,x\in\{0,1\}^*\) and \(x=x^{\mathcal{R}}\}\)
We define a function \(f\) to update the position of a robot on a 3-position number-line, with valid positions \(-1\), \(0\), and \(+1\), and an “out of bounds” position “out”. The set of positions is denoted \(P=\{\text{out}, -1, 0, +1\}\). The valid set of moves is \(M=\{\text{Left}, \text{Right}\}\). Once out of bounds, the robot cannot come back to a valid position. The position update function \(f: P\times M\rightarrow P\) is given in the following table:
| Left | Right | |
| out | out | out |
| -1 | out | 0 |
| 0 | -1 | +1 |
| +1 | 0 | out |
For example, \(f(0,\text{Right})=+1\) and \(f(-1,\text{Left})=\text{out}\).
Explain in your own words what the notation “\(f:P\times M\rightarrow P\)” means.
What is \(f(f(f(f(f(0,\text{Left}),\text{Right}),\text{Right}),\text{Left}),\text{Right})\)? Show your work!
What is \(f(f(f(f(f(0,\text{Left}),\text{Right}),\text{Right}),\text{Right}),\text{Left})\)? Show your work!
Prove by contradiction: Any undirected graph with \(n\geq 2\) vertices must have two vertices with the same degree.
Use induction to prove that for all \(n\geq 1\), \[ \sum_{x=0}^{n-1} x(x-1) = \frac{n(n-1)(n-2)}{3}.\]
Let \(G\) be a directed graph with \(n\) vertices, and let \(v\) and \(w\) be any two nodes in the graph. Prove that if there is a path from node \(v\) to node \(w\) of length \(n\), then there is another path from \(v\) to \(w\) with length greater than \(2n\). (Hint: Think about what is appropriate in the following blank, and how that is important to this property: “Any path with \(n\) edges in an \(n\)-vertex graph must contain a _________________.” Note that this is just to get you thinking. Any property you fill in that blank with needs to be proved as part of the overall proof – you can’t just state it, even if you think it’s obvious.)