DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 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.

The language denoted by a regular expression

Definition

Fix an alphabet $Σ$ . The denotation of a regular expression $R \in Reg (Σ)$ is the language $L (R) \subseteq Σ^{*}$ defined recursively by

$L (\emptyset) = \emptyset, L (ε) = {ε}, L (a) = {a} (a \in Σ),$

and by the recursive clauses

$L (R + S) = L (R) \cup L (S),$ $L (R S) = L (R) L (S),$ $L (R^{*}) = L (R)^{*} .$

The operations on the right are the language union, concatenation, and Kleene star from Boolean operations on languages over a fixed alphabet and Language concatenation, powers, and Kleene star.

Remarks

The syntax $R$ and the language $L (R)$ have different types: one is a formal expression, the other is a subset of $Σ^{*}$ .
The recursive clauses are meaningful only because the next lemma makes the denotation assignment structurally well-defined.

Depends on

Used by

Generalized NFA's and their accepted languages Definition
FALSE: a regular expression is the same object as its denoted language False statement
Regular-expression denotation is structurally well-defined Lemma
Every regular expression has an equivalent epsilon-NFA Theorem
Regular languages are closed under homomorphic image Theorem

Dependency tree · two levels

7 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)