APPENDIX A
FINITE-STATE TRANSDUCERS
Finite accepters play a central role in the study of formal languages, but in other areas, such as digital design, transducers are more important. While we cannot go into this subject matter in any depth, we can at least outline the main ideas. A full treatment, with many examples of practical applications, can be found in Kohavi and Jha, 2010.
A.1 A GENERAL FRAMEWORK
Finite-state transducers (fst’s) have many things in common with finite accepters. An fst has a finite set Q of internal states and operates in a discrete time frame with transitions from one state to another made in the interval between two instances tn and tn+1. An fst is associated with a read-once-only input file that contains a string from ...
Get An Introduction to Formal Languages and Automata, 6th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
