W3C home > Mailing lists > Public > xml-editor@w3.org > July to September 1999

Quibble on "deterministic"

From: Rick Jelliffe <ricko@gate.sinica.edu.tw>
Date: Fri, 3 Sep 1999 19:33:14 +0800
Message-ID: <007401bef600$1c658240$8d066d8c@sinica.edu.tw>
To: <xml-editor@w3.org>
Here is a quibble on Appendix E.

The term "ambiguous" is a correct computer science term. A grammar is
ambiguous; an automaton is "deterministic".  (Of course, because grammars
and automata are different expressions of the same thing, a term properly
belonging to one can be used improperly with the other.)

A content model is clearly a grammar and not an automaton.  So Appendix E
should be changed to use "ambiguous".  On the other hand, "deterministic" is
the favoured term for algorithms.

Apart from this usage in the literature, "deterministic" as a term derives
from analyses of whether an automaton can finish in deterministic time or
space;  so it seems that there is a reason for there to be two separate
terms.

There is a parenthetical comment that suggests that ISO 8879 is incorrect or
strange in using "ambiguous". This should be removed also.

"A regular grammar G is ambiguous if some sentence in L(G) has two distinct
derivations in G from the start symbol S; otherwise G is unambiguous."
S.Sippu, E.Soisalon-Soininen, Parsing Theory, Vol 1, Springer-Verlag, 1988,
p. 82

"A finite automaton M is nondeterministic if it has a configuration to which
two rules are applicable..." p. 87


Rick Jelliffe
Received on Friday, 3 September 1999 07:35:22 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:59:29 GMT