Expressive power of \(\text{LL}(k)\) Boolean grammars (Q719251): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.013 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2038010989 / rank | |||
Normal rank |
Revision as of 01:08, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Expressive power of \(\text{LL}(k)\) Boolean grammars |
scientific article |
Statements
Expressive power of \(\text{LL}(k)\) Boolean grammars (English)
0 references
10 October 2011
0 references
Boolean grammars [the author, ``Boolean grammars'', Inf. Comput. 194, No. 1, 19--48 (2004; Zbl 1073.68037)] extend the definition of context-free grammars by allowing explicit Boolean operations in the rules in the sense that standard context-free grammars can combine syntactical conditions using disjunction (effectively specified by multiple rules for a single symbol), conjunctive grammars [the author, ``Conjunctive grammars'', J. Autom. Lang. Comb. 6, No. 4, 519--535 (2001; Zbl 1004.68082)] additionally allow conjunction, and Boolean grammars further support negation. The paper establishes some limitations of the expressive power of \(\text{LL}(k)\) Boolean grammars, the subcase of Boolean grammars to which recursive descent parsing is applicable [the author, ``Recursive descent parsing for Boolean grammars'', Acta Inf. 44, No. 3--4, 167--189 (2007; Zbl 1119.68101)]. After the definition of Boolean grammars, recursive descent parsers for Boolean grammars, and the presentation of some simple normal forms, it is proved that Boolean LL grammars over a unary alphabet generate only regular languages. This is in contrast with general conjunctive grammars which are known to have greater expressive power over one letter alphabets. This result is then used to demonstrate that languages of the form \(\{a^n b^{f(n)} \mid n\geq 1\}\) can only be generated by Boolean LL grammars if \(f(n)\) is linearly bounded (this implies the non-representability of the language \(\{a^nb^{2^n} \mid n\geq 0\}\)). Next, stronger non-representability results are obtained for linear conjunctive LL grammars and linear Boolean LL grammars, then based on these a detailed hierarchy of language families is obtained. Finally, closure properties of these families are determined and compared to the known closure properties of context-free LL languages.
0 references
Boolean grammars
0 references
conjunctive grammars
0 references
context-free grammars
0 references
LL grammars
0 references
language equations
0 references
parsing
0 references
recursive descent
0 references