1. Given R, a regular language, and E, a recursive (turing-decidable, right?) language, is $\{w|\exists v\in E : wv\in R\}$ regular?

The answers say it is, but how can that be? We know prefix(R) is regular, but this isn't all the prefixes, it's supposed to screen which prefixes are allowed and which are not by something not necessarily regular.

2. Is the following problem in NPC? Input: graph and a natural number k. Question: is there a simple path in the graph that is k edges long?

I can easily see that the problem is in NP, but I'm having trouble proving it's NP-hard.

3. A lot of the multiple-choice questions have to do with homomorphisms and how they affect relations between languages, something I also recall seeing in a lot of midterms in semesters the class was given by Dershowitz. Is this something we need to be familiar with?