Quibble on "deterministic"

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 UTC