New to automata, looking for some clearification and some guidance.
I understand the concept of prefix and proper prefix, but I'm struggling with the following question: (It is translated, so forgive me for the misspelling) For $L$ over finite letters:
$\max(L) = \{w \in L \mid L \text{ does not contain $w'$ in $L$ so that the word $w$ is a proper prefix of $w'$} \}$
Q: what is $\max(L)$ for the language over $\{a, b, c\}$? Describe the language $\max(L)$ using a regular expression.
The language is $L = \Sigma + \Sigma\Sigma + \Sigma\Sigma\Sigma$
I'm quite confused but this definition, do they mean that $\max(L)$ is simply a language with no proper prefix? If so how would one describe it using a regular expression?
$(a+b+c)^* (a+b+c)^+$?
Any help or references will be greatly appreciated. I've been going over a few books, including CODES AND AUTOMATA, and Sipser's book.
The essence here is to understand what the function $max$ does. It is a function on a language -- and recall that a language is just a set of sentences -- which produces a subset of the language.
Specifically, given a language $L$, $max(L)$ consists of those sentences in $L$ which are maximal in the sense that they cannot be extended to produce another sentence in $L$. If, for example, $L$ is $\{a, b, aba\}$, then $max(L)$ is $\{b, aba\}$. $a$ is not an element of $max(L)$ because it is a proper prefix of $aba$.
For finite languages, that's all pretty simple; it is clear how to compute $max(L)$ for any finite $L$. It gets more interesting for infinite languages. In particular, it will turn out that if $L$ is a regular language, so is $max(L)$.
The simplest proof of this assertion is based on the fact that regular languages and finite-state automata (FSA) are equivalent. That's because there is a reasonably simple transformation of a (deterministic) FSA which will produce the $max$ of the language recognised by the FSA. Try to see if you can figure that transformation out.
One way to solve the problem you've been given is to turn the given language $L$ (which you don't specify, but which must be part of the problem) into a FSA. Then transform the FSA into the $max$, and finally turn that back into a regular expression. However, except for very simple regular expressions, that will be extremely tedious.
In many cases, though, it is trivial. For example, $max(a^*)$ is the empty set, because every sentence in $a^*$ can be extended by adding another $a$. On the other hand, $max(a^*b)$ is $a^*b$, because no sentence can be extended. Not all regular expressions are so accommodating but you can get a long way by thinking about how $max$ interacts with the regular expression operators.