search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
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. 
in Theory of Computation 13 points 8 views

1 Answer

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.,
...