# The language that contains no proper prefixes of all words of a regular language is regular

Let $L$ be a regular language. I need to prove that the language $$M_L = \{w \in L \; | \forall x \in L \; \forall y \in \Sigma^+ : w \neq xy \}$$ that contains all words of L that do not have a related proper prefix in L.

As an example I thought about the language $L_1 = \{12,34,56,3456\}$ where $M_{L_1} = \{12,34,56\}$. I played around with complement of the automaton of the language L and the intersection of this automaton with the one of the language L (no complement) and some modifications, but am stuck right now.

-

The condition that no proper prefix is in $L$ means that the input should be rejected if you encounter an accepting state before the word is completely read. So you could use a FSM for $L$ with the modification that from an accepting state all transitions are redirected to a non-accepting error state.

Edit: Of course, one has to assume w.l.o.g. that the FSM that recognizes $L$ is deterministic and has no $\lambda$-transitions.

-
This construction does not work if the automaton is nondeterministic. It works for deterministic ones, so it's still a valid proof idea. –  Raphael Jun 7 '12 at 11:45
One can assume w.l.o.g. that the FSM is deterministic and has no $\lambda$-transitions. I added that to my answer. –  marlu Jun 7 '12 at 11:59

this is a similar problem i hope this helps u...

We say a string x is a proper preﬁx of a string y, if there exists a non-empty string z such that xz = y. For a language A, we deﬁne the following operation NOEXT END(A) = {w ∈ A | w is not a proper preﬁx of any string in A} Show that if A is regular, then so is NOEXT END(A).[20 points] Solution: Given a DFA for the language A, we want to accept only those strings which reach a ﬁnal state, but to which no string can be added to reach a ﬁnal state again. Hence, we want to accept strings ending in exactly those ﬁnal states, from which there is no (directed) path to any ﬁnal state (not even itself). For a given state q ∈ F, we can check if there is a path from q to any state in F (or a cycle involving q) by a DFS. Let F 0 ⊆ F be the set of all the states from which there is no such path. Then changing the set of ﬁnal states of the DFA to F 0 gives a DFA for NOEXT END(A)

-