Homework 4
Last updated: Sun, 9 Oct 2022 19:58:12 -0400
Out: Mon Oct 10, 00:00 EST Due: Sun Oct 16, 23:59 EST
This assignment will let you practice writing inductive proofs.
Homework Problems
Induction Practice (6 points)
Induction Practice, with Regular Expressions (10 points)
Proving That a Language is Not a Regular Language (8 points)
README (1 point)
Total: 25 points
Submitting
Submit your solution to this assignment in Gradescope hw4. Please assign each page to the correct problem and make sure your solutions are legible.
A submission must also include a README containing the required information.
1 Induction Practice
Prove that the following statement is true:
\sum_{i=1}^n i^2 =\frac{n(n+1)(2n+1)}{6}
Use induction on one of the natural numbers in the equation.
which value the induction is "on",
base case(s),
and inductive case(s) (where each includes an inductive hypothesis)
In addition, the proof of each case should be clearly explained with a table of statements and accompanying justifications, as described in class.
2 Induction Practice, with Regular Expressions
Prove the theorem from the Caesar Cipher - Closed? problem in
Homework 3—
As a reminder: \mathrm{map}_{lang}(L) = \left\{\mathrm{map}_{str}(w)\mid w\in L\right\}
where \mathrm{map}_{str} is defined using the \mathrm{map}:\Sigma_1\rightarrow\Sigma_2 function (which maps single characters in alphabet \Sigma_1 to single characters in another alphabet \Sigma_2).
This time, however, your answer must be a proof by induction on regular expressions.
3 Proving That a Language is Not a Regular Language
Show that the following language is not a regular language:
L_3 = \left\{x\texttt{==}y\mid\textrm{where }x\textrm{ and }y\textrm{ are equal binary numbers }\right\}
Assume the alphabet is \Sigma = \left\{0,1,\texttt{=}\right\}.
Use the Pumping Lemma and proof by contradiction. Make sure your proof has all the correct components.
Interesting sidenote: This problem is feels similar to the "Real" Computation with DFAs problem from Homework 1. But there, the language was regular. Here, by rearranging the characters making up the strings in the language, we now have a non-regular language that cannot be recognized by DFAs or NFAs!