A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Expressive power of LL(k) Boolean grammars
Tekijät: Okhotin A
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2011
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Numero sarjassa: 39
Vuosikerta: 412
Numero: 39
Aloitussivu: 5132
Lopetussivu: 5155
Sivujen määrä: 24
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2011.05.013
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali