Lax132576.EpsilonEliminationExtended
Elimination of ε-transitions, with extended transitions
concepts/Lax132576/EpsilonEliminationExtended.lean · lax-132576
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 46 of the paper of lax-157538, Transducers
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 and states , the runs from to reading 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
| 1 | import Lax132576.EpsilonFreeAutomata |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Elimination of ε-transitions, with extended transitions |
| 6 | type: theorem |
| 7 | --- |
| 8 | Every rational relation is computed by an automaton with output and extended |
| 9 | transitions in which every accepting run is in ε-free normal form: if the input |
| 10 | string is nonempty, each transition reads exactly one letter, and if the input |
| 11 | is empty, the run has exactly one transition (Lemma B.2.4 of *Transducers*, |
| 12 | first sentence). After arranging that no state is both initial and final and |
| 13 | that every transition reads at most one letter, the usual elimination replaces, |
| 14 | for every letter and states , the runs from to reading and |
| 15 | any number of empty-input transitions by one transition labelled with the |
| 16 | regular language of their outputs; a fresh initial and a fresh final state with |
| 17 | one transition between them, labelled with the outputs on the empty input, take |
| 18 | care of the empty string. |
| 19 | |
| 20 | # Formalization notes |
| 21 | |
| 22 | The 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 | |
| 27 | namespace Lax132576.EpsilonEliminationExtended |
| 28 | |
| 29 | open Lax132576.LabelledAutomata Lax132576.RationalRelations Lax132576.EpsilonFreeAutomata |
| 30 | |
| 31 | /-- Every rational relation is computed by an ε-free automaton with extended |
| 32 | transitions. -/ |
| 33 | axiom 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 | |
| 38 | end Lax132576.EpsilonEliminationExtended |
| 39 |
Formalization notes
The automaton is a with regular languages as labels (), its relation is , and the normal form is . Both alphabets are assumed finite.
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