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!

  • 1
    $\begingroup$ What do you mean by "does not explicitly state the $\Sigma$"? Every language is over some alphabet, implicitly. $\endgroup$ – Yuval Filmus Nov 3 '16 at 6:42
  • $\begingroup$ @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. $\endgroup$ – Leonardo Vinsen Nov 3 '16 at 6:49
  • 1
    $\begingroup$ I would suggest asking your TA for personal guidance. Another option is talking to your peers. $\endgroup$ – Yuval Filmus Nov 3 '16 at 6:52
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Hans Hüttel Nov 3 '16 at 7:31
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Hans Hüttel Nov 3 '16 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.