Expressive power of LL(k) boolean grammars

Standard

Expressive power of LL(k) boolean grammars. / Okhotin, Alexander.

In: Theoretical Computer Science, Vol. 412, No. 39, 09.09.2011, p. 5132-5155.

Research output: Contribution to journal › Article › peer-review

Author

Okhotin, Alexander. / Expressive power of LL(k) boolean grammars. In: Theoretical Computer Science. 2011 ; Vol. 412, No. 39. pp. 5132-5155.

BibTeX

@article{e93777ca2c664e4ca991a488ba6ab9d4,

title = "Expressive power of LL(k) boolean grammars",

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 Σ*a* obey a certain periodicity property, which, in particular, makes the language anb2n|n0 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.",

keywords = "Boolean grammars, Conjunctive grammars, Context-free grammars, Language equations, LL grammars, Parsing, Recursive descent",

author = "Alexander Okhotin",

year = "2011",

month = sep,

day = "9",

doi = "10.1016/j.tcs.2011.05.013",

language = "English",

volume = "412",

pages = "5132--5155",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "39",

}

RIS

TY - JOUR

T1 - Expressive power of LL(k) boolean grammars

AU - Okhotin, Alexander

PY - 2011/9/9

Y1 - 2011/9/9

N2 - 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 Σ*a* obey a certain periodicity property, which, in particular, makes the language anb2n|n0 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.

AB - 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 Σ*a* obey a certain periodicity property, which, in particular, makes the language anb2n|n0 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.

KW - Boolean grammars

KW - Conjunctive grammars

KW - Context-free grammars

KW - Language equations

KW - LL grammars

KW - Parsing

KW - Recursive descent

UR - http://www.scopus.com/inward/record.url?scp=80051664073&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.05.013

DO - 10.1016/j.tcs.2011.05.013

M3 - Article

AN - SCOPUS:80051664073

VL - 412

SP - 5132

EP - 5155

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 39

ER -

ID: 41140892