that . The language of a grammar is the set of all strings it generates. Example The grammar , with productions , , , , , is conjunctive. A typical derivation is It can be shown that . The language is not context-free, proved by the pumping lemma for context-free languages. Parsing algorithms Though the expressive power of conjunctive grammars is greater than those of context-free grammars, conjunctive grammars retain some 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. Theoretical properties A property that is undecidable already for context-free languages or finite intersections of them, must be undecidable also for conjunctive grammars; these include: emptiness, finiteness, regularity, context-freeness, inclusion and equivalence. The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure under complement and under ε-free string homomorphism are still open problems (as of 2001). The expressive power of grammars over a one-letter alphabet has been researched. This work provided a basis for the study of language equations of a more general form. Synchronized alternating pushdown automata Aizikowitz and Kaminski introduced a new class of pushdown automata (PDA) called synchronized alternating pushdown automata (SAPDA). They proved it to be equivalent to conjunctive grammars in the same way as nondeterministic PDAs are equivalent to context-free grammars. Notes References External links Technical report version (pdf) Formal languages