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

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

Date: 8 Aug 2004 09:48:35 -0700

I am grateful to William Elliot (WE) for his observation
concerning positive grammars with no empty productions.

When WE suggesting replacing the production rule Z -> z e
with the rule Z -> e to terminate the derivation, I realized
that I had not made my question sufficiently precise (although
interestingly, WE's suggestion goes to the heart of the matter.)

So, here is a more careful statement of the original question.

Suppose a grammar G (without e in its terminal alphabet Vt)
capable of producing one derivation charactrerizable by
the derivation tree T representable as the labelled bracketing:

[ a [ b [ z ]
 A B Z

G generates the regular language L with the one string 'abz'
and being right-linear, G belongs to the lowest level of
the Chomsky formallanguage hierarchy.

[NB:

My interpretation of the definition of a linear grammar is that
every one of its productions must introduce either one terminal
symbol OR one non-terminal and a terminal; further, the derivation
trees of derivations in linear grammars must be uniformly right-
branching or uniformly left-branching, i.e. in all productions
of a linear grammar that introduce a non-terminal, the non-terminal
must always follow ("right-branching") or always precede ("left-
branching") the terminal.

So, for example, a grammar capable of a single derivation whose
tree is characterizable by the labelled bracketing:

[ a [ [ Z ] b]
 A B Z

is not linear, but rather context-free, since there is a
production A -> a B (final non-terminal) and a production B -> Z b

If this is interpretation is incorrect in any respect, I would
be grateful for appropriate correction(s).

]

OK - now suppose we have a grammar G' with the empty string symbol
e in its terminal alphabet Vt. Suppose, moreover, that G'
is capable of one derivation with a tree characterizable by
the bracketing:

[ a [ b [ z e ]
 A B Z

My understanding of the definition of linear grammar is that
this grammar G' cannot be considered linear because it contains
one production Z -> z e which does NOT introduce either one
just one terminal nor just one terminal and just one non-terminal.

But if G' is not linear for this reason, then must it be
considered context-free (albeit a very trivial type of context-free ?)

So, perhaps the correct way to ask my question is as follows:

Is G' linear (at the lowest-level of the Chomsky hierarchy) or
context-free (one level up in this hierarchy?)

Again, I understand that this question may have no answer because
it is itself not a "well-formed" question; but if it is not
"well-formed", I would very much appreciate it if someone would
tell me why (no sarcasm intended!)

Relevant Pages

  • "Z -> z versus Z -> z e" - sole thread for future discussion/postings
    ... When WE suggesting replacing the production rule Z -> z e ... with the rule Z -> e to terminate the derivation, ... Suppose a grammar G ... of a linear grammar that introduce a non-terminal, ...
    (sci.math)
  • "Z -> z versus Z -> z e" - sole thread for future discussion/postings
    ... When WE suggesting replacing the production rule Z -> z e ... with the rule Z -> e to terminate the derivation, ... Suppose a grammar G ... of a linear grammar that introduce a non-terminal, ...
    (comp.theory)
  • Single production vs recursive grammar structure
    ... The InstanceOfExpressionproduction and the other ones directly ... void InstanceOfExpression(): ... RelationalExpression() [... ... grammar, ...
    (comp.compilers.tools.javacc)
  • Re: C# 2.0 language grammar
    ... While I agree that it probably boiled down to an arbitrary decision, ... namespace-type-name production is used is in the context of a using-directive ... particular productions are used, and according to the grammar it is, then I ... question the logic in constructing the namespace-name and namespace-type-name ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Extended context-free grammar
    ... it doesn't look like it is guaranteed to terminate. ... So the length of this prefix sequence is bounded, ... isn't going to produce a concrete word (note that the grammar given ...
    (comp.theory)