Regular Languages Closed Under Inverse (Homo)Morphism

Here we show that regular languages are closed under inverse (homo)morphism. The idea is to have a DFA for L, and imagine any string w in L. Then a DFA for h^-1(L) would have to determine if there is a string z such that h(z) = w. The trick is to realize that the homomorphism property is useful in that we can "break up" the string w corresponding to individual characters of z, and so define the transition function for the "inverse" DFA on input a to be wherever h(a) went from that state.

A homomorphism is a function h from a set A to a set B such that for any strings x, y in A, h(xy) = h(x)h(y); informally, this means that the function can "split up" a string into individual characters, apply the function to each, and concatenate the results. The homomorphism of a language L is the set of all strings h(x) where x is in L.

An inverse homomorphism is the same as a homomorphism, but in reverse; a function h^(-1) applied to a language, which is the set of all strings x such that h(x) is in L - note that the order is swapped on h(x) and x here.

Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory

Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

Gold Supporters: Micah Wood Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com

▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=utlPZgorDLg