Conjunctive and Boolean Grammars
Alexandros Palioudakis · 2010
In this thesis we examine four interesting classes of formal languages. The two of them, namely the regular and context-free ones, are well-known classes that have been widely studied in the literature [21, 22, 23, 24, 25]. The other two, namely conjunctive and Boolean languages, are more recent ones and appear to possess many interesting properties [1, 3, 15]. Conjunctive and Boolean languages can be produced by conjunctive and Boolean grammars respectively which are natural extensions of context-free grammars introduced by A. Okhotin in [1] and [15]. The basic idea behind of these new formalisms is to allow intersection, in conjunctive grammars, and intersection and negation, in Boolean grammars, in the right-hand side of rules. It is immediately obvious that the classes of conjunctive and Boolean languages are proper supersets of the class of context-free languages. In this thesis we also examine three models of abstract machines closely related to the above classes of formal languages. These machines are: automata, pushdown automata and synchronized alternating pushdown automata. Each one of them corresponds in terms of expressive power to one of the previous classes of languages. More specifically, automata correspond to regular languages, pushdown-automata to context-free languages and synchronized alternating pushdown automata to conjunctive languages. At present, there is no known machine model that corresponds to Boolean languages. Nowadays, there exist certain well-understood techniques for demonstrating that a language is not regular or context-free. Unfortunately this does not hold for conjunctive and Boolean languages. After ten years of study, no technique is presently known for showing that a language is not conjunctive or Boolean. Possibly this is the most important open problem in the area. Most of the ideas presented in this thesis are based on existing articles, books and lecture notes. We were mostly influenced by Okhotin’s lectures [27]. Our contributions can be outlined as follows: • Lemmas 2.3.1 and 3.2.1 in which we present a language that can be produced by a one non terminal conjunctive grammar but not by a one non terminal context-free grammar. • Propositions 2.3.1 and 3.2.1 which give us a more general criterion that can be used to show that certain languages can not be produced by one non terminal context-free and one non terminal conjunctive grammars.