Mappings of languages by two-tape devices
- 1 July 1965
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 12 (3) , 423-434
- https://doi.org/10.1145/321281.321294
Abstract
Several devices with two input lines and one output line are introduced. These devices are viewed as transformations which operate on pairs of (ALGOL-like) languages. Among the results proved are the following: (i) a pair consisting of a language and a regular set is transformed into a language; (ii) let ( V, W ) be a pair consisting of a language and a regular set. Then the set of those words w 1 , for which there exists a word w 2 in V so that ( w 1 , w 2 ) is mapped into W , is a language.Keywords
This publication has 3 references indexed in Scilit:
- Quotients of Context-Free LanguagesJournal of the ACM, 1963
- Operations Which Preserve Definability in LanguagesJournal of the ACM, 1963
- Two Families of Languages Related to ALGOLJournal of the ACM, 1962