Abstract family of acceptors

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. Seymour Ginsburg, "Algebraic and automata theoretic properties of formal languages", North-Holland, 1975, ISBN 0 7204 2506 9.]

Formal definitions

AFA Schema

An "AFA Schema" is an ordered 4-tuple (Gamma, I, f, g), where
# Gamma and I are nonempty abstract sets.
# f is the "write" function: f : Gamma^* imes I ightarrow Gamma^* cup {empty} (N.B. * is the Kleene star operation).
# g is the "read" function, a mapping from Gamma^* into the finite subsets of Gamma^*, such that g (epsilon) = { epsilon } and epsilon is in g(gamma) if and only if gamma = epsilon. (N.B. epsilon is the empty word).
# For each gamma in g(Gamma^*), there is an element 1_gamma in I satisfying f(gamma', 1_gamma) = gamma' for all gamma' such that gamma is in g(gamma').
# For each "u" in "I", there exists a finite set Gamma_uGamma, such that if Gamma_1Gamma, gamma is in Gamma_1^*, and f(gamma,u) e empty, then f(gamma,u) is in (Gamma_1 cup Gamma_u)^*.

Abstract family of acceptors

An "abstract family of acceptors (AFA)" is an ordered pair (Omega, mathcal{D}) such that:
#Omega is an ordered 6-tuple (K, Sigma, Gamma, I, f, g), where
## (Gamma, I, f, g) is an AFA schema; and
## K and Sigma are infinite abstract sets
#mathcal{D} is the family of all acceptors D = (K_1, Sigma_1, delta, q_0, F), where
##K_1 and Sigma_1 are finite subsets of K, and Sigma respectively, FK_1, and q_0 is in K_1; and
##delta (called the "transition" function) is a mapping from K_1 imes (Sigma_1 cup { epsilon }) imes g(Gamma^*) into the finite subsets of K_1 imes I such that the set G_D = { gamma | delta(q,a,gamma) ≠ ø for some q and a } is finite.

For a given acceptor, let vdash be the relation on K_1 imes Sigma_1^* imes Gamma^* defined by: For a in Sigma_1 cup { epsilon }, (p,aw,gamma) vdash (p',w,gamma') if there exists a overline{gamma} and u such that overline{gamma} is in g(gamma), (p',u) is in delta(p,a,overline{gamma}) and f(gamma,u)=gamma'. Let vdash^* denote the transitive closure of vdash.

Let (Omega, mathcal{D}) be an AFA and D = (K_1, Sigma_1, delta, q_0, F) be in D. Define L(D) to be the set { w in Sigma_1^* | exists q in F . (q_0,w,epsilon) vdash^* (q,epsilon,epsilon)}. For each subset mathcal{E} of mathcal{D}, let mathcal{L}(mathcal{E}) = {L(D) | D in mathcal{E} }.

Define L_f(D) to be the set { w in Sigma_1^* | exists(q in F)exists(gamma in Gamma^*) . (q_0,w,epsilon) vdash^* (q,epsilon,gamma)}. For each subset mathcal{E} of mathcal{D}, let mathcal{L}_f(mathcal{E}) = {L_f(D) | D in mathcal{E} }.

Informal discussion

AFA Schema

An AFA schema defines a store or memory with read and write function. The symbols in Gamma are called "storage symbols" and the symbols in I are called "instructions". The write function f returns a new storage state given the current storage state and an instruction. The read function g 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

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 vdash relation defines one step in the operation of an acceptor. L_f(D) is the set of words accepted by acceptor D by having the acceptor enter an accepting state. L(D) is the set of words accepted by acceptor D 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

The main result from AFL theory is that a family of languages mathcal{L} is a full AFL if and only if mathcal{L} = mathcal{L}(mathcal{D}) for some AFA (Omega, mathcal{D}). Equally important is the result that mathcal{L} is a full semi-AFL if and only if mathcal{L} = mathcal{L}_f(mathcal{D}) for some AFA (Omega, mathcal{D}).


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. [ [http://www.worldcat.org/oclc/2891921 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.]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • Sheila Greibach — (1939 ) is a researcher in formal languages, automata, compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles.She worked with Seymour Ginsburg… …   Wikipedia

  • automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… …   Universalium

  • Alcohol dehydrogenase — Crystallographic structure of the homodimer of human ADH5.[1] Identifiers …   Wikipedia

  • Health effects of tobacco — Part of a series on Tobacco …   Wikipedia

  • Graphene — is a one atom thick planar sheet of sp2 bonded carbon atoms that are densely packed in a honeycomb crystal lattice. It can be viewed as an atomic scale chicken wire made of carbon atoms and their bonds. The name comes from GRAPHITE + ENE;… …   Wikipedia

  • Dihydroorotate dehydrogenase — Dihydroorotate oxidase Identifiers EC number CAS number 9029 03 2 …   Wikipedia

  • CCR5 receptor antagonists — are a class of small molecules that antagonize the CCR5 receptor. The C C motif chemokine receptor CCR5 is involved in the HIV entry process. Hence antagonists of this receptor have potential therapeutic applications in the treatment of HIV… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”