Expressive power of LL(k) Boolean grammars

: Okhotin A

Publisher: ELSEVIER SCIENCE BV

: 2011

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 39

: 412

: 39

: 5132

: 5155

: 24

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2011.05.013

The 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 Sigma*a* obey a certain periodicity property, which, in particular, makes the language {a(n)b(2n) vertical bar 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. (C) 2011 Elsevier B.V. All rights reserved.