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 ?

Improve this question
$\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$
    – Hendrik Jan
    Feb 20, 2022 at 21:08

2 Answers 2

Reset to default
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.

Improve this answer
$\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)

Improve this answer
$\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 that you have read and understand our privacy policy and code of conduct.

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