a few questions (regarding the sol of the above exam):
1. In partI-Q2, what does the symbol of a triangle mean?
2. In partII-Q3,
a. Why can I infer from that L1 is NP-hard and L2 is in co-NP-hard, that their union is NP-hard and co-NP-hard?
b. What do we know about EXP with regard to NP, co-NP?
c. What do you mean when you say about a claim that it holds always or sometimes?
d. How the explanation (in sol) explains the first part of the claim: L1UL2 in EXP? and if it doesn't, can you please explain this?
3. In partII-Q5, just to make sure, what's L(A)?
4. In partII-Q8, why the original form of the test isn't ture regarding +1 instead of +2? (if the longest word in L is m, the minimal number of states in the appropriate DFA is at most m+1 - for q0 - isn't it?)
Thanks in advance!