TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Regular languages are closed under inverse homomorphism

Statement

Let $h : Σ \to Δ^{*}$ be an alphabet map with induced word map $\hat{h} : Σ^{*} \to Δ^{*}$ . If $K \subseteq Δ^{*}$ is regular, then ${\hat{h}}^{- 1} (K) : = {w \in Σ^{*} : \hat{h} (w) \in K}$ is regular over $Σ$ .

Facts & Assumptions

Given: An alphabet map $h : Σ \to Δ^{*}$ and a regular language $K \subseteq Δ^{*}$ .

[L1]

By Alphabet maps into $Δ^{*}$ and their induced maps on words, the induced map $\hat{h}$ is obtained by concatenating the image words of the letters of the input word.

[L2]

By The extended transition function of a DFA, a DFA transition function extends from letters to words, and the extension respects the recursive clause $δ^{*} (q, u a) = δ (δ^{*} (q, u), a)$ .

[L3]

By Acceptance of a word by a DFA and the recognized language, a word is accepted exactly when the extended transition from the start state lands in an accepting state.

[L4]

By Regular languages, every regular language is recognized by some DFA.

Proof

technique · direct

1.1

Choose a DFA $D = (Q, Δ, δ, q_{0}, F)$ with $L (D) = K$ by [L4]. Define a DFA $D_{h}$ over $Σ$ with the same state set, start state, and accepting set by $δ_{h} (q, a) : = δ^{*} (q, h (a))$ for each $q \in Q$ and $a \in Σ$ .

L2L4givenconstruct

2.1

We claim that for every word $w \in Σ^{*}$ one has $δ_{h}^{*} (q_{0}, w) = δ^{*} (q_{0}, \hat{h} (w))$ . The proof is by induction on $∣ w ∣$ : for $w = ε$ both sides equal $q_{0}$ , and appending one letter $a$ updates the left-hand side by $δ_{h} (-, a)$ and the right-hand side by the block $h (a)$ , exactly as [L1] and [L2] prescribe.

L1L2step 1.1induction

3.1

By [L3] and step 2.1, the DFA $D_{h}$ accepts $w$ exactly when $D$ accepts $\hat{h} (w)$ , that is, exactly when $\hat{h} (w) \in K$ . Thus $L (D_{h}) = {\hat{h}}^{- 1} (K)$ , so the inverse image is regular.

L3step 2.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

H. Conrad Cunningham, Notes on Models of Computation, Chapter 4: Properties of Regular Languages (standard reference, not scraped)
Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)