LemmaStatement: Literature-sourcedProof: 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.

Kleene star is the least concatenation-closed language containing $L$ and $ε$

Statement

Let $L$ be a language over an alphabet $Σ$ .

$ε \in L^{*}$ .
$L L^{*} \subseteq L^{*}$ .
If $K$ is a language with $ε \in K$ and $L K \subseteq K$ , then $L^{*} \subseteq K$ .

In particular, $L^{*}$ is the least language containing $ε$ and closed under left concatenation by words from $L$ ; therefore it is also the least concatenation-closed language containing $L$ and $ε$ .

Facts & Assumptions

Given: A language $L \subseteq Σ^{*}$ and a language $K \subseteq Σ^{*}$ .

[L1]

The powers of $L$ satisfy $L^{0} = {ε}$ , for $n \geq 1$ the set $L^{n}$ consists of words $u_{1} \dots u_{n}$ with each $u_{i} \in L$ , and $L^{*} = ⋃_{n \in N} L^{n}$ by Language concatenation, powers, and Kleene star.

[L2]

Language concatenation is $A B = {a b : a \in A and b \in B}$ by Language concatenation, powers, and Kleene star.

Proof

technique · direct

1.1givenL1

By [L1], $ε \in L^{0} \subseteq L^{*}$ . This proves clause 1.

1.2L1L2

Let $w \in L L^{*}$ . By [L2] there are $u \in L$ and $v \in L^{*}$ with $w = u v$ . Since $v \in L^{*}$ , [L1] gives some $n \in N$ with $v \in L^{n}$ . Then $w \in L^{n + 1}$ by the definition of $L^{n + 1}$ in [L1], so $w \in L^{*}$ again. Thus $L L^{*} \subseteq L^{*}$ , proving clause 2.

1.3givenL1base

Assume $ε \in K$ and $L K \subseteq K$ . We prove by induction on $n \in N$ that $L^{n} \subseteq K$ . For $n = 0$ , [L1] gives $L^{0} = {ε} \subseteq K$ .

1.4ihL1L2induction

For the induction step, assume $L^{n} \subseteq K$ . If $w \in L^{n + 1}$ , then by [L1] there are $u \in L$ and $v \in L^{n}$ with $w = u v$ . The induction hypothesis gives $v \in K$ , so $w \in L K \subseteq K$ . Hence $L^{n + 1} \subseteq K$ .

1.5L1L2construct

If $u, v \in L^{*}$ , choose $m, n \in N$ with $u \in L^{m}$ and $v \in L^{n}$ . Writing $u = u_{1} \dots u_{m}$ and $v = v_{1} \dots v_{n}$ with every $u_{i}, v_{j} \in L$ , the concatenation $u v$ is the $(m + n)$ -fold product $u_{1} \dots u_{m} v_{1} \dots v_{n}$ , so $u v \in L^{m + n} \subseteq L^{*}$ . Therefore $L^{*} L^{*} \subseteq L^{*}$ , and $L^{*}$ is concatenation-closed.

1.6L2

Any concatenation-closed language $K$ containing $L$ and $ε$ satisfies $L K \subseteq K$ , because for $u \in L \subseteq K$ and $v \in K$ the concatenation $u v$ lies in $K K \subseteq K$ .

2.1step 1.3step 1.4L1discharge-induction

By steps 1.3 and 1.4, every $L^{n}$ is contained in $K$ . Since $L^{*} = ⋃_{n \in N} L^{n}$ by [L1], we get $L^{*} \subseteq K$ . This proves clause 3.

3.1L1step 1.1step 2.1step 1.5step 1.6∎

Step 1.1 gives $ε \in L^{*}$ , and [L1] gives $L = L^{1} \subseteq L^{*}$ . Together with step 1.5, this shows that $L^{*}$ is itself a concatenation-closed language containing $L$ and $ε$ . Now step 2.1 and step 1.6 show that every other such language contains $L^{*}$ . This is exactly the stated minimality.

Depends on

Language concatenation, powers, and Kleene star

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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

Kleene star is the least concatenation-closed language containing LL and εε