# Regular expression

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

Regular expressions recursively build languages from the empty language, epsilon, alphabet symbols, union, concatenation and Kleene star.

mko-regular-expression · definition · v0.10.0



## Mathematical statement

The typed AST permits only empty-language, epsilon, alphabet symbols, union, ordered concatenation and star; every symbol belongs to the explicit alphabet. Its language is defined recursively. Bounded star enumeration uses fixed-point closure with extensional deduplication to terminate epsilon cycles. Word membership must be decided with a sufficient complete length slice, not by absence from an insufficient bound. Unions are canonicalized under permutation and idempotence, while concatenation order is retained. The empty language differs from the language containing the empty word, a shell wildcard is not this core regex AST, and equality through length N does not imply equality of the full languages.





## Representative formula (exact TeX)

R(A,w)=b





## Assumptions


- The alphabet is finite and unique; a word is a finite sequence of its symbols.
- Every AST node type, key set and arity is validated.
- A bounded language is explicitly limited to length≤N and is not unbounded equivalence.





## Symbol scope


- R — regular-expression semantics operator
- A — finite alphabet
- w — finite word
- b — membership Boolean





## Intuition, definition, and misconceptions

Qualify the typed AST and alphabet first.

Bounded star closure handles epsilon and deduplication.

Separate complete word membership from bounded-equivalence boundaries.

The empty language is not epsilon, shell wildcard syntax is not a Kleene-star AST, and finite-bound agreement is not full equivalence.





## Adopted derivation guide

[Star closure with epsilon and a complete length slice](https://ocme.evemisslab.com/en/derivations/derivation-mko-regular-expression-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Regular language](https://ocme.evemisslab.com/en/mko/mko-regular-language/) — Use the semantic codomain.
- [Set](https://ocme.evemisslab.com/en/mko/mko-set/) — Form language unions.
- [Sequence](https://ocme.evemisslab.com/en/mko/mko-sequence/) — Represent words and concatenation.
- [Mathematical induction](https://ocme.evemisslab.com/en/mko/mko-mathematical-induction/) — Retain AST and star recursion.





## Verification boundary

Bounded enumeration certifies only the specified length slice.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add regex-to-NFA construction and equivalence decision procedures.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/regular-expression.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-regular-expression/index.md)