Conjunctive grammar

From Wikipedia, the free encyclopedia

Conjunctive grammars are a class of formal grammars studied in formal language theory. They extend the basic type of grammars, the context-free grammars, with a conjunction operation. Besides explicit conjunction, conjunctive grammars allow implicit disjunction represented by multiple rules for a single nonterminal symbol, which is the only logical connective expressible in context-free grammars. Conjunction can be used, in particular, to specify intersection of languages. A further extension of conjunctive grammars known as Boolean grammars additionally allows explicit negation.

The rules of a conjunctive grammar are of the form

A \to \alpha_1 \wedge \ldots \wedge \alpha_m

where A is a nonterminal and α1, ..., αm are strings formed of symbols in Σ and N (finite sets of terminal and nonterminal symbols respectively). Informally, such a rule asserts that every string w over Σ that satisfies each of the syntactical conditions represented by α1, ..., αm therefore satisfies the condition defined by A.

Two equivalent formal definitions of the language specified by a conjunctive grammar exist. One definition is based upon representing the grammar as a system of language equations with union, intersection and concatenation and considering its least solution. The other definition generalizes Chomsky's generative definition of the context-free grammars using rewriting of terms over conjunction and concatenation.

Though the expressive means of conjunctive grammars are greater than those of context-free grammars, conjunctive grammars retain some practically useful properties of the latter, such as efficient parsing algorithms.


[edit] External links