3
$\begingroup$

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!

2 Answers 2

9

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.

  • 0
    One can assume w.l.o.g. that the FSM is deterministic and has no $\lambda$-transitions. I added that to my answer.2012-06-07
1

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)$.