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.
Contents
AFA Schema
An AFA Schema is an ordered 4-tuple
-
Γ andI are nonempty abstract sets. -
f is the write function:f : Γ ∗ × I → Γ ∗ ∪ { ∅ } (N.B. * is the Kleene star operation). -
g is the read function, a mapping fromΓ ∗ Γ ∗ g ( ϵ ) = { ϵ } andϵ is ing ( γ ) if and only ifγ = ϵ . (N.B.ϵ is the empty word). - For each
γ ing ( Γ ∗ ) , there is an element1 γ I satisfyingf ( γ ′ , 1 γ ) = γ ′ γ ′ γ is ing ( γ ′ ) . - For each u in I, there exists a finite set
Γ u Γ , such that ifΓ 1 Γ ,γ is inΓ 1 ∗ f ( γ , u ) ≠ ∅ , thenf ( γ , u ) is in( Γ 1 ∪ Γ u ) ∗
Abstract family of acceptors
An abstract family of acceptors (AFA) is an ordered pair
-
Ω is an ordered 6-tuple (K ,Σ ,Γ ,I ,f ,g ), where- (
Γ ,I ,f ,g ) is an AFA schema; and -
K andΣ are infinite abstract sets
- (
-
D is the family of all acceptorsD = (K 1 Σ 1 δ ,q 0 F ), where-
K 1 Σ 1 K , andΣ respectively,F ⊆K 1 q 0 K 1 -
δ (called the transition function) is a mapping fromK 1 × ( Σ 1 ∪ { ϵ } ) × g ( Γ ∗ ) into the finite subsets ofK 1 × I such that the setG D = { γ |δ ( q , a , γ ) ≠ ø for someq anda } is finite.
-
For a given acceptor, let
Let
Define
AFA Schema
An AFA schema defines a store or memory with read and write function. The symbols in
Abstract family of acceptors
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
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
The main result from AFL theory is that a family of languages
Origins
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.