You are here: TUCS > PUBLICATIONS > Publication Search > Expressive Power of LL(k) Bool...
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
Expressive Power of LL(k) Boolean Grammars
Alexander Okhotin, Expressive Power of LL(k) Boolean Grammars. TUCS Technical Reports 823, Turku Centre for Computer Science, 2007.
Abstract:
The family of languages generated by Boolean grammars and usable with the recursive descent parsing is studied. It is demonstrated that Boolean LL languages over a unary alphabet are regular, while Boolean LL subsets of Σ*a* obey a certain periodicity property, which, in particular, makes the language { <i>a<sup>n</sup></i> <i>b</i><sup>2<sup><i>n</i></sup></sup> | <i>n</i> ≥ 0 } nonrepresentable. It is also shown that { <i>a<sup>n</sup> b<sup>n</sup> c s</i> | <i>n</i> ≥ 0, <i>s</i> ∈ {<i>a,b</i>} } is not generated by any linear conjunctive LL grammar, while linear Boolean LL grammars cannot generate { <i>a<sup>n</sup> b<sup>n</sup> c</i>* | <i>n</i> ≥ 0 }.
Files:
Full publication in PDF-format
BibTeX entry:
@TECHREPORT{tOkhotin07b,
title = {Expressive Power of LL(k) Boolean Grammars},
author = {Okhotin, Alexander},
number = {823},
series = {TUCS Technical Reports},
publisher = {Turku Centre for Computer Science},
year = {2007},
keywords = {Boolean grammars, conjunctive grammars, language equations, parsing, recursive descent},
ISBN = {978-952-12-1912-2},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics