Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the empty string)

Larry Evans wrote:


> Is there something like an identity element for the alternative
> operator, |. I'm thinking that in (x e) the space is the implicit
> multiplication operator with identity e, but I was wondering
> if there were something similar for the addition (i.e. | )
> operator. In addition, could this be what parsers are "in theory"
> using when the lexer's return # (as in yacc) to signal the end of input?


It is interesting (to me, at least) that Larry Evans (LE) should bring
up the matter of # as an end-of-input symbol.


When I first became interested in the type of right (or left) linear
derivation in which all productions save the last introduce one
terminal and the last introduces two terminals, I immediately thought
of interpreting the rightmost(leftmost) deepest terminal as a "STOP"
symbol. This is because any such right(left) linear derivation has an
automata-theoretic interpretation as a model of a finite-state
process, and it seemed natural to me to interpret the "extra" terminal
introduced by the last production in the derivation as a designated
"STOP" symbol, or "final state" symbol, just as the symbol to the left
of the rewrite arrow in the first production can be considered a
designated initial symbol of the grammar (or "initial-state" symbol.)


However, since I don't have even the slightest REAL knowledge of
finite-state automata theory nor its relation to formal language
theory, I hestitated to bring this up as a possible interpretation of
the deepest rightmost(leftmost) terminal in the class of derivations
in which I am interested.


If the language-theoretic/automata-theoretic community were to agree
that this is as legitimate and useful interpretation of the "extra"
rightmost (leftmost) and deepest terminal in the class of derivations
under consideration, then researchers now working under the auspices
of Cumulative Inquriy can say something quite interesting about how to
"double" such derivations in an intuitvely natural way which can be
expressed both algebraically and geometrically. In this regard, see
the "oDAG/POSET Problem" material and the "oDAGs invariant under a
half-turn" material at:


http://www.CumulativeInquiry.com/Problems


The upshot of the research in these two threads at the above URL is
that we can create the derivation tree of the derivation:


A -> a B
B -> b C
C -> c D
D -> d f


by starting with the derivation tree of the derivation:


C -> c D
D -> d f


and algebraically and/or geometrically "doubling" this derivation tree
in a straightforward manner by a symmetry operation suggested by the
work of Robert Jamison (Clemson) and William F. Mann (CI) on the
notion of "trees invariant under a half-turn".


This "doubling" of derivation trees, moreover, may shed some new
formal light on the applied problem of figuring out why certain
protein structures which do NOT appear to involve gene segment
duplication nonetheless converge on structures which DO appear to
involve gene segment duplication.

Return to the comp.compilers page.
Search the comp.compilers archives again.