Prove that, if L is regular, $P(L) = \{ w \in L\text{ } |\text{for any prefix } w' \text{ of w, } w' \in L\}$ is regular

Question

I have found one specific problem about regular languages which I am not sure how to solve:

Prove that the following language $$P(L) = \{ w \in L\text{ } |\text{for any prefix } w' \text{ of w, } w' \in L\}$$ is regular, given that L is regular too.

I thought of using closure properties, but I can't think of any other language to use for that. Any tips?

Answer 1

It is possible to construct a non-deterministic automaton for $P(L)$:

Consider a DFA of $L$, and construct an NFA by adding an accepting state with no outgoing edges, and an $\epsilon$ edge from each of the states that have a path to an accepting state in the DFA, to the new accepting state.

This way, if a word is a prefix, then there is a path from the end of its run on the DFA to an accepting state, and there is an $\epsilon$ transition to the new accepting state.

If there is a run which reaches an accepting state, then it is either a run of the DFA (and then the word is in $L\subset P(L)$) or a run reaching the new accepting state, and therefore must be a word that reached a state that has a path to an accepting state in the DFA, therefore a prefix.

Answer 2

Your idea of using closure properties was the right one. First observe that $P(L)$ is the set of words in $L$ with no prefix in $L^c$ (the complement of $L$). Now, the set of words with no prefix in $L^c$ is the complement of the set $L^cA^*$ of words having a prefix in $L^c$. Altogether, you get $$ P(L) = L \cap (L^cA^*)^c $$ Since regular languages are closed under intersection, complement and product, $P(L)$ is regular. This solution is more powerful that a proof using automata. It shows for instance, that if $L$ is star-free, then so is $P(L)$.