476 views
0 votes
0 votes
Let R be any regular set .Let Min(R) is a set of all strings 'w' in R , where every proper prefix of 'w' is not in R, then to which class of language does this Min(R) belong ?

1 Answer

Best answer
3 votes
3 votes
We have a regular set and we want to remove all strings such that in our set for any string, we should not have its prefix. Now consider the DFA for $L$. Take all of its final states and see if there is a path to any other final state. (This is a graph search problem). If so, then mark that final state as non-final because this path we found is essentially adding a "suffix" to an already accepted string in $L$ and making another string in $L$. Doing like this for all final states give us the DFA for $\text{MIN(L)}$. So, it must also be regular.
selected by

Related questions

1 votes
1 votes
2 answers
1
2 votes
2 votes
3 answers
2
3 votes
3 votes
2 answers
3
RRajeev asked Jun 29, 2015
7,733 views
is the language WXWR is regular? can any one provide the proof?
0 votes
0 votes
0 answers
4
Garrett McClure asked Oct 31, 2017
355 views
Given an S-R flip-flop in the 0 state, what is the sequence of inputs necessary to cause the following sequence of states:0, 0, 1, 1, 0, 0, 1, 0, 1.