A New Notation for Derivations in Chomsky's Generative Grammars
ID
TR-77-04
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.
File(s)