Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Homework 8: Finite Automata; Fundamentals Review
Due date: Friday December 8th at 10 PM
If you work with others (and you should!), remember to follow the collaboration policy outlined in the syllabus.
In general, you are graded on both the clarity and accuracy of your work. Your solution should be clear enough that someone in the class who had not seen the problem before would understand it.
We sometimes describe approximately how long our explanations are. These are intended to help you understand approximately how much detail we are expecting. You are allowed to have longer explanations, but explanations significantly longer than necessary may receive deductions.
To help with formatting of English proofs, we’ve published a style guide on the website containing some tips. Unless otherwise noted in a problem, all proofs must be English proofs. You should not have numbered steps (e.g., you should not be doing an inference proof.)
Finally, be sure to read the grading guidelines for more information on what we’re looking for.
This is the last homework :D. You can only use up to one late day on this homework (you can submit up to Saturday at 10 PM), but keep in mind that you need time to study for the exam. Unused late days will be converted to concept checks. For every late day you haven’t used, we will convert a concept check to full credit (assuming you would have gotten full credit had you gotten extra time).
We will not be able to return feedback on HW8 until after the final.
1. Contrapositive [10 points]
In this problem, you’ll prove “For all perfect squares x (i.e., x such that √ x is an integer): if 4 does not divide x then √ x is odd.”
(a) Write the contrapositive of the statement to be proven in English (be sure to explicitly mention any quantifiers). [2 points]
(b) Now do the proof; you must use proof by contrapositive for this problem. Be sure to explicitly mention your proof technique! [8 points]
2. Com-pair-isons [7 points]
Let A = {S : S ⊆ N ∧ |S| = 2}. I.e., an element of A is a set containing two natural numbers.
We define the relation on A as follows.
Let X = {x1, x2} with x1 < x2
Let Y = {y1, y2} with y1 < y2
We will say X Y if and only if x1 ≥ y1 and x2 ≥ y2.
In English, we say X Y if and only if the smaller element of Y is at most the smaller element of X and the larger element of Y is at most the larger element of X.
For example:
• {8, 11} {4, 8}
• {4, 16} 6 {7, 9} because 4 < 7
• {2, 32} {2, 6}
• {7, 14} {11, 2} (we compare elements based on their sizes, not what order they are listed in).
(a) Prove that is antisymmetric on A. You may not use proof by contradiction for this problem. Remember to introduce arbitrary variables as arbitrary. [7 points]
Hint: Remember that we had two equivalent definitions of antisymmetry. The definition ∀x∀y([(x, y) ∈ R ∧ (y, x) ∈ R] → x = y) is probably going to give you a cleaner proof than the other definition in this problem.
Hint: Please, when introducing a set, also name its elements. E.g. when you introduce X also let X = {x1, x2} for integers x1, x2, with x1 < x2. Your proof will be much easier to read and write this way.
(b) Convince yourself that is a partial order on A (you just showed antisymmetry; you should convince yourself of reflexivity and transitivity). You do not have to write anything for this part [0 point]
3. Build DFAs (Online) [15 points]
For each of the following languages, construct a DFA that accepts exactly the given set of strings. You should submit (and check!) your answers online at https://grin.cs.washington.edu/
Think carefully before entering your DFA; you have a limited number of guesses. Because these are auto-graded, we will not award partial credit.
(a) Binary strings with at least two 0’s and at least one 1.
(b) Binary strings with at most two 1’s and an even number of 0’s.
(c) Binary strings such that none of their runs of 1s have an odd length > 2.
A “run” of 1s is a string of consecutive 1s with edges at the start of the string, end of the string, or adjacent to a 0. “1” contains exactly one run of 1s (of length 1).
• “111101” contains two runs of 1s (one of length 4, the other of length 1).
• For example, “1100111” is not accepted because the last three characters are an odd-length run of 1s. But “0110001” is accepted because the first run of 1s has length 2, and the second run of 1s has length 1 (even though this is odd, it is fine since the run is not > 2). “00000” is also accepted because it contains no run of 1s.
4. Build NFAs (Online) [15 points]
For each of the following languages, construct an NFA that accepts exactly the given set of strings. You should submit (and check!) your answers online at https://grin.cs.washington.edu/
Think carefully before entering your NFA; you have a limited number of guesses. Because these are auto-graded, we will not award partial credit. (a) The set of binary strings that contain ”11” and do not contain ”00”. [7 points] (b) The set of binary strings that contain ”11” or do not contain ”10”. [8 points]
5. Primal Translations [10 points]
We define a cousin prime as a prime number which is separated from another prime number by a distance of only 4. For example, 3 and 7 are cousin primes. Formally, we say an integer x is a cousin prime if it’s prime and if there exists a prime number y such that x − y = 4 or y − x = 4.
(a) Define COUSIN-PRIME(x) in predicate logic by translating the formal definition above. Let your domain of discourse be integers, and let PRIME(p) be the predicate which is true iff p is prime. You may use standard arithmetic notation (including +, −, =, ≤, etc.) in all parts of this problem [2 points]
(b) The cousin prime conjecture states that there are infinitely many cousin primes (it is not known to the 311 staff if the conjecture is true)1 . We can rephrase the conjecture as follows: For any integer N, no matter how large, there always exists a cousin prime larger than N. Write in predicate logic a proposition which is true if and only if the cousin prime conjecture holds. Your answer should use your predicate from part (a). [2 points]
(c) Negate the translation you wrote in part (b). Show your work, but leave your answers as symbols. You don’t have to name rules as you use them. Your final answer must have negations applied only to single predicates. You do not need to simplify to “take advantage of domain restriction.” [3 points]
(d) Translate your answer from (c) into English. You may NOT use the words finite or infinite or any variation of them. [3 points]
6. Proof By Contradiction [11 points]
In this problem you’ll show
Claim: Subtracting a rational number from an irrational number always gives an irrational number.
(a) Translate the claim above into predicate logic. Let your domain of discourse be all real numbers. Use the predicate R(x) for ”x is rational”. (note that “x is irrational” is ¬ R(x), so you don’t need another predicate; you can use − for subtraction).
(b) Write the negation of the claim above in predicate logic.
(c) Now, write an (English) proof of the claim. You must use proof by contradiction for this problem.
7. Prove a language is not regular [15 points]
This problem uses the technique from Monday’s lecture. You can look ahead at the slides or wait until Monday. Prove that the following language is not regular: The set of all strings over {0, 1, 2} of the form x2y, with x, y ∈ {0, 1} ∗ and y is the reversal of x. The “reversal” of a string, is the string going from right-to-left (instead of left-to-right). For example
- 0112110 is in the language.
- 00001210000 is in the language.
- 0122210 is not in the language (you can only have a single 2).
- 0002000 is in the language.
- 000200 is not in the language.
8. Extra Credit: Going Back to the Well [0 point]
In class, we’ll use proof by contradiction as a method of showing languages are not regular. Another common way to prove languages are not regular is “The Pumping Lemma.”
Formally, the pumping lemma says: If L is a regular language, then there exists an integer p such that for all w ∈ L, if len(w) ≥ p, then there is a way to divide w into substrings x, y, z such that:
- w = xyz (i.e. x, y, z break w into pieces)
- len(xy) ≤ p
- len(y) ≥ 1
- ∀i ∈ N, xyi z ∈ L
The lemma says you can break any string of L into pieces, where the “middle” piece is length at least 1, such that you can “pump” the string w by inserting extra copies of y into the string while still having the new string also be in L
For some intuition: roughly, p corresponds to the number of states in a hypothetical DFA for L. Once a string w has more than p characters, you have to have a cycle when the machine processes w, but then you could go around the cycle as many times as you want (including 0 times) and still end up in the same accepting state at the end. So some y in the string (what’s read when you go around the cycle) could be duplicated any number of times and still be accepted. The difficulty of using the lemma to prove irregularity is we don’t know which part of the string the cycle would be in (we’re doing proof by contradiction – the language is irregular, so there isn’t even a DFA in real life!) so these proofs often have cases based on all the places y could be in the string.
Use the pumping lemma to show {a 311b nc m : n = 311+m} is not regular. The hardest thing about using the pumping lemma is getting the quantifiers right (there are a lot of them...) make sure you’re declaring and using the arbitrary variables as arbitrary, and saying what the existential variables are. Usually this proof is done by contradiction (suppose L is regular and use the pumping lemma’s guarantee to derive a contradiction) or contrapositive (show the conclusion of the pumping lemma does not hold, and apply the contrapositive to get that the language is not regular). You should feel free to look online or in the textbook for an example proof or two to get a sense of how they usually go.
9. Feedback [1 point]
Answer these questions on the separate gradescope box for this question.
Please keep track of how much time you spend on this homework and answer the following questions. This can help us calibrate future assignments and future iterations of the course, and can help you identify which areas are most challenging for you.
- How many hours did you spend working on this assignment (excluding any extra credit questions, if applicable)? Report your estimate to the nearest hour.
- Which problem did you spend the most time on?
- Any other feedback for us?