A formal model for context-free languages augmented with reduplication
Walter J. Savitch · 1989
Family of Languages), which in some circles invests the class with a certain respectability. This is because such closure properties determine much of the character of well-known language classes, such as context-free languages and finite-state languages. (A Full AFL is any class of languages that contains at least one nonempty language and that is closed under union, A-free concatenation of two lan- guages, homomorphism, inverse homomorphism, and intersection with any finite-state language. See Salomaa 1973, for more details.) The notion of a finite-state transduction is important when analyzing pushdown machines. If a finite-state control reads a string of input while pushing some string onto the stack (without any popping), then the string in the stack is a finite-state transduction of the input string. Unfortunately, the concept of a finite-state transduction is fading out of the popular textbooks. We will therefore give a brief informal definition of the concept.