O'Reilly logo

An Introduction to Formal Languages and Automata, 6th Edition by Linz

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required