Language of prefixes of regular language is regular.

Question

Let $L$ is regular language and $L_1$ be the language of all words whose prefixes are all in $L$. I need hint to prove that $L_1$ is regular.

Answer 1

A word $w_1w_2\dots w_n$ will be accepted by $L_1$ if all the words $w_1w_2\dots w_m$, for $m\leq n$ are accepted by $L$.

So you can start from a finite automaton that defines $L$ and you modify it so that it rejects the word that is feeded to it as soon as any of its intermediate states rejects. You can do this by collecting all the states that are not-accepting into one new state that is itself not accepting and from which there is no way out. (I.e. all arrows starting at this new state go back to itself.)

Then this new automaton will work just like the old one, except that if at some point the old automaton would reach a state that is not accepting, the new one will go to a not accepting state, and stay there forever, so the word is not accepted.

Answer 2

The complement of $L_1$ is the set of words having at least one prefix not in $L$. Therefore, denoting by $K^c$ the complement of a language $K$ of $A^*$, we get $$ L_1 = (L^cA^*)^c $$ Since regular languages are closed under complementation and under product, the result follows.

Answer 3

Suppose $L$ is recognized by a DFA $D$. Then what you need to do is build a new DFA $D'$ from $D$. $D'$ has exact same states as $D$, but for each state $s \in D$, if there's an accepting state reachable from $s$, then the corresponding state in $D'$ will be an accepting state.

And $D'$ will recognize $L_1$.