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.

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

Social Media:

Merch:

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀

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

[turkirob]

this really very good explanation but i suggest that you solve examples on it which would make it clearer

[attafriski]

I have a question. What is the relation between context-free grammar with homomorphism and inverse homomorphism sir? Sorry For My English.

[onemonsterceo]

Wow that really made things clear. Thanks