# How to prove the regularity of one language given that another is regular?

Consider the following unary operation on languages:
min(L) = {x ∈ L | no proper prefix of x is in L}
Prove that regular languages are closed under this operation; that is, prove that if language L is regular, then so is min(L).
(hint: construct a DFA to accept Min(L) based on the DFA accepting L)

After searching online, I found out that I have to:

• Let M=⟨Q,Σ,δ,q0,A⟩ be a DFA that accepts L; Q is the set of states, Σ is the input alphabet, δ is the transition function, q0 is the initial state, and A is the set of acceptor states.
• To get a DFA that accepts min(L), add a new trap state q∗ and modify δ so that any input to an acceptor state sends M to q∗.

However, I have no idea to construct a DFA for language L where it does not explicitly state the Σ. Can anyone guide me? Any help is appreciated. Thanks!

• What do you mean by "does not explicitly state the $\Sigma$"? Every language is over some alphabet, implicitly. – Yuval Filmus Nov 3 '16 at 6:42
• @YuvalFilmus what I was trying to say is that it does not state whether Σ = {a,b} or {0,1} etc. I'm still learning so forgive my mistakes. – Leonardo Vinsen Nov 3 '16 at 6:49
• I would suggest asking your TA for personal guidance. Another option is talking to your peers. – Yuval Filmus Nov 3 '16 at 6:52
• Maybe it will be helpful for you to consider some examples. Find a DFA for your favourite regular language $L$ and use it/modify it to build a DFA (or an NFA) for $min(L)$. – Hans Hüttel Nov 3 '16 at 7:31
• Try thinking for yourself instead of all that desperate googling. Draw your favourite automaton and then modifying it such that it will recognise $min(L)$. – Hans Hüttel Nov 3 '16 at 8:19