I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show the construction of a DFA for a homomorphism in general. For example, if I were to create a mapping between an alphabet $A$ and the binary alphabet $B$, how would I go about showing the construction of a DFA to recognize this mapping? I would really appreciate any help, whether with an actual example, or just an idea of what I would need to do.

  • 2
    $\begingroup$ I have no intention to solve this for you. But here is a tiny hint. On input of a DFA, your output could be an $\epsilon$-NFA or any other thing that recognizes a regular language. Any such algorithm could then be combined with one of the standard translations to DFAs. $\endgroup$ – Kai Feb 19 '17 at 9:10
  • 1
    $\begingroup$ Given a regexp, replace every symbol $a$ with any regexp for $h(a)$. $\endgroup$ – chi Feb 19 '17 at 12:52
  • $\begingroup$ And thank you @chi. I hadn't considered using a regular expression, but that is certainly a good technique $\endgroup$ – tpm900 Feb 19 '17 at 21:43

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.