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.orgBecome a member:
https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams):
https://streamlabs.com/easytheory1/tipPaypal:
https://paypal.me/easytheoryPatreon:
https://www.patreon.com/easytheoryDiscord:
https://discord.gg/SD4U3hsYoutube 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/EasyTheoryMerch:
Language Hierarchy Apparel:
https://teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel:
https://teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel:
https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1Gold 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