Proving that a certain language is regular

Question

Consider two languages $L$ and $\operatorname{minimum}(L) = \{ w \in \Sigma^* \mid w \in L, \text{ but no real prefix of $w$ is in $L$}\}$.

I want to prove now, that for every DFA language $L$ , minimum(L) is a DFA language too.

First thought: constructing the complement language $L^c $ . Wouldn't that describe minimum(L)?
$L^c$ is per definition regular,so there is a DFA. But that seems a bit ....mmh.

Open for any suggestions. And by the way, I am new to this stuff. Hope I offend no one with this question :)

with best regards

Answer 1

Here's two ways of doing this.

Algebraic way: note that $\Sigma^+ = \Sigma^* \setminus \{ \epsilon \}$ is regular. The concatenation of regular languages $L \Sigma^+$ is also regular. So is the difference of regular languages $L \setminus (L \Sigma^+)$. Can you see that $L \setminus (L \Sigma^+) = minimum(L)$?

Automaton way: take a DFA for $L$, and add a "trap" state, where all arrows from it point to itself. For each accept state, redirect all arrows to the trap state. So the only way to accept a word is to reach an accept state and have no more symbols to process.

Answer 2

Henry's answer is very succinct and nice. But let me add another solution, proceeding the lines of your initial thoughts, i.e. working with the complement, thus showing that it is possbile to do it that way.

For this we need some way to detect that we have at least one proper prefix from our language. We introduce $$ \operatorname{prefcount}_n(L) := \{ u \in L \mid \mbox{at least $n$ proper prefixes of $u$ are contained $L$} \} $$ then we have $$ (\min(L))^C = L^C \cup \operatorname{prefcount}_1(L) $$ and by the closure properties of regular languages by union and complement, if we can establish that the $\operatorname{prefcount}_n$-operator preserves regularity, we are done. (also note that $\operatorname{prefcount}_0(L) = L$). Let $\mathcal A = (X, Q, \delta, q_0, F)$ be an automaton for $L$, then set $$ Q' := Q \times \{ 0,1,\ldots, n + 1\}, \quad F' := F \times \{n+1\} $$ (the second component in the state essentially counts how often we entered a final state in the processing of the word), and $$ \delta((q, i), x) := \left\{\begin{array}{ll} (\delta(q,x), i) & \delta(q, x) \notin F \\ (\delta(q,x), i+1) & \delta(q,x) \in F \end{array}\right. $$ for $i = 0,\ldots, n$ and $\delta((q,n+1), x) := (\delta(q,x), n+1)$.

Set $\mathcal A' := (Q', X, \delta', (q_0,0), F')$, I claim $L(\mathcal A') = \operatorname{prefcount}_n(L)$.

To see this, let $u \in \operatorname{prefcount}_n(L)$. Note that by forgetting the second component, the automaton essentially works like the original one (this could be made more precise by the notion of automata homomorphism), or said differently we have $n+1$ ''layers'' of the same automaton that work the same, despite that before entering a final state, we switch to the ''next layer''. Hence if $u$ has $n$ proper prefixes in $L$, by processing $u$ we switch for the first occurence to the first layer, for the second proper prefix to the second layer, hence after processing of the $n$ proper prefixes we are in the $n$-th layer, and here we continue processing $u$ like the original automaton. As $u \in L$ we have to enter a final state one more time, i.e. switch to the $n+1$ layer, then either we are done ($u$ has precisely $n$ proper prefixes from $L$), or we continue processing $u$ in the $n+1$ layer, where we have to enter a final state again as $u \in L$, in either case we end up in a state from $F \times \{n+1\}$, i.e. $u$ is accepted by the automaton. Conversely let $w \in L(\mathcal A')$, then $w$ moves the automaton into a state from $F \times \{n+1\}$. By construction this mean in processing the proper prefixes we must have passed through a final state in the original automaton $n$ times, i.e. $w$ must have $n$ proper prefixes from $U$. $\square$

Finally let me give one easy generalisation of this, define for $U, V \subseteq X^{\ast}$ the language $$ \operatorname{prefcount}_n(U,V) := \{ u \in U \mid \mbox{at least $n$ proper prefixes from $u$ are contained in $V$}\} $$ and I claim that for regular $U,V$ this set is also regular. Let \begin{align*} \mathcal A_1 & = (Q_1, X, \delta_1, q_{01}, F_1) \\ \mathcal A_2 & = (Q_2, X, \delta_2, q_{02}, F_2) \end{align*} be two automata for $U$ and $V$ respectively. Then set $$ Q := Q_1 \times Q_2 \times \{0,\ldots, n+1\}, \quad F := F_1 \times Q_2 \times \{n+1\} $$ and $$ \delta((q, q', i), x) := \left\{ \begin{array}{ll} (\delta_1(q,x),\delta_2(q',x), i) & \mbox{if } \delta_2(q',x)\notin F \\ (\delta_1(q,x),\delta_2(q',x),i+1) & \mbox{if } \delta_2(q',x) \in F \end{array}\right. $$ for $i = 0,\ldots, n$ and $\delta((q,q',n+1), x) := (\delta_1(q,x), \delta_2(q,x),n+1)$. Set $\mathcal A = (Q, X, \delta, (q_{01}, q_{02}, 0), F)$ and we have $L(\mathcal A') = \operatorname{prefcount}_n(U,V)$, the proof is similar as above.