Re: "Z -> z versus Z -> z e" - sole thread for future discussion/postings

From: David Halitsky (dhalitsky_at_cumulativeinquiry.com)
Date: 08/09/04 

Date: 9 Aug 2004 07:48:06 -0700

OK - now that I'm sure that I understand William Elliot (WE)'s
last messae to this thread, I would like to respond to his
claim that nothing of any great import follows from the
fact that the grammar G with productions:

A -> a B
B -> b Z
Z -> z e (where e is the designated emoty string symbol)

is a context-free grammar of a regular language, i.e. not
a linear grammar of a regular language.

(I assume here that if anything of reasonable import
can be shown to follow from this observation, then
WE would agree that the discussion is not over a
'quibble.' Also, please note that I myself am not
sure whether there is a 'quibble' involved here or not,
and will therefore be grateful if WE will maintain
his willingness to discuss the matter a little bit
further.)

At the URL:

//http:www.CumulativeInquiry.com/Problems

work by several mathematicians is accumulating concerning
the properties of certain "ordered" DAGs (directed acyclic
graphs) in relation to posets of dimension 2 and also
in relation to certain simple symmetries which arise when
considering the space Zm x Zm in the surface of a torus,
or equivalently, in a tiling of the plane.

One outcome of this work on symmetries in Zm X Zm is the
fact that the following derivation trees (when considered
as "ordered DAGS" in the sense defined at the above URL)
are an undeniable "natural class":

the derivation tree generated from the productions:

A -> a B
B -> b Z
Z -> z e (e the designated empty symbol

the derivation tree generated from the productions:

A -> a B c
B -> d C f
C -> g h i

the derivation tree generated from the productions:

A -> B C
B -> b
C -> c

the derivation tree generated from the production:

A -> a B
B -> C b
C -> c D
D -> d e (e the empty string symbol)

(Note that the mathematically definable "natural class"
involved here contains MANY other types of context-free
grammars.)

So the question is whether the existence of this natural
class can shed any new light on the much-discussed
question of precisely how processes modellable by
linear grammars do and do not differ from processes
modellable by non-linear context-free grammars.

I do not claim to have an answer to this question at
present; I am simply arguing that it is too early
to decide whether it is "quibbling" to observe
that one can define context-free grammars of regular
languages which fall into a "natural class" of potential
formal and empirical interest, once one permits introduction
of the empty string symbol into Vt.

Relevant Pages

  • Re: "Z -> z versus Z -> z e" - sole thread for future discussion/postings
    ... the derivation tree generated from the productions: ... (Note that the mathematically definable "natural class" ... linear grammars do and do not differ from processes ...
    (comp.theory)
  • Re: "Z -> z versus Z -> z e" - sole thread for future discussion/postings
    ... the derivation tree generated from the productions: ... (Note that the mathematically definable "natural class" ... linear grammars do and do not differ from processes ...
    (sci.logic)
  • Earley Parser
    ... - processes ALL context free grammars (including epsilon productions, ... Parsing Techniques - A Practical Guide ...
    (comp.compilers)
  • Re: CYK & Context-Free Expressions
    ... extensions of) Chomsky normal form grammars. ... the current state of the art in parsing theory is ... is something that applies in reference to context-free grammars. ... the grammar induces upon a text a derivation tree. ...
    (comp.theory)
  • Re: Error reporting, was Infinite look ahead required by C++?
    ... productions possible and it is reasonable to give messages of the form ... characteristics to be expected of general LRgrammars. ... The problem isn't the parsing technology, but the language itself. ... gone quite some distance past the real problem, ...
    (comp.compilers)