0
$\begingroup$

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 | L 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 𝐿 = Σ + ΣΣ + ΣΣΣ

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.

$\endgroup$
2
  • 1
    $\begingroup$ "for the language over $\{a,b,c\}$" - for which langugae over $\{a,b,c\}$? E.g., if $L=\{a,b,c\}^*$ then clearly (just elaborate the definition) $\max(L)=\emptyset$ $\endgroup$ May 11, 2019 at 21:04
  • $\begingroup$ corrected the question: It is a finite language over {a,b,c} $\endgroup$
    – Immanuel
    May 12, 2019 at 6:59

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I corrected the question: it is over a finite language over {a,b,c}. Can you elaborate why over finite languages it is very simple? $\endgroup$
    – Immanuel
    May 12, 2019 at 7:00
  • $\begingroup$ @immanuel: your edit doesn't really help. The question must specify a particular language. Also, please note that there is a difference between a finite language, and a language over a finite alphabet. For a finite language, you just take the list of valid sentences in reverse order by length (longest first), and add to $max$ each sentence which is not a prefix of some previously added sentence. $\endgroup$
    – rici
    May 12, 2019 at 13:18
  • $\begingroup$ Thank you for your reply, I looked at the question again, and found out that the layout of the question is put together wrong. The language was on the next page adjacent to the next question, which made it very unclear and confusing. I edited the question again. $\endgroup$
    – Immanuel
    May 13, 2019 at 5:43
  • $\begingroup$ @Immanuel: So, yes, that is a finite language and the computation of $max$ is trivial. You should be able to figure it out, and there is a pretty big hint in my previous comment. $\endgroup$
    – rici
    May 13, 2019 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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