Multitape AFA
Seymour Ginsburg, Sheila A. Greibach · Journal of the ACM · 1972
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 substitution operations to AFL (abstract families of languages).In particular, if ~ and ~2 are multitape 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 substituting the AFL defined by ~2 into the AFL defined by ~D~ .