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!