patternMinor
The language of non-extendable strings of a regular language is regular
Viewed 0 times
extendablethenonregularlanguagestrings
Problem
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?
$ \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?
Solution
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?
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?
Context
StackExchange Computer Science Q#90901, answer score: 3
Revisions (0)
No revisions yet.