home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2795 < prev    next >
Encoding:
Text File  |  1993-01-06  |  3.6 KB  |  94 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!paladin.american.edu!howland.reston.ans.net!usc!cs.utexas.edu!convex!constellation!a.cs.okstate.edu!matzen
  3. From: matzen@a.cs.okstate.edu (MATZEN RICHARD WAL)
  4. Subject: Systems of automata: an alternative to CFGs
  5. Message-ID: <1993Jan6.010102.14054@a.cs.okstate.edu>
  6. Organization: Oklahoma State University, Computer Science, Stillwater
  7. Date: Wed, 6 Jan 93 01:01:02 GMT
  8. Lines: 84
  9.  
  10. I have defined a class of recognizers, systems of automata, that
  11. recognize the context free languages.  I believe that they should
  12. be defined somewhere in the literature.  However, I have tracked down
  13. a number of leads and I am unable to find a similar definition.  I
  14. would appreciate any references, leads, or comments.
  15.  
  16. Symbol key:
  17.    U  -  set union
  18.   _x  - subscripted x
  19.  
  20.   ^x  - superscript x
  21.   |-  - moves
  22.  
  23. Given the usual definition of a nondeterministic NFA as a 5-tuple,
  24. M=(Q, SIGMA, delta, q0, F), where:
  25.   Q is a finite set of states.
  26.   SIGMA is a finite set of input symbols (the input alphabet).
  27.   delta is the state transition function that maps (Q X (SIGMA U e))
  28.     to subsets of Q.
  29.   q0 is a state in Q: the start state of M.
  30.   F is a subset of Q: the final (or accepting) states of M.
  31.  
  32. Then a system of automata is defined to be a 6-tuple,
  33. S=(M, N, SIGMA, GAMMA, DELTA, M_0)  where:
  34.  
  35. 1. M is a finite set of NFAs, M_i, i=1...n.  We denote the components
  36.    of each M_i as Q_i, SIGMA_i, delta_i, q0_i, and F_i.  Each SIGMA_i
  37.    is a subset of (SIGMA U N).
  38.  
  39. 2. N is a set of unique symbols (names) for M_i, i=1..n, such that
  40.    N intersect SIGMA is empty.  We denote the symbol for M_i as N_i.
  41.  
  42. 3. SIGMA is the input alphabet for S.
  43.  
  44. 4. GAMMA is the finite set of ordered pairs, (M_i,q), for i=1...n and
  45.    q in Q_i.
  46.  
  47. 5. DELTA is a mapping from (GAMMA X GAMMA^* X (N U SIGMA U e)) to
  48.    (GAMMA X GAMMA^*), and is defined by delta_i, i=1...n as follows:
  49.    For each delta_i, and for all delta_i(q,a)-->p and alfa in GAMMA^*:
  50.  
  51.    A. if a is in (SIGMA U e),
  52.       then DELTA((M_i,q),alfa,a)-->((M_i,p),alfa).
  53.   
  54.    B. if a=N_j for some j=1...n,
  55.       then DELTA((M_i,q),alfa,a)-->((M_j,q0_j),(M_i,p)alfa)
  56.       and for each final state f in F_j
  57.       DELTA((M_j,f),(M_i,p)alfa,e)-->DELTA((M_i,p),alfa)
  58.  
  59. 6. M_0 is the top level (or start) automaton, where M_0 is some M_i,
  60.    i=1...n:  q_0=q0_i is the start state of S and F_0=F_i is the set
  61.    of the final states of S.
  62.  
  63. A configuration of S is a triple ((M_i,q),alfa,w), where (M_i,q)
  64. represents the current state of the finite control, (M_i,q)alfa in
  65. GAMMA^+ represents the open NFA's and their respective current states,
  66. and w in SIGMA^* represents the remaining input.  An initial
  67. configuration of S is C_0=((M_0,q_0),e,w), for some w in SIGMA^*, and
  68. the final (accepting) configurations are C_f=((M_0,f),e,e) for all f
  69. in F_0. An input string w in SIGMA^* is accepted by S if C_0 |-^* C_f,
  70. for some f.  The language recognized by S is denoted by L(S).
  71.  
  72. Moves are defined by DELTA as described above.  For each delta_i
  73. and for all delta_i(q,a)-->p, alfa in GAMMA^*, and x in SIGMA:
  74. .
  75.    A. if a is in (SIGMA U e),
  76.       then ((M_i,q),alfa,ax) |- ((M_i,p),alfa,x).
  77.   
  78.    B. if a=N_j for some j=1...n,
  79.       then ((M_i,q),alfa,x) |- ((M_j,q0_j),(M_i,p)alfa,x)
  80.       and for each final state f in F_j,
  81.       ((M_j,f),(M_i,p)alfa,x) |- ((M_i,p),alfa,x)
  82. .
  83. The moves described in A are local moves and the moves in B are
  84. pushdown list moves.  There are local e-moves and all pushdown list
  85. moves are e-moves.
  86. .
  87. I appreciate your time and interest.  Send any responses to:
  88.   matzen@a.cs.okstate.edu
  89. .
  90. Thanks,
  91. Rick Matzen
  92. Computer Science Department
  93. Oklahoma State University
  94.