ExampleConstruction: AI-generatedVerification: 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.

Running the emptiness and finiteness tests on small grammars

Example

Use the three grammars

$G_{\emptyset} : S \to A B, A \to a, B \to b B,$ $G_{\infty} : S \to A, A \to a A b ∣ a b,$ $G_{f i n} : S \to a A ∣ b, A \to c ∣ d .$

Facts & Assumptions

Given: The three displayed grammars.

[L1]

By CFG emptiness and finiteness are decidable, the emptiness and finiteness questions for CFG's are decidable by generating-variable and dependency-graph tests.

Verification

technique · direct

1.1

In $G_{\emptyset}$ , the variable $B$ never derives a terminal word, so the start symbol $S$ is not generating. The emptiness test from [L1] therefore reports $L (G_{\emptyset}) = \emptyset$ .

L1given

1.2

In $G_{f i n}$ , the dependency graph is acyclic and the grammar generates exactly the three words $a c$ , $a d$ , and $b$ . So the finiteness test from [L1] reports "finite" on this grammar.

L1given

2.1

In $G_{\infty}$ , the variable $A$ lies on a productive cycle through the rule $A \to a A b$ , so the dependency-graph test from [L1] reports infinitude. Indeed $L (G_{\infty}) = {a^{n} b^{n} : n \geq 1}$ is infinite.

L1step 1.1

3.1

These three tiny inputs realize the empty, infinite, and finite outcomes of the theorem.

step 1.1step 1.2step 2.1∎

Depends on

CFG emptiness and finiteness are decidable

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 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, CSci 311, Models of Computation, Chapter 8 (standard reference, not scraped)