A1 Refereed original research article in a scientific journal
Expressive power of LL(k) Boolean grammars
Authors: Okhotin A
Publisher: ELSEVIER SCIENCE BV
Publication year: 2011
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Number in series: 39
Volume: 412
Issue: 39
First page : 5132
Last page: 5155
Number of pages: 24
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2011.05.013
Abstract
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.
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.
UTU Research Portal