self doubt

Question

The min of a language L is defined as

min(L) = { w $\epsilon$ L : there is no u $\epsilon$ L, v $\epsilon$ $\sum$*, such that w = uv }.

Show that the family of regular languages is closed under the min operation.

Answer 1

There seems to be a mistake in the question.

The definition of “min(L)” given in the question is as following :

The min of a language L is defined as

min(L) = { w $\epsilon$ L : there is no u $\epsilon$ L, v $\epsilon$ $\sum$*, such that w = uv }.

NOTE that by this definition, For any language $L,$ $min(L)$ will be $\phi$ Because every string $w$ is $w.\in.$

So, if this definition of $min(L)$ is used, then For any language $L,$ $min(L) = \phi$

---

 The Questions should be asking the following :

The min of a language L is defined as

min(L) = { w $\epsilon$ L : there is no u $\epsilon$ L, v $\epsilon$ $\sum^+$, such that w = uv }.

Show that the family of regular languages is closed under the min operation.

Answer :

First understand, for any language $L,$ What is $min(L) ?$

Take, for example,  $L = \{ a,ab,aba,ba,bb,baba \}$

What is $min(L) ?$

$min(L) = \{ a,ba,bb  \}$

Take, for example,  $L = \{ a^n b | n>= 0 \}$

What is $min(L) ?$

$min(L) = L$

Take, for example,  $L = \{ a^n b^n | n>= 1 \}$

What is $min(L) ?$

$min(L) = L$

Take, for example,  $L = \{ a^n b^n | n>= 0 \}$

What is $min(L) ?$

$min(L) = \{ \in \}$

NOTE that “Proper prefix” of any string $w$ is a prefix which is not same as $w.$

---

After understanding $min(L)$ for any language $L,$ Now we can proceed with the given question :

Let $L$ be a regular language. So, we have some DFA $D$ for $L.$

From $D,$ we can make DFA for $min(L).$

The idea is simple : From  $L,$ we want to remove those strings whose some proper prefix also belong to $L.$

Basically, If $w$ belong to $L$ then remove ALL extensions of $w$ i.e. remove all $wx$ which belong to $L$, where $x \neq \in.$

To implement this idea on DFA $D$ of $L, $ we only need to do the following :

As soon as we get into any final state, say on string $w$, that’s it. We don’t accept any further extension of $w.$

So, from EVERY Final state, send ALL transitions to a Dead State. 

Your resulting DFA will accept $min(L).$

Briefly :

To get a DFA that accepts $min(L)$ from a DFA $D$ of $L$, add a new trap state $q*$ in $D$ and modify $δ$ so that any input to an acceptor state sends $D$ to $q*$.

https://math.stackexchange.com/questions/551057/prove-regular-language-closed-under-min-and-max

https://www.cs.cornell.edu/courses/cs381/2005fa/solutions/hw5/381-hw5-solns.pdf

Comments

Amazing explanation sir.

One thing I would like to clarify is that, I'm currently seeing $min(L)$ as prefix code, or somewhat similar to that. So, is there anything wrong in thinking that sir?

---

@Priyam Garg, $min(L)$ (the correct definition discussed in my answer) is the set of those strings of $L$ whose No proper prefix is in $L.$

Prefix Code: A prefix code is a set of words C such that no word in C is a proper prefix of another word in C. Prefix codes are uniquely decodable, as the end of a codeword is immediately recognizable. 

For example, the set $\{0^i 1 | i ≥ 1 \}$ is a prefix code over the binary alphabet. 

For every $L,$ $min(L)$ will be a prefix code.