Lax132576.BimachineOfRational
Rational functions are computed by bimachines
concepts/Lax132576/BimachineOfRational.lean · lax-132576
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 45 of the paper of lax-157538, Transducers
Theorem
Every rational function is computed by a bimachine: the implication (1) ⇒ (3) of Theorem B.2.3 of Transducers (Eilenberg), through the unambiguous automaton of (2). Given an unambiguous automaton whose accepting runs end with a single empty-input transition, the bimachine's prefix automaton computes the states reachable from an initial state on the prefix, its suffix automaton computes the first letter of the suffix and the states that can reach acceptance on the rest, and the output function reads off the output of the unique transition consuming the letter at the gap — or of the final empty-input transition at the last gap.
Lean source view on GitHub
| 1 | import Lax132576.RationalFunctions |
| 2 | import Lax132576.Bimachines |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Rational functions are computed by bimachines |
| 7 | type: theorem |
| 8 | --- |
| 9 | Every rational function is computed by a bimachine: the implication (1) ⇒ (3) |
| 10 | of Theorem B.2.3 of *Transducers* (Eilenberg), through the unambiguous |
| 11 | automaton of (2). Given an unambiguous automaton whose accepting runs end with |
| 12 | a single empty-input transition, the bimachine's prefix automaton computes the |
| 13 | states reachable from an initial state on the prefix, its suffix automaton |
| 14 | computes the first letter of the suffix and the states that can reach |
| 15 | acceptance on the rest, and the output function reads off the output of the |
| 16 | unique transition consuming the letter at the gap — or of the final |
| 17 | empty-input transition at the last gap. |
| 18 | |
| 19 | # Formalization notes |
| 20 | |
| 21 | Both alphabets are assumed finite, as the construction of the unambiguous |
| 22 | automaton needs. |
| 23 | -/ |
| 24 | |
| 25 | namespace Lax132576.BimachineOfRational |
| 26 | |
| 27 | open Lax132576.RationalFunctions Lax132576.Bimachines |
| 28 | |
| 29 | /-- A rational function is computed by a bimachine. -/ |
| 30 | axiom isBimachine_of_isRationalFun {A B : Type} [Finite A] [Finite B] |
| 31 | {f : List A → List B} (hf : IsRationalFun f) : IsBimachine f |
| 32 | |
| 33 | end Lax132576.BimachineOfRational |
| 34 |
Formalization notes
Both alphabets are assumed finite, as the construction of the unambiguous automaton needs.
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