3. (50 points) Define H-{(M, k? | M is an NFA, k is an integer, and there is no NFA with at most k states that accepts the same language as H}. Show that SAT is mapping-reducible to H in the following manner (a) (40 points) Let ?-C1 ? ? Cm be a 3CNF formula with some n variables and some m clauses. We can view each 0/1-sequence having length n as a truth- assignment to the variables of ?, where for each i, l-i-n, the i-th bit of the sequence represents the value given to the i-th variable of ? i. (10 points) For each i, 1-i ? m, let Li-{x | x is a 0/1 sequence having length n that represents a truth-assignment that fails to satisfy Ci}. Show that for each i, 1-i ? m, there exists an NFA with n + 1 states for Li. ii. (10 points) Show that there is a DFA with n+ 2 states for Lo-[x|x is a 0/1 sequence whose length is not equal to n iii. (5 points) Define L to be the union of Lo, L?,... , Lm. Using the above two results, show that there is an NFA with at most (m+1)(n+1) +1 states for L. iv. (10 points) Show that ? is not satisfiable if and only if L = {0, 1 v. (5 points) Show that there is a one-state NFA (actually DFA) for {0, 1j*. (b) (10 points) Using the above observations, show that SAT is polynomial-time map- ping reducible to H 3. (50 points) Define H-{(M, k? | M is an NFA, k is an integer, and there is no NFA with at most k states that accepts the same language as H}. Show that SAT is mapping-reducible to H in the following manner (a) (40 points) Let ?-C1 ? ? Cm be a 3CNF formula with some n variables and some m clauses. We can view each 0/1-sequence having length n as a truth- assignment to the variables of ?, where for each i, l-i-n, the i-th bit of the sequence represents the value given to the i-th variable of ? i. (10 points) For each i, 1-i ? m, let Li-{x | x is a 0/1 sequence having length n that represents a truth-assignment that fails to satisfy Ci}. Show that for each i, 1-i ? m, there exists an NFA with n + 1 states for Li. ii. (10 points) Show that there is a DFA with n+ 2 states for Lo-[x|x is a 0/1 sequence whose length is not equal to n iii. (5 points) Define L to be the union of Lo, L?,... , Lm. Using the above two results, show that there is an NFA with at most (m+1)(n+1) +1 states for L. iv. (10 points) Show that ? is not satisfiable if and only if L = {0, 1 v. (5 points) Show that there is a one-state NFA (actually DFA) for {0, 1j*. (b) (10 points) Using the above observations, show that SAT is polynomial-time map- ping reducible to H
