A New Notation for Derivations in Chomsky's Generative Grammars

ID
TR-77-04
Authors
J. L. Baker
Publishing date
June 1977
Abstract

Ordered directed graphs (generalizing ordered trees) are defined and used in a new formal definition of grammatical derivation. The latter is shown equivalent to the currently accepted definition. The new scheme is illustrated by detailed proofs of two familiar results: the equivalence of the notions "context-sensitive" and "length-nondecreasing" as applied to grammars, and an important lemma in the theory of deterministic context-free parsing.