The language of non-extendable strings of a regular language is regular

Question

I recently came across this question in my textbook.

$ \text{Let } L \text{ be a language over an alphabet } \Sigma \text{ that is accepted by some FSA.} $ $ \text{Prove that the language is also accepted by some FSA.} $ $ \operatorname{Max}(L) = \{x \in L : \forall y \in \Sigma^* - \{ \lambda \}.\ xy \notin L \}.$

Where $ \lambda $ is the empty string in this case.

It seems that any regular language that has any maximal length string must not contain any repetition operators $"{^*}"$. Hence the regular language only consists of characters, concatenation, and alternation. That means the FSA it generates cannot contain any cycles that contain a final state.

From the above, I decided to go with cases, where the language is generated by a regular expression that contains repetition or does not.

If the regular expression contains repetition, then the FSA that accepts the new language contains only one state, the starting state, and no final states.

If the regular expression does not contain repetition, then the FSA that accepts the new language is a copy of the original FSA with the final states restricted to the final states that were the largest number of edges away from the starting state of all the final states. That means only the longest strings that were accepted will be accepted.

This description intuitively makes sense, however, I cannot see how I might begin to prove any part of this, and I do not even know if this description is fully accurate. Is this description accurate and is there an easier way? If this description is accurate, how would I go about proving it?

Answer 1

The definition does not ask for a maximal length string in $L$ but it looks for the strings that cannot be extended into a longer string in the language: $x\in L$, but no $xy \in L$ for nonempty $y$.

This means that repetitions are no problem. For $L = a^*b$ in fact $\mathrm{Max}(L) = L$ as no string can be extended to a longer string in $L$. But for $L = ba^*$ we have $\mathrm{Max}(L) = \varnothing$,as every string can be extended.

If you start with a (deterministic!) FSA, you can easily see which strings can be extended, and which not. How?

Answer 2

Recall that for languages $A,B$ over the same alphabet $\Sigma$, their quotient $A/B$ is given by $$ A/B = \{ w \in \Sigma^* : wx \in A \text{ for some } x \in B \}. $$ It is not hard to check that $$ \mathrm{Max}(L) = L \setminus (L/\Sigma^+). $$ Since $\Sigma^+$ is regular and the regular languages are closed under quotient and set difference, we see that if $L$ is regular then so is $\mathrm{Max}(L)$.

As Hendrik Jan mentions, it is in fact easy to transform a DFA for $L$ into one for $\mathrm{Max}(L)$ with the same states, by modifying the set of accepting states (exercise). This shows the stronger property that $\mathrm{index}(\mathrm{Max}(L)) \leq \mathrm{index}(L)$, where the index of a language is the number of equivalence classes in the Myhill-Nerode relation.