Proving that reguarity is closed under prefixes? Show that regularity is closed under prefixes. That is, if $L$ is regular,
then so is 
$$L_1 = \{x \mid \exists y: xy\in L\}$$
I am having a hard time trying to work this through. Can you please help me?
Also, From what I understand, $L$ will be a subset of $L_1$ since a string can have a prefix as the entire string itself concatenated with the null string?
Thanks!
 A: The idea is: An automaton recognizing $L$ can be transfered into one recognizing $L_1$ if we make all states accepting which lie on a path leading to an accepting state (we have to read $y$):
Let $A = (Q, \Sigma, \delta, q_0, F)$ a dfa recognizing $L$, define $F_1$ by 
$$ F_1 = \{q \in Q : \exists y \in \Sigma^*. \delta^*(q,y) \in F\} $$
Then $A_1 = (Q, \Sigma, \delta, q_0, F_1)$ recognizes $L_1$, as for $x \in \Sigma^*$ we have
\begin{align*}
   x \in L(A_1) &\iff \delta^*(q_0, x) \in F_1\\
                &\iff \exists y : \delta^*\bigl(\delta^*(q_0, x), y\bigr) \in F\\
                &\iff \exists y: \delta^*(q_0, xy) \in F\\
                &\iff \exists y : xy \in L\\
                &\iff x \in L_1
\end{align*}
Hence, $L_1$ is regular.
A: In case you are approaching this from a point of view not involving automata, like if your course material covers automata only after regular expressions and languages (which is very likely), then the idea is to show there exists is a regular expression for every prefix of a language $\mathcal L$. A language is regular, if and only if there exists a regular expression defining it, after all.
Therefore we need to go through the conditions in the recursive definition of regular expressions for an arbitrary prefix language
$$
  \operatorname{pre}\mathcal L = \{x \in\operatorname{pre} y \mid y \in \mathcal L\}\,,
$$
where the prefix of the string $y$ is $\operatorname{pre} y = \{ y[1:i] \mid i \in \{1, \ldots, |y|\}\}$ and the left associative slice operator $[m:n]$ returns the substring consisting of the letters between the indices $m$ and $n$ in the word $y$. The conditions were as follows:

The set of regular expressions generated by the alphabet $\Sigma$, $\mathrm{RE}(\Sigma)$ with the alphabet $\Sigma_{\mathrm{RE}} = \Sigma \cup \{\epsilon, \varnothing, (, ), \ast, +\}$, is the smallest set of expressions, that fulfills the following closure conditions or axioms:
  
  
*
  
*The expression $\epsilon\in\operatorname{RE}(\Sigma)$ and $\mathcal L(\epsilon) = \{\epsilon\}$
  
*The expression $\varnothing\in\operatorname{RE}(\Sigma)$ (note that here $\varnothing$ is a symbol representing the empty set, not the empty set itself) and $\mathcal L(\varnothing) = \varnothing$
  
*Every $\alpha\in\Sigma$ is also in $\operatorname{RE}(\Sigma)$, and $\mathcal L(\alpha) = \{\alpha\}$
  
*If $R, S \in\operatorname{RE}(\Sigma)$, then $R + S \in\operatorname{RE}(\Sigma)$ and $\mathcal L(R + S) = \mathcal L(R) \cup \mathcal L(S)$.
  
*If $R, S \in\operatorname{RE}(\Sigma)$, then $RS \in\operatorname{RE}(\Sigma)$, and $\mathcal L(RS) = \mathcal L(R) \mathcal L(S)$.
  
*If $R \in\operatorname{RE}(\Sigma)$, then the Kleene closure $R^\ast\in\operatorname{RE}(\Sigma)$, and $\mathcal L(R^\ast) = \mathcal L(R)^\ast$.

We now simply need to go through each of these conditions and show that there is a prefix corresponding to every one of them:


*

*Obviously $\operatorname{pre}\epsilon = \epsilon$, so $\mathcal L(\operatorname{pre}\epsilon) = \mathcal L(\epsilon)$

*Same for the symbol $\varnothing$: $\operatorname{pre}\varnothing = \varnothing$, so $\mathcal L(\operatorname{pre}\varnothing ) = \mathcal L(\varnothing)$.

*For any single symbol $\alpha\in\Sigma$, $\operatorname{pre}\alpha = \alpha$, so $\mathcal L(\operatorname{pre}\alpha ) = \mathcal L(\alpha)$

*In the case of the union $R + S \in\operatorname{RE}(\Sigma)$, we take either the prefix of the expression $R$ or the expression $S$: $\operatorname{pre}(R + S) = \operatorname{pre} R + \operatorname{pre} S$.

*The prefix of $RS \in \operatorname{RE}(\Sigma)$ is $RS[1:i]$, where $i \in \{1, \ldots, |RS|\}$.

*The Kleene closure can be reasoned fairly easily as well. For any repetition $R^\ast\in\operatorname{RE}(\Sigma)$, $\operatorname{pre}(R^\ast) = R^\ast[1:i]$
Now, you would still need to show that the languages generated by parts  4--6 are the same by using the recursive definition of a regular language (as I skipped the specifics) given above, but this is the blueprint or recipe for the proof.
