Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 is regular.

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.

Could you please help me to go on?

Thanks in advance!

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
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 prefix of a string $y$, if there exists a non-empty string $z$ such that $xz = y$.

For a language $A$, we define the following operation

$$\text{NOEXT END}(A) = \{w \in A | w \text{ is not a proper prefix of any string in A}\}$$

Show that if $A$ is regular, then so is $\text{NOEXT END}(A)$.[20 points]

Solution: Given a DFA for the language $A$, we want to accept only those strings which reach a final state, but to which no string can be added to reach a final state again.

Hence, we want to accept strings ending in exactly those final states, from which there is no (directed) path to any final state (not even itself). For a given state $q\in 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 final states of the DFA to $F_0$ gives a DFA for $\text{NOEXT END}(A)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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