Multitape AFA

Publisher Website
Google Scholar
Abstract
Device representations, via multitape AFA (abstract families of acceptors), are given for the families of languages which result from applying the wedge (A) m)d the substitu- tion operations to AFL (abstract families of languages). In particular, if ~ and ~2 are multi- tape AFA (i.e. certain families of multistorage tape acceptors), then 5)~ A ~2 is defined as the family of multitape acceptors which results when the tapes of ~ and ~2 are coalesced, with the ~-tapes preceding those in ~2 . It is shown that the smallest full AFL containing 2(~) A 2 (~D2) = {L~ N L2 ILi in2 (~Di) } is ,12 (~ h~:). For each multitape AFAr, aset ~.v of "nested" multitape acceptors is defined. It is shown that if ~ and ~2 are single-tape AFA, then the family of languages obtained from (~ A ~2) N is the family of langnages obtained by substitut- ing the AFL defined by ~2 into the AFL defined by ~D~ .

This publication has 18 references indexed in Scilit: