Motivation
Changing an alphabet can reveal or hide structure in a language. A homomorphism replaces each input symbol by a fixed word, possibly empty, and extends that replacement to whole words by concatenation. Regular languages remain regular under both direct images and inverse images, but the two constructions work in different directions.
For an inverse image, a DFA can simulate the entire replacement word for each input symbol. For a direct image, each old transition is replaced by a path spelling its output word; empty replacements naturally become -transitions. Both constructions are effective and handle erasing symbols explicitly.
Definitions
Definition 1.5.1
(String homomorphism and erased symbols)
Let and be finite alphabets. A monoid homomorphism is specified by a word for each , with and . A symbol is erased if its image is .
Definition 1.5.2
(Direct image and inverse image)
For , the direct image is . For , the inverse image is . These are different operations on languages over different alphabets.
A DFA has extended transition function on words. An -NFA may take transitions labeled without consuming an input symbol. Both are finite automata; -NFAs can be determinized by -closure and subset construction.
Theorem 1.5.3
(Inverse homomorphic image)
If is regular, then is regular. Given a DFA for with states, an -state DFA for the inverse image is obtained by simulating each replacement word on one input transition.
Theorem 1.5.4
(Direct homomorphic image)
If is regular, then is regular. Given a finite automaton for and the finitely many words , an -NFA for can be constructed effectively.
Proof: inverse image by block simulation
Proof
(Block simulation of an inverse image)
Let accept . Build a DFA on the same state set, start state and accepting set, but over alphabet , with transition
If , this transition leaves the state unchanged. For a word , induction on gives
Thus the new machine accepts exactly when , which is the definition of . It has the same states, although it can be minimized further. The finite transition table can be computed by simulating each explicitly given image word from each original state.
Proof X-ray
One input symbol may simulate a whole word
The inverse-image machine reads one symbol but follows the original DFA through every symbol of internally. If the image is empty, it follows no original transition and stays in the same state.
The key move is to package original steps into one new step. The induction on uses with and , which is where enters. The DFA must be complete, so that exists for every state and symbol. The empty image needs no separate case, since .
Proof: direct image by replacing transitions
Proof
(Replacing each transition by a path)
Let an NFA for have a transition . If with , replace that transition by a path from to labeled , using fresh intermediate states unique to that transition. If , replace it by an -transition from to . Keep the original initial and accepting states. Existing -transitions, if any, remain -transitions.
An original accepting run on becomes a run on by expanding each transition into its replacement path. Conversely, every run in the new automaton can be decomposed into complete replacement paths and old -transitions: fresh intermediate states have only the continuation belonging to their path. For each complete path or erased edge, choose a corresponding original transition; if identical new edges were merged, any witnessing original transition suffices. Collapsing the choices gives an original run on some word , and the new run's consumed label is . Therefore the new automaton accepts exactly .
The construction is finite. A transition with image length adds intermediate states; an erased transition adds none and becomes . The total size is bounded by the sum of the explicitly given replacement lengths over transitions, plus the old states and transitions. Determinizing the resulting -NFA is possible but can increase the number of states.
Proof X-ray
Why a run of the new automaton collapses
The expansion direction is routine; the argument lives in the converse. A run of the new automaton can enter a fresh intermediate state only through the first edge of a replacement path, and from there it has exactly one way to continue, so it cannot leave the path before the path is complete. Hence every run splits into whole replacement paths and old -edges, each standing for one original transition. Two hypotheses are essential: the intermediate states are fresh, and every word is finite, so only finitely many of them are added. When no intermediate state appears and the splitting is immediate.
Worked examples
Worked example 1.5.5
(Erasing a symbol in a direct image)
Let , with and . Each occurrence of 01 maps to ab, so . In the transition construction, a zero transition becomes an a-then-b path and a one transition becomes an -transition.
Worked example 1.5.6
(Inverse image of even length)
Let be the language of even-length words over , with and . A word maps to even length exactly when it has an even number of zero symbols; every one contributes two letters and does not affect parity. The inverse-image DFA changes parity on 0 and stays in the same state on 1.
Worked example 1.5.7
(An empty replacement)
If , the inverse-image transition for is at every state. Reading an erased input symbol cannot change whether the simulated output prefix is accepted.
Worked example 1.5.8
(A direct-image collision)
If , the different source words a and b both map to x. The direct image is a set, so it contains x once. The constructed NFA may have two accepting runs for x; nondeterministic acceptance requires at least one, not exactly one.
Common mistakes
Counterexample mode
Images do not generally commute with complement
Let , and . Then and as well. These two images overlap, so the image of a complement is not the complement of the image in general.
Inverse images do commute with complement when the complement universes are specified: . This follows by checking whether belongs to . It is a different claim from the failed direct-image identity.
Common mistake
(Assuming every image is nonempty)
A homomorphism may erase symbols. Assuming every image has positive length would omit valid cases, and interpreting an erased transition as consuming an ordinary symbol would recognize the wrong language.
Common mistake
(Treating the inverse image as an inverse function)
The set is defined for every homomorphism, even when has no inverse, and the two operations do not undo each other. With and , we get but . In general and : a target word outside the range of has no preimage.
Direct images through expressions
There is another proof of direct-image closure when the source language is given by a regular expression. Replace every source symbol in the expression by the literal expression spelling , using when the image is empty. Leave union, concatenation, star, and in place.
The key identities are
For concatenation, each image equals , and every pair of source words gives such an image. For star, a source word is a finite concatenation of words from ; its image is a finite concatenation of their images. Conversely, every finite concatenation of images arises from a corresponding finite concatenation of source words. The zero-factor case is . These identities give a structural induction proving the substitution construction.
For example, if , and , replacing the symbols gives . Its language is . The construction can produce redundant syntax, but redundancy does not affect the represented language. It also makes clear that erasure can create factors without creating an infinite expression.
A detailed inverse-image trace
Let be the even-length unary language and use , . Its DFA has an even state and odd state , with each a toggling them. In the inverse-image DFA, reading 0 simulates one toggle, so . Reading 1 simulates two toggles and returns to the same state.
For source word 1010, the inverse machine follows and accepts. Its image is aa followed by a, then aa, then a, a word of length six. For source word 101, the machine ends in , and its image has odd length five. The block simulation invariant relates these two descriptions at every prefix, not just at the end.
The image word for one source symbol can contain several output symbols, so a source input of length can map to a word much longer or shorter than . The inverse DFA performs those simulations while constructing its transition table. Its later run has one table transition per source symbol; preprocessing cost still depends on the lengths of the specified images.
Size and representation costs
Suppose the source DFA for a direct image has states and is total over . It has transitions. For a symbol with image length , replacing all its transitions adds intermediate states. Thus the -NFA has at most
states. The count may be smaller if unreachable states are removed or transitions share structure, but the simple construction uses fresh intermediate states to make its reverse-run proof direct. The number of replacement edges is similarly bounded by , counting an erased transition as one -edge.
For the inverse image of an -state DFA, the new transition for each pair is computed by following from . A direct implementation takes transition-table work, including the empty-image cases. The resulting DFA still has states, but writing its transition entries is part of the cost. These bounds assume finite alphabets and explicitly represented image words.
Erasure and runs
An -NFA can have -cycles. They do not invalidate the direct-image language proof: acceptance requires a finite run, and each finite new run decomposes into finitely many replacement paths. An erased source transition corresponds to an -step that still records which original source transition was used. Several source words can map to the same output word, and the new automaton may have several accepting runs for it.
For example, if a source automaton accepts and , every source word maps to the empty word. The image language is exactly , not an infinite set of different empty words. The replacement automaton can traverse its -loop any finite number of times, but all those runs consume the same word. Language membership ignores the number of runs.
Conversely, a target word need not have any source preimage. If and the source alphabet is , every image has even length; x cannot be in the direct image of any source language. The construction enforces this constraint through complete replacement paths rather than accepting an arbitrary prefix of a path.
Why fresh intermediate states matter
Suppose two source transitions have images with overlapping prefixes. If their replacement paths shared an intermediate state without a careful construction, a new run might enter the path for one source transition and leave along the continuation of another. That spliced path need not correspond to any original transition. Giving each transition its own intermediate states prevents this accidental mixing.
After a complete path ends at an original state, the new run can choose another replacement path just as the old automaton chooses another transition. If the image length is one, no intermediate state is needed. If it is zero, the -edge has at least one corresponding source transition, even if identical -edges from different transitions are represented only once. These cases make the collapse argument uniform across all replacement lengths.
Boolean operations on inverse images
For any target languages , membership of in means exactly that lies in both target languages. Therefore
The same pointwise argument works for union and for complement relative to the specified alphabets. It does not depend on regularity; regularity ensures that finite automata for the resulting languages exist.
Counterexample mode
Direct images do not preserve intersections
A tempting claim is . Direct images behave differently because two distinct source words can map to the same target word. The disjoint singleton languages and have overlapping images when . Thus an image of an intersection need not equal the intersection of images. The distinction is about quantifiers and possible collisions, not about whether the source languages are regular. Here and , so and , whereas . Only the inclusion holds in general.
Summary
Inverse images are recognized by simulating each replacement word in the original DFA. Direct images are recognized by replacing source transitions with output-labeled paths, using -transitions for erased symbols. Both constructions preserve regularity.
Exercises
Quick check
(If and , compute .)
Apply symbol by symbol and concatenate.
Solution · Answer
.
Quick check
(What inverse-image transition is used when ?)
Recall .
Solution · Answer
It is a self-transition at each state, since .
Quick check
(Why can reversing a direct-image run into a source run require remembering which replacement path was followed?)
Ask whether the consumed output word alone determines a source transition.
Solution · Answer
Different source symbols can have the same image, so the consumed output word alone need not identify the source transition. The fresh intermediate states of a replacement path record which transition was used, and that choice lets us select a corresponding source transition.
Quick check
(Does a direct homomorphic image always preserve disjointness of languages?)
Try two different source symbols with the same image.
Solution · Answer
No. With , the disjoint source languages and both have image .