Boolean grammars

A new generalization of context-free grammars is introduced: Boolean grammars allow the use of all set-theoretic operations as an integral part of the formalism of rules. Rigorous semantics for these 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 cubic-time recognition algorithm and some limited extension of the notion of a parse tree, which together allow to conjecture practical applicability of the new concept.

Authors

• Alexander Okhotin

Keywords

• Context-free grammar
• Intersection
• Complement
• Language equation
• Parsing
• Conjunctive grammar
• Trellis automaton
• Cellular automaton