Expressive power of \(\text{LL}(k)\) Boolean grammars (Q719251)

Boolean grammars [the author, ``Boolean grammars'', Inf. Comput. 194, No. 1, 19--48 (2004; Zbl 1073.68037)] extend the definition of context-free grammars by allowing explicit Boolean operations in the rules in the sense that standard context-free grammars can combine syntactical conditions using disjunction (effectively specified by multiple rules for a single symbol), conjunctive grammars [the author, ``Conjunctive grammars'', J. Autom. Lang. Comb. 6, No. 4, 519--535 (2001; Zbl 1004.68082)] additionally allow conjunction, and Boolean grammars further support negation. The paper establishes some limitations of the expressive power of \(\text{LL}(k)\) Boolean grammars, the subcase of Boolean grammars to which recursive descent parsing is applicable [the author, ``Recursive descent parsing for Boolean grammars'', Acta Inf. 44, No. 3--4, 167--189 (2007; Zbl 1119.68101)]. After the definition of Boolean grammars, recursive descent parsers for Boolean grammars, and the presentation of some simple normal forms, it is proved that Boolean LL grammars over a unary alphabet generate only regular languages. This is in contrast with general conjunctive grammars which are known to have greater expressive power over one letter alphabets. This result is then used to demonstrate that languages of the form \(\{a^n b^{f(n)} \mid n\geq 1\}\) can only be generated by Boolean LL grammars if \(f(n)\) is linearly bounded (this implies the non-representability of the language \(\{a^nb^{2^n} \mid n\geq 0\}\)). Next, stronger non-representability results are obtained for linear conjunctive LL grammars and linear Boolean LL grammars, then based on these a detailed hierarchy of language families is obtained. Finally, closure properties of these families are determined and compared to the known closure properties of context-free LL languages.