View Related Documents

Abstract

As a direct continuation of the earlier research on conjunctive grammars — context-free grammars equipped with intersection — this paper introduces a new class of formal grammars, which allow the use of all set-theoretic operations as an integral part of the formalism of rules. Rigorous semantics for such grammars is defined by language equations in a way that allows to generalize some techniques from the theory of context-free grammars, including Chomsky normal form, Cocke—Kasami—Younger recognition algorithm and some limited extension of the notion of a parse tree, which together allow to conjecture the practical applicability of the new concept.

Fulltext Preview

Image of the first page of the fulltext document