Book contents
- Frontmatter
- Contents
- Preface
- Part I Formal Background
- 1 Formal Preliminaries
- 2 Monoidal Finite-State Automata
- 3 Classical Finite-State Automata and Regular Languages
- 4 Monoidal Multi-Tape Automata and Finite-State Transducers
- 5 Deterministic Transducers
- 6 Bimachines
- Part II From Theory to Practice
- References
- Index
5 - Deterministic Transducers
from Part I - Formal Background
Published online by Cambridge University Press: 29 July 2019
- Frontmatter
- Contents
- Preface
- Part I Formal Background
- 1 Formal Preliminaries
- 2 Monoidal Finite-State Automata
- 3 Classical Finite-State Automata and Regular Languages
- 4 Monoidal Multi-Tape Automata and Finite-State Transducers
- 5 Deterministic Transducers
- 6 Bimachines
- Part II From Theory to Practice
- References
- Index
Summary
In this chapter we explore deterministic finite-state transducers. Obviously, it only makes sense to ask for determinism if we restrict attention to transducers with a functional input-output behaviour. In this chapter we focus on transducers that are deterministic on the input tape (called sequential or subsquential transducers). We shall see that only a proper subset of all regular string functions can be represented by this kind of device and we describe a decision procedure for testing whether a functional transducer can be determinized. Further we present a subsequential transducer minimization procedure based on theMyhill–Nerode relation for string functions.
Keywords
- Type
- Chapter
- Information
- Finite-State TechniquesAutomata, Transducers and Bimachines, pp. 94 - 137Publisher: Cambridge University PressPrint publication year: 2019