HW13 Part 1:
• Answer the following questions regarding HITTING_SET and VERTEX_COVER as defined below.
• Use the reductions described in the book to perform the following conversions.
a. Reduction: SAT (in cnf) to 3-SAT. Input: Φ=(𝑎∨𝑏)∧(𝑎∨𝑏¯∨𝑐∨𝑑)
b. Reduction: 3-SAT to CLIQUE. Input: Φ=(𝑎∨𝑏∨𝑏)∧(𝑎¯∨𝑏¯∨𝑏¯)
c. Reduction 3-SAT to SUBSET-SUM. Input: Φ=(𝑎∨𝑏∨𝑏)∧(𝑎¯∨𝑏¯∨𝑏¯)
Part 2: Portfolio Problems:
Write up each of these problems formally using LaTeX (overleaf.com). A formal proof is very specific about definitions and notation. It uses complete sentences for explanation where possible. Each proof should be contained within its own LaTeX file.
Each proof contains KEY components which are labeled in the requirements. Getting the key component correct is not worth much as it does not contribute much to the proof. However, getting it incorrect completely ruins the proof and will result in a significant deduction.
共5大题：
第一题：DFA/NFA Construction Assignment 三个都要做
• Prove the class of regular languages are closed under the intersection operator. Use the technique similar to the proof for union in either Theorem 1.25 (p45) or Theorem 1.45 (p 59).
Theorem 1.25 The class of regular languages is closed under the union operation. In other words, if A1 and A2 are regular languages, so is A1 ∪ A2.
Theorem 1.45 The class of regular languages is closed under the union operation.
• Problem 1.31. Regular languages are closed under the reverse operator.
• Problem 1.36. Let Bn={ak | k is a multiple of n}. Show that for each 𝑛>=1, the language Bn is regular.
Requirements:
• Introduction includes the statement you are proving and definitions.
• The argument is laid out in a short paragraph.
• All five components of a DFA or NFA are included. (KEY).
• The transition function 𝛿δ is described formally with mathematics or logic and includes a brief verbal description.
• Includes a conclusion.
第二题：Top of Form
Bottom of Form
第二题：Pumping Lemma Proof Assignment三个都要做
• Problem 1.47 Let Σ = {1,#} and let
Y ={w|w=x1#x2#···#xk for k≥0, each xi ∈1∗, and xi != xj for i !=j}. Prove that Y is not regular.
• Problem 1.49 有两小题
a. Let B={1ky|y∈{0,1}∗ and y contains at least k 1s, for k≥1 }.Show that B is a regular language.
b. Let C={1ky|y∈{0,1}∗ and y contains at most k 1s,for k ≥1}. Show that C isn’t a regular language.
• Problem 2.31. Let B be the language of all palindromes over {0,1} containing equal numbers of 0s and 1s. Show that B is not context free.
Requirements:
• The argument is laid out correctly as a proof by contradiction.
• The proof is written clearly in complete sentences. (see solution to 1.29a,b on page 97 for a sample).
• The string s is written in terms of p, and p is not replaced by a number later in the proof. (KEY)
• The string s is in the language. (KEY)
• The possibilities for how the string is split cover all possible cases.
• Includes a conclusion.
第三题：Top of Form
Top of Form
Bottom of Form
第三题：Decidable Languages Assignment： 三道题都要做Top of Form
• Problem 4.3. Let ALLDFA = { | A is a DFA and L(A) = Σ∗}. Show that ALLDFA is decidable.
• Problem 4.13. Let A = {
• Problem 4.21. Let S = {
Requirements:
• Include an introductory and concluding sentence.
• The solution includes a Turing decider.
• The input is specified correctly (format and type) e.g. “On input where A is a DFA.” (KEY)
• If you rely on a decider for a different language you specify what that language is.
• All accept and reject statements are explicitly included in the decider.
第四题：Top of Form
Bottom of Form
Undecidable Languages Assignment选择一个做
Do ONE of the following problems.
• Problem 5.1. Show 𝐸𝑄𝐶𝐹𝐺 is undecidable. Use a reduction along with Theorem 5.13 which states that 𝐴𝐿𝐿𝐶𝐹𝐺 is undecidable.
• Problem 5.9. Let T={(M) | M is a TM that accepts wR whenever it accepts w}. Show T is undecidable using Rice’s Theorem.
• Problem 5.30 c. 𝐴𝐿𝐿𝑇𝑀 = {(M) | M is a TM and L(M) = Σ*}. Show that 𝐴𝐿𝐿𝑇𝑀 is undecidable using Rice’s Theorem.
Note: Rice’s Theorem is stated in problem 5.28 (p. 241) and an example solution that uses it is 5.30a (p 244).
Requirements:
• Includes an introduction and conclusion.
• The argument is described logically in a paragraph.
• (if you select problem 1) The reduction is done correctly. (KEY)
• (if you select 2 or 3) Both components of Rice’s Theorem are included. (KEY)
第五题：Top of Form
Top of Form
Bottom of Form
NP Completeness Assignment 两道题都要做
• Problem 7.21 b. Let LPATH = {<𝐺,𝑎,𝑏,𝑘>∣ undirected graph G contains a simple path of length at least k from a to b. }. Show that LPATH is NP-Complete.
• Problem 7.22. Let DOUBLE-SAT = {<Φ>∣Φhas at least two satisfying assignments }. Show that DOUBLE-SAT is NP-Complete.
Requirements:
• Includes an introduction and conclusion.
• The language is shown to be in NP by either a non-deterministic TM or a verifier.
• Includes a description of the runtime for the TM or verifier.
• Clearly state the language to be used in the reduction. (KEY)
• The reduction is performed correctly.
• Briefly describe the correctness of the reduction e.g. 𝑤∈𝐿1 iff 𝑓(𝑤)∈𝐿2.
• The conversion used in the reduction is described.
• The runtime of the conversion is described.