# Regular language

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

A language is regular when a complete DFA recognizes all and exactly its words.

mko-regular-language · definition · v0.10.0



## Mathematical statement

The DFA certificate must cover every finite word over the declared alphabet. Mod-count and parity languages use a state invariant valid for arbitrary word length; a finite language can use a prefix-trie DFA construction. Finitely many tested words do not prove regularity or language equivalence.





## Representative formula (exact TeX)

R(L)





## Assumptions


- The alphabet is finite and the DFA transition function is complete and total.
- This slice adds no regex, NFA, epsilon transition, minimization or pumping-lemma machinery.





## Symbol scope


- R — regular-language certificate
- L — language as a set of words





## Intuition, definition, and misconceptions

Existence of a complete recognizing DFA is a whole-language certificate.

Parity and mod-count constructions use an invariant for every prefix.

Finite languages admit explicit DFA constructions; passing finitely many tests is not enough.

A small test suite does not establish regularity or equality of two languages.





## Adopted derivation guide

[A parity invariant for arbitrary word length](https://ocme.evemisslab.com/en/derivations/derivation-mko-regular-language-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Deterministic finite automaton](https://ocme.evemisslab.com/en/mko/mko-finite-automaton/) — A DFA supplies the recognition certificate.
- [Set](https://ocme.evemisslab.com/en/mko/mko-set/) — A language is a set of words.
- [Sequence](https://ocme.evemisslab.com/en/mko/mko-sequence/) — A word is a finite ordered symbol sequence.
- [Decision problem](https://ocme.evemisslab.com/en/mko/mko-decision-problem/) — Membership is accepted or rejected.





## Verification boundary

Only DFAs with explicit invariants or finite-language constructions are handled; no other computational model is inferred.

not_formalized

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





## Next obligation

Add NFAs, regular expressions and closure constructions.





## 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-language.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-regular-language/index.md)