# For a regular language L, the language of all words such that no prefix of them are in L is also regular

Prove that for every regular language $$L$$, the following language is regular:

$$L_{pf}=$$ $$\{x \in L |$$ no proper prefix of $$x$$ is in $$L\}$$

How should I prove this?

I understood that $$L_{pf}$$ is just subset of $$L$$ and the words inside it are special such that no word is the prefix of other one, is this right ? it's not hard if I have the words in $$L$$ to prove this, but how to generalise it ?

• Hint: Think of a DFA $\mathcal{A}$ for $L$, for $L_{pf}$ you only want to accept the runs on $\mathcal{A}$ that end in an accepting state but never pass through an accepting state. Feb 20, 2022 at 14:47
• Does this answer your question? Are regular and context free languages closed against making them prefix-free?. In particular the answer by Raphael, where it is argued that $L_{pf} = L \setminus (L\cdot \Sigma^+)$. Feb 20, 2022 at 21:08

Let $$L' = \{xx'\,|\,x\in L\,\&\,|x'|>0\}$$. Your language $$L_{pf} = L\setminus L'$$, so constructing DFA for $$L'$$ solves your task, since you can use the closure properties.
Consider a DFA $$A$$ recognizing $$L$$. Let $$F$$ be the set of the final states of $$A$$. Add a new final state $$q_T$$ to $$A$$ and for every final $$q_i\in F$$ and every terminal $$s$$ add the transitions $$(q_i, s, q_T)$$ to your automaton. Finally, make all the states in $$F$$ non-final. You get an NFA recognising words with the proper prefixes in $$L$$, and in order to use the closure properties you need to apply a determinisation algorithm. Afterwards, construct the complement and the intersection.
Take a DFA for $$L$$. Make every exiting transition from a final state go to a non-final sink state instead. (Proof details left to you)