(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 ? ??? 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 Cij. Show that for each i, 1 ??? 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) 111. (5 points) Define L to be the union of Lo, L1, , Lm-sing the above two results, show that there is an NFA with at most (m+1) (n +1) +1 states for 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,1}*. (b) (10 points) Using the above observations, show that SAT is polynomial-time map- ping reducible to H (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 ? ??? 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 Cij. Show that for each i, 1 ??? 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) 111. (5 points) Define L to be the union of Lo, L1, , Lm-sing the above two results, show that there is an NFA with at most (m+1) (n +1) +1 states for 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,1}*. (b) (10 points) Using the above observations, show that SAT is polynomial-time map- ping reducible to H
