# 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!

• It's just a corollary of the general theorem that, any regular language $L$, and any language $K$, the quotient $L/K$ is regular. Then take $K$ to be the language that includes all words. – MaudPieTheRocktorate Nov 16 '18 at 13:02

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.