Contents

Abstract family of acceptors

AFA Schema[edit]

AnAFA Schema is an ordered 4-tuple ${\displaystyle (\Gamma ,I,f,g)}$, where

1. ${\displaystyle \Gamma }$ and ${\displaystyle I}$ are nonempty abstract sets.
2. ${\displaystyle f}$ is the write function: ${\displaystyle f:\Gamma ^{*}\times I\rightarrow \Gamma ^{*}\cup \{\emptyset \}}$ (N.B. * is the Kleene star operation).
3. ${\displaystyle g}$ is the read function, a mapping from ${\displaystyle \Gamma ^{*}}$ into the finite subsets of ${\displaystyle \Gamma ^{*}}$, such that ${\displaystyle g(\epsilon )=\{\epsilon \}}$ and ${\displaystyle \epsilon }$ is in ${\displaystyle g(\gamma )}$ if and only if ${\displaystyle \gamma =\epsilon }$. (N.B. ${\displaystyle \epsilon }$ is the empty word).
4. For each ${\displaystyle \gamma }$in${\displaystyle g(\Gamma ^{*})}$, there is an element ${\displaystyle 1_{\gamma }}$in${\displaystyle I}$ satisfying ${\displaystyle f(\gamma ',1_{\gamma })=\gamma '}$ for all ${\displaystyle \gamma '}$ such that ${\displaystyle \gamma }$ is in ${\displaystyle g(\gamma ')}$.
5. For each uinI, there exists a finite set ${\displaystyle \Gamma _{u}}$ ⊆ ${\displaystyle \Gamma }$, such that if ${\displaystyle \Gamma _{1}}$ ⊆ ${\displaystyle \Gamma }$, ${\displaystyle \gamma }$ is in ${\displaystyle \Gamma _{1}^{*}}$, and ${\displaystyle f(\gamma ,u)\neq \emptyset }$, then ${\displaystyle f(\gamma ,u)}$ is in ${\displaystyle (\Gamma _{1}\cup \Gamma _{u})^{*}}$.

Abstract family of acceptors[edit]

Anabstract family of acceptors (AFA) is an ordered pair ${\displaystyle (\Omega ,{\mathcal {D}})}$ such that:

1. ${\displaystyle \Omega }$ is an ordered 6-tuple (${\displaystyle K}$, ${\displaystyle \Sigma }$, ${\displaystyle \Gamma }$, ${\displaystyle I}$, ${\displaystyle f}$, ${\displaystyle g}$), where
   1. (${\displaystyle \Gamma }$, ${\displaystyle I}$, ${\displaystyle f}$, ${\displaystyle g}$) is an AFA schema; and
   2. ${\displaystyle K}$ and ${\displaystyle \Sigma }$ are infinite abstract sets
2. ${\displaystyle {\mathcal {D}}}$ is the family of all acceptors ${\displaystyle D}$ = (${\displaystyle K_{1}}$, ${\displaystyle \Sigma _{1}}$, ${\displaystyle \delta }$, ${\displaystyle q_{0}}$, ${\displaystyle F}$), where
   1. ${\displaystyle K_{1}}$ and ${\displaystyle \Sigma _{1}}$ are finite subsets of ${\displaystyle K}$, and ${\displaystyle \Sigma }$ respectively, ${\displaystyle F}$ ⊆ ${\displaystyle K_{1}}$, and ${\displaystyle q_{0}}$ is in ${\displaystyle K_{1}}$; and
   2. ${\displaystyle \delta }$ (called the transition function) is a mapping from ${\displaystyle K_{1}\times (\Sigma _{1}\cup \{\epsilon \})\times g(\Gamma ^{*})}$ into the finite subsets of ${\displaystyle K_{1}\times I}$ such that the set ${\displaystyle G_{D}=\{\gamma }$ | ${\displaystyle \delta (q,a,\gamma )}$ ≠ ø for some ${\displaystyle q}$ and ${\displaystyle a\}}$ is finite.

For a given acceptor, let ${\displaystyle \vdash }$ be the relation on ${\displaystyle K_{1}\times \Sigma _{1}^{*}\times \Gamma ^{*}}$ defined by: For ${\displaystyle a}$in${\displaystyle \Sigma _{1}\cup \{\epsilon \}}$, ${\displaystyle (p,aw,\gamma )\vdash (p',w,\gamma ')}$ if there exists a ${\displaystyle {\overline {\gamma }}}$ and ${\displaystyle u}$ such that ${\displaystyle {\overline {\gamma }}}$ is in ${\displaystyle g(\gamma )}$, ${\displaystyle (p',u)}$ is in ${\displaystyle \delta (p,a,{\overline {\gamma }})}$ and ${\displaystyle f(\gamma ,u)=\gamma '}$. Let ${\displaystyle \vdash ^{*}}$ denote the transitive closureof${\displaystyle \vdash }$.

Let ${\displaystyle (\Omega ,{\mathcal {D}})}$ be an AFA and ${\displaystyle D}$ = (${\displaystyle K_{1}}$, ${\displaystyle \Sigma _{1}}$, ${\displaystyle \delta }$, ${\displaystyle q_{0}}$, ${\displaystyle F}$) be in ${\displaystyle D}$. Define ${\displaystyle L($D)} to be the set ${\displaystyle \{w\in \Sigma _{1}^{*}|\exists q\in F.(q_{0},w,\epsilon )\vdash ^{*}(q,\epsilon ,\epsilon )\}}$. For each subset ${\displaystyle {\mathcal {E}}}$of${\displaystyle {\mathcal {D}}}$, let ${\displaystyle {\mathcal {L}}({\mathcal {E}})=\{L($D)|D\in {\mathcal {E}}\}} .

Define ${\displaystyle L_{f}($D)} to be the set ${\displaystyle \{w\in \Sigma _{1}^{*}|\exists (q\in F)\exists (\gamma \in \Gamma ^{*}).(q_{0},w,\epsilon )\vdash ^{*}(q,\epsilon ,\gamma )\}}$. For each subset ${\displaystyle {\mathcal {E}}}$of${\displaystyle {\mathcal {D}}}$, let ${\displaystyle {\mathcal {L}}_{f}({\mathcal {E}})=\{L_{f}($D)|D\in {\mathcal {E}}\}} .

Informal discussion[edit]

AFA Schema[edit]

An AFA schema defines a store or memory with read and write function. The symbols in ${\displaystyle \Gamma }$ are called storage symbols and the symbols in ${\displaystyle I}$ are called instructions. The write function ${\displaystyle f}$ returns a new storage state given the current storage state and an instruction. The read function ${\displaystyle 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[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 ${\displaystyle \vdash }$ relation defines one step in the operation of an acceptor. ${\displaystyle L_{f}($D)} is the set of words accepted by acceptor ${\displaystyle D}$ by having the acceptor enter an accepting state. ${\displaystyle L($D)} is the set of words accepted by acceptor ${\displaystyle 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[edit]

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

Origins[edit]

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

References[edit]