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:    / @easytheory  
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon:   / easytheory  
Discord:   / discord  

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

Social Media:
Facebook Page:   / easytheory  
Facebook group:   / easytheory  
Twitter:   / easytheory  

Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierar...
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-f...

If you like this content, please consider subscribing to my channel:    / @easytheory  

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀
[email protected]

▶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.