🚀 go-pugleaf

I have defined a class of recognizers, systems of automata, that
recognize the context free languages.  I believe that they should
be defined somewhere in the literature.  However, I have tracked down
a number of leads and I am unable to find a similar definition.  I
would appreciate any references, leads, or comments.

Symbol key:
   U  -  set union
  _x  - subscripted x

  ^x  - superscript x
  |-  - moves

Given the usual definition of a nondeterministic NFA as a 5-tuple,
M=(Q, SIGMA, delta, q0, F), where:
  Q is a finite set of states.
  SIGMA is a finite set of input symbols (the input alphabet).
  delta is the state transition function that maps (Q X (SIGMA U e))
    to subsets of Q.
  q0 is a state in Q: the start state of M.
  F is a subset of Q: the final (or accepting) states of M.

Then a system of automata is defined to be a 6-tuple,
S=(M, N, SIGMA, GAMMA, DELTA, M_0)  where:

1. M is a finite set of NFAs, M_i, i=1...n.  We denote the components
   of each M_i as Q_i, SIGMA_i, delta_i, q0_i, and F_i.  Each SIGMA_i
   is a subset of (SIGMA U N).

2. N is a set of unique symbols (names) for M_i, i=1..n, such that
   N intersect SIGMA is empty.  We denote the symbol for M_i as N_i.

3. SIGMA is the input alphabet for S.

4. GAMMA is the finite set of ordered pairs, (M_i,q), for i=1...n and
   q in Q_i.

5. DELTA is a mapping from (GAMMA X GAMMA^* X (N U SIGMA U e)) to
   (GAMMA X GAMMA^*), and is defined by delta_i, i=1...n as follows:
   For each delta_i, and for all delta_i(q,a)-->p and alfa in GAMMA^*:

   A. if a is in (SIGMA U e),
      then DELTA((M_i,q),alfa,a)-->((M_i,p),alfa).
  
   B. if a=N_j for some j=1...n,
      then DELTA((M_i,q),alfa,a)-->((M_j,q0_j),(M_i,p)alfa)
      and for each final state f in F_j
      DELTA((M_j,f),(M_i,p)alfa,e)-->DELTA((M_i,p),alfa)

6. M_0 is the top level (or start) automaton, where M_0 is some M_i,
   i=1...n:  q_0=q0_i is the start state of S and F_0=F_i is the set
   of the final states of S.

A configuration of S is a triple ((M_i,q),alfa,w), where (M_i,q)
represents the current state of the finite control, (M_i,q)alfa in
GAMMA^+ represents the open NFA's and their respective current states,
and w in SIGMA^* represents the remaining input.  An initial
configuration of S is C_0=((M_0,q_0),e,w), for some w in SIGMA^*, and
the final (accepting) configurations are C_f=((M_0,f),e,e) for all f
in F_0. An input string w in SIGMA^* is accepted by S if C_0 |-^* C_f,
for some f.  The language recognized by S is denoted by L(S).

Moves are defined by DELTA as described above.  For each delta_i
and for all delta_i(q,a)-->p, alfa in GAMMA^*, and x in SIGMA:
.
   A. if a is in (SIGMA U e),
      then ((M_i,q),alfa,ax) |- ((M_i,p),alfa,x).
  
   B. if a=N_j for some j=1...n,
      then ((M_i,q),alfa,x) |- ((M_j,q0_j),(M_i,p)alfa,x)
      and for each final state f in F_j,
      ((M_j,f),(M_i,p)alfa,x) |- ((M_i,p),alfa,x)
.
The moves described in A are local moves and the moves in B are
pushdown list moves.  There are local e-moves and all pushdown list
moves are e-moves.
.
I appreciate your time and interest.  Send any responses to:
  matzen@a.cs.okstate.edu
.
Thanks,
Rick Matzen
Computer Science Department
Oklahoma State University