DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-08-30

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.

Alphabet maps into $Δ^{*}$ and their induced maps on words

Definition

Let $Σ$ and $Δ$ be alphabets. An alphabet map is a function $h : Σ \to Δ^{*}$ in the sense of A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain.

Its induced word map is the function $\hat{h} : Σ^{*} \to Δ^{*}$ defined as follows. For the empty word, $\hat{h} (ε) = ε$ . For a one-letter word $w = a_{0}$ , set $\hat{h} (w) : = h (a_{0})$ . For a word $w = a_{0} a_{1} \dots a_{n - 1}$ of length $n \geq 2$ over $Σ$ , set $\hat{h} (w) : = (\dots ((h (a_{0}) h (a_{1})) h (a_{2})) \dots h (a_{n - 1})),$ the left-associated concatenation of the image words of its letters.

Remarks

When every $h (a)$ has length $1$ , the induced map simply replaces each letter $a$ by a single letter $h (a)$ .
The point of the definition is that the whole map on $Σ^{*}$ is determined by the values on the letters of $Σ$ .

Depends on

Used by

Context-free languages are closed under union, concatenation, Kleene star, and homomorphism Theorem

Dependency tree · two levels

10 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

Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)

Alphabet maps into Δ∗Δ∗ and their induced maps on words