0
$\begingroup$

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 ?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – ttnick
    Feb 20, 2022 at 14:47
  • 1
    $\begingroup$ 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^+)$. $\endgroup$ Feb 20, 2022 at 21:08

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ by the "non-final sink state" do you mean dead state? $\endgroup$
    – MR.-c
    Feb 20, 2022 at 15:05
  • $\begingroup$ Yes, that's it. $\endgroup$
    – Nathaniel
    Feb 20, 2022 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.