Given a (Deterministic Finite Automata) DFA that recognizes a language $L$, show how to construct another DFA that recognizes the language $\max(L)$.

Question

If $L$ is any language, then $$\max(L)= \{w \mid \text{$w$ is in $L$ and there is no non-empty string $x$ such that $wx$ is in $L$} \}.$$

I am really confused about what this problem is asking and I would greatly appreciate some light.

Answer 1

This new language is composed of the "maximal elements" of $L$. For example, if $L = \{ab, ba, aba\}$, then max$(L) = \{ba, aba\}$. It doesn't include $ab$ since that can be extended to $aba$ and still be $L$.

So how can we construct a DFA recognizing this? Since $L$ is regular, it has a DFA $D = (Q, \Sigma, \delta, q_0, F)$ recognizing it. We should try to use this DFA to make a new one for max$(L)$, $D' = (Q', \Sigma, \delta', q_0', F')$. Given max$(L) \subseteq L$, it seems like a good idea to make $Q'$ the Cartesian product of $Q$ and another set. This will allow us to basically run two DFAs in parallel, and check in the first DFA if $w \in L$, and in the second that there is no way to extend $w$ to any $wx \in L$.

It may seem difficult to think of the second half of the tuple, but consider this: is there a way to cleverly define $F'$ using a simple second half, to make $F'$ do most of the work of "figuring out" if there is $wx \in L$? It may be useful to write out an actual DFA or two and see how you yourself would determine max($L$), and see if you can define an $F'$ that suffices. Remember that $Q$ is finite, so you (or a set-builder...) could do a graph search over it to find paths to accepting states. Once you have $F'$ and $Q'$, then $q_0'$ and $\delta'$ are straightforward. You could even drop the tuple entirely, but I find it easier to think about for this category of problem.

Answer 2

It is easier to use the definition of a DFA in which the transition function is allowed to be partial. Let us say that a state $q$ is accessible if there is a path from the initial state to $q$ and coaccessible if there is a path from $q$ to some final state. A DFA is trim if every state is both accessible and coaccessible. It is easy to see that every DFA is equivalent to a trim DFA (just get rid of the non-accessible and non-coaccessible states).

Now, let start with a trim DFA ${\cal A} = (Q, A, i, ., F)$ recognizing $L$ and, as suggested by copper.hat, consider the automaton ${\cal A}' = (Q, A, i, ., F')$ where $$ F' = \{q \in F \mid \text{there is at least one transition $q \xrightarrow{a} q'$ for some letter $a$\}} $$ Then ${\cal A}'$ recognizes $\max(L)$.