Conjunctive grammar

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}\And \ldots \And \alpha _{m}

where $A$ is a nonterminal and $\alpha _{1}$ , ..., $\alpha _{m}$ are strings formed of symbols in $\Sigma$ and $N$ (finite sets of terminal and nonterminal symbols respectively). Informally, such a rule asserts that every string $w$ over $\Sigma$ that satisfies each of the syntactical conditions represented by $\alpha _{1}$ , ..., $\alpha _{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. Most importantly, there are generalizations of the main context-free parsing algorithms, including the linear-time recursive descent, the cubic-time generalized LR, the cubic-time Cocke-Kasami-Younger, as well as Valiant's algorithm running as fast as matrix multiplication.

A number of theoretical properties of conjunctive grammars have been researched, including the expressive power of grammars over a one-letter alphabet and numerous undecidable decision problems. This work provided a basis for the study language equations of a more general form.

References

Alexander Okhotin, Conjunctive grammars. Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519-535. (pdf)
Alexander Okhotin, Conjunctive and Boolean grammars: The true general case of the context-free grammars. Computer Science Review, 9 (2013), 27-59.
Artur Jeż. Conjunctive grammars can generate non-regular unary languages. International Journal of Foundations of Computer Science 19(3): 597-615 (2008) Technical report version (pdf)

External links

Artur Jeż. Conjunctive grammars can generate non-regular unary languages. Slides of talk held at the International Conference on Developments in Language Theory 2007.
Alexander Okhotin's page on conjunctive grammars.
Alexander Okhotin. Nine open problems for conjunctive and Boolean grammars.

This article is issued from Wikipedia - version of the 7/9/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.