LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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-expression denotation is structurally well-defined

Statement

For every regular expression $R$ over an alphabet $Σ$ , there exists a unique language $L (R) \subseteq Σ^{*}$ satisfying the recursive clauses of The language denoted by a regular expression.

Facts & Assumptions

Given: A regular expression $R \in Reg (Σ)$ .

[L1]

By Regular expression syntax over an alphabet, every regular expression is obtained from the base symbols $\emptyset, ε, a$ by finitely many applications of union, concatenation, and star.

[L2]

By The language denoted by a regular expression, the intended denotation is fixed on the three base symbols and, for a composite expression, is obtained from the denotations of its immediate subexpressions by one of the operations $L \cup K$ , $L K$ , or $L^{*}$ .

Proof

technique · direct

1.1

By [L1], every regular expression has a finite construction tree, so there is a well-founded induction on the number of constructor occurrences in that tree.

L1given

2.1

In the base cases $R = \emptyset$ , $R = ε$ , and $R = a$ , the language is uniquely fixed by [L2]. If $R$ is composite, then its outermost constructor is uniquely one of $+$ , concatenation, or $^{*}$ by [L1]. The induction hypothesis gives unique denotations to the immediate subexpressions, and then [L2] applies one fixed language operation to those already determined languages.

L1L2step 1.1induction

3.1

Therefore exactly one language $L (R)$ satisfies the recursive clauses for the given expression $R$ .

step 2.1∎

Depends on

Used by

Dependency tree · two levels

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