DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 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.

Computation alphabets, words, the empty word, and $Σ^{*}$

Definition

Let $Σ$ be a finite set, called an alphabet. For each natural number $n$ , a word of length $n$ over $Σ$ is a function $w : n \to Σ$ , equivalently an element of $Σ^{n}$ (The set $B^{A}$ of all functions $A \to B$ ). Writing $w (i) = a_{i}$ for $i < n$ , we display the word as $a_{0} a_{1} \dots a_{n - 1}$ . This is the same finite-word convention already used in Finite words, contiguous factors, avoidance and proper-prefix states.

The unique word of length $0$ is the empty word $ε$ .

If $u : m \to Σ$ and $v : n \to Σ$ are words, their concatenation is the word $u v : (m + n) \to Σ$ defined by $(u v) (i) : = {\begin{cases} u (i), & i < m, \\ v (i - m), & m \leq i < m + n . \end{cases}$

The set of all finite words over $Σ$ is $Σ^{*} : = ⋃_{n \in N} Σ^{n},$ an indexed union in the sense of $⋃_{i \in I} A_{i} : = ⋃ {A_{i} : i \in I}$ , and $⋂_{i \in I} A_{i} : = ⋂ {A_{i} : i \in I}$ for $I \neq \emptyset$ .

Remarks

A word is an element of $Σ^{*}$ , not a subset of $Σ$ . The symbols of the alphabet are the values of the function; the word itself is the whole finite sequence.
For the binary alphabet ${0, 1}$ the notation ${0, 1}^{*}$ means every finite binary word, including $ε$ .

Depends on

Used by

Alphabet maps into Δ^* and their induced maps on words Definition
Boone machine semigroup and augmented configurations Definition
Computable martingales on binary strings Definition
Context-free grammars Definition
Description machines and plain Kolmogorov complexity Definition
Deterministic finite automata Definition
Deterministic one-tape Turing machines with designated accept and reject states Definition
Effective binary encodings and total decoders Definition
Effectively open sets in Cantor space Definition
Epsilon-NFAs, finite epsilon closure, and extended word transition Definition
Initial tapes and machine-relative halting configurations Definition
Initial, accepting, and rejecting configurations Definition
Language concatenation, powers, and Kleene star Definition
Languages over an alphabet Definition
Marked positions and admissible Ogden decompositions Definition
Nerode equivalence of words Definition
Nondeterministic pushdown automata Definition
Parse trees and their yields Definition
Regular expression syntax over an alphabet Definition
The CYK parsing table and span variables Definition
The extended transition function of a DFA Definition
The Turing-machine acceptance problem A_TM Definition
Word reversal and language reversal Definition
FALSE: a language is a set of symbols False statement
FALSE: every countable language is decidable False statement
Language concatenation is associative Lemma
Reversal is an involution and reverses concatenation Lemma
The computation-word convention agrees with the published finite-word definition Lemma
The induced word map is the unique concatenation-preserving extension Lemma

Dependency tree · two levels

12 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)
John E. Savage, Models of Computation: Exploring the Power of Computing (standard reference, not scraped)
Michael Sipser, MIT 18.404J Theory of Computation, Lecture 1 (standard reference, not scraped)

Computation alphabets, words, the empty word, and Σ∗Σ∗