Abstract families of languages
- 1 January 1967
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 128-139
- https://doi.org/10.1109/focs.1967.3
Abstract
The notion of an abstract family of languages (AFL) as a family of sets of words satisfying certain properties common to many types of formal languages is introduced. Operations preserving AFL are then considered. The concept of an abstract family of acceptors (AFA) is also introduced and shown to give rise to an AFL. A necessary and sufficient condition on an AFL is presented in order that the AFL come from some AFA. Finally, abstract families of transducers (AFA with output) are discussed.Keywords
This publication has 9 references indexed in Scilit:
- One-way stack automataJournal of the ACM, 1967
- Stack automata and compilingJournal of the ACM, 1967
- Mappings which preserve context sensitive languagesInformation and Control, 1966
- Finite-Turn Pushdown AutomataSIAM Journal on Control, 1966
- Preservation of languages by transducersInformation and Control, 1966
- Classes of languages and linear-bounded automataInformation and Control, 1964
- Three theorems on phrase structure grammars of type 1Information and Control, 1963
- Decision problems of finite automata design and related arithmeticsTransactions of the American Mathematical Society, 1961
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959