Abstract family of acceptors

An abstract family of acceptors (AFA) is a grouping of generalized acceptors. Informally, an acceptor is a device with a finite state control, a finite number of input symbols, and an internal store with a read and write function. Each acceptor has a start state and a set of accepting states. The device reads a sequence of symbols, transitioning from state to state for each input symbol. If the device ends in an accepting state, the device is said to accept the sequence of symbols. A family of acceptors is a set of acceptors with the same type of internal store. The study of AFA is part of AFL (abstract families of languages) theory.[1]

Formal definitions

edit

AFA Schema

edit

An AFA Schema is an ordered 4-tuple  , where

  1.   and   are nonempty abstract sets.
  2.   is the write function:   (N.B. * is the Kleene star operation).
  3.   is the read function, a mapping from   into the finite subsets of  , such that   and   is in   if and only if  . (N.B.   is the empty word).
  4. For each   in  , there is an element   in   satisfying   for all   such that   is in  .
  5. For each u in I, there exists a finite set   , such that if   ,   is in  , and  , then   is in  .

Abstract family of acceptors

edit

An abstract family of acceptors (AFA) is an ordered pair   such that:

  1.   is an ordered 6-tuple ( ,  ,  ,  ,  ,  ), where
    1. ( ,  ,  ,  ) is an AFA schema; and
    2.   and   are infinite abstract sets
  2.   is the family of all acceptors   = ( ,  ,  ,  ,  ), where
    1.   and   are finite subsets of  , and   respectively,   , and   is in  ; and
    2.   (called the transition function) is a mapping from   into the finite subsets of   such that the set   |   ≠ ø for some   and   is finite.

For a given acceptor, let   be the relation on   defined by: For   in  ,   if there exists a   and   such that   is in  ,   is in   and  . Let   denote the transitive closure of  .

Let   be an AFA and   = ( ,  ,  ,  ,  ) be in  . Define   to be the set  . For each subset   of  , let  .

Define   to be the set  . For each subset   of  , let  .

Informal discussion

edit

AFA Schema

edit

An AFA schema defines a store or memory with read and write function. The symbols in   are called storage symbols and the symbols in   are called instructions. The write function   returns a new storage state given the current storage state and an instruction. The read function   returns the current state of memory. Condition (3) insures the empty storage configuration is distinct from other configurations. Condition (4) requires there be an identity instruction that allows the state of memory to remain unchanged while the acceptor changes state or advances the input. Condition (5) assures that the set of storage symbols for any given acceptor is finite.

Abstract family of acceptors

edit

An AFA is the set of all acceptors over a given pair of state and input alphabets which have the same storage mechanism defined by a given AFA schema. The   relation defines one step in the operation of an acceptor.   is the set of words accepted by acceptor   by having the acceptor enter an accepting state.   is the set of words accepted by acceptor   by having the acceptor simultaneously enter an accepting state and having an empty storage.

The abstract acceptors defined by AFA are generalizations of other types of acceptors (e.g. finite state automata, pushdown automata, etc.). They have a finite state control like other automata, but their internal storage may vary widely from the stacks and tapes used in classical automata.

Results from AFL theory

edit

The main result from AFL theory is that a family of languages   is a full AFL if and only if   for some AFA  . Equally important is the result that   is a full semi-AFL if and only if   for some AFA  .

Origins

edit

Seymour Ginsburg of the University of Southern California and Sheila Greibach of Harvard University first presented their AFL theory paper at the IEEE Eighth Annual Symposium on Switching and Automata Theory in 1967.[2]

References

edit
  1. ^ Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0-7204-2506-9.
  2. ^ IEEE conference record of 1967 Eighth Annual Symposium on Switching and Automata Theory : papers presented at the Eighth Annual Symposium, University of Texas, October 18–20, 1967.