Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax132576.EpsilonEliminationExtended

Elimination of ε-transitions, with extended transitions

concepts/Lax132576/EpsilonEliminationExtended.lean · lax-132576

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Evidence

    Each proof establishes this claim relative to its assumptions.

    In the paper

    Theorem

    Every rational relation is computed by an automaton with output and extended transitions in which every accepting run is in ε-free normal form: if the input string is nonempty, each transition reads exactly one letter, and if the input is empty, the run has exactly one transition (Lemma B.2.4 of Transducers, first sentence). After arranging that no state is both initial and final and that every transition reads at most one letter, the usual elimination replaces, for every letter aa and states p,qp, q, the runs from pp to qq reading aa and any number of empty-input transitions by one transition labelled with the regular language of their outputs; a fresh initial and a fresh final state with one transition between them, labelled with the outputs on the empty input, take care of the empty string.

    Lean source view on GitHub

    1import Lax132576.EpsilonFreeAutomata
    2
    3/-!
    4---
    5title: Elimination of ε-transitions, with extended transitions
    6type: theorem
    7---
    8Every rational relation is computed by an automaton with output and extended
    9transitions in which every accepting run is in ε-free normal form: if the input
    10string is nonempty, each transition reads exactly one letter, and if the input
    11is empty, the run has exactly one transition (Lemma B.2.4 of *Transducers*,
    12first sentence). After arranging that no state is both initial and final and
    13that every transition reads at most one letter, the usual elimination replaces,
    14for every letter aa and states p,qp, q, the runs from pp to qq reading aa and
    15any number of empty-input transitions by one transition labelled with the
    16regular language of their outputs; a fresh initial and a fresh final state with
    17one transition between them, labelled with the outputs on the empty input, take
    18care of the empty string.
    19
    20# Formalization notes
    21
    22The automaton is a `LabAut` with regular languages as labels
    23(`IsExtendedNFAO`), its relation is `extRel`, and the normal form is
    24`EpsilonFree`. Both alphabets are assumed finite.
    25-/
    26
    27namespace Lax132576.EpsilonEliminationExtended
    28
    29open Lax132576.LabelledAutomata Lax132576.RationalRelations Lax132576.EpsilonFreeAutomata
    30
    31/-- Every rational relation is computed by an ε-free automaton with extended
    32transitions. -/
    33axiom exists_extended_epsilonFree {A B : Type} [Finite A] [Finite B]
    34 {R : List A → List B → Prop} (hR : IsRationalRel R) :
    35 ∃ (Q : Type) (_ : Finite Q) (M : LabAut A (Language B) Q),
    36 IsExtendedNFAO M ∧ EpsilonFree M ∧ ∀ w v, R w v ↔ extRel M w v
    37
    38end Lax132576.EpsilonEliminationExtended
    39
    Show Proof

    Formalization notes

    The automaton is a LabAutLabAut with regular languages as labels (IsExtendedNFAOIsExtendedNFAO), its relation is extRelextRel, and the normal form is EpsilonFreeEpsilonFree. Both alphabets are assumed finite.

    Used by

    none

    From Mathlib

    none

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…