Expressive power of LL(k) Boolean grammars

AbstractThe paper studies the family of Boolean LL languages, generated by Boolean grammars and usable with the recursive descent parsing. It is demonstrated that over a one-letter alphabet, these languages are always regular, while Boolean LL subsets of Σ∗a∗ obey a certain periodicity property, which, in particular, makes the language {anb2n|n⩾0} non-representable. It is also shown that linear conjunctive LL grammars cannot generate any language of the form L⋅{a,b}, with L non-regular, and that no languages of the form L⋅c∗, with non-regular L, can be generated by any linear Boolean LL grammars. These results are used to establish a detailed hierarchy and closure properties of these and related families of formal languages