# #Ullman #RegularLanguage

1 vote
8 views

Please Correct me if Logic is wrong.
Let w = w1.w2.w3...wk,
By definition of min(L), w L but any w1.w2.w3...w(k-1) doesn’t.
Then NO prefix reach any final state regardless of their length. Using only prefixes of w drawing a dfa is not possible but w itself belongs to L and min(L).
So dfa of min(L) exists.=> Closed.

1 vote

The good thing is that you have tried to think of some formal logic to prove the Closure of Regular Set under “min” operation, But you have not framed your argument properly.

Let w = w1.w2.w3...wk, By definition of min(L), w ∈ L

Does $w \in L ???$

Also I could not make sense of your further logic.

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

1.7k points
0
Hi., Got your point. Thank You.,