TY - JOUR

T1 - The Hardest LL(k) Language

AU - Мрыхин, Михаил Кириллович

AU - Охотин, Александр Сергеевич

PY - 2023/4

Y1 - 2023/4

N2 - This paper establishes an analogue of Greibach's hardest language theorem ("The hardest context-free language", SIAM J. Comp., 1973, http://dx.doi.org/10.1137/0202025) for the classical family of LL(κ) languages. The first result is that there is a language L0 defined by an LL(1) grammar in the Greibach normal form, to which every language L defined by an LL(1) grammar in the Greibach normal form can be reduced by a homomorphism, that is, w L if and only if h(w) L0. Then it is shown that this statement does not hold for the full class of LL(κ) languages. The other hardest language theorem is then established in the following form: there is a language L0 defined by an LL(1) grammar in the Greibach normal form, such that, for every language L defined by an LL(κ) grammar, with κ ≥ 1, there exists a homomorphism h, for which w L if and only if h(w) L0, where is a new symbol. The results lead to two robust language families: the closures of the languages defined by LL(1) grammars in the Greibach normal form under inverse homomorphisms and under inverse finite transductions.

AB - This paper establishes an analogue of Greibach's hardest language theorem ("The hardest context-free language", SIAM J. Comp., 1973, http://dx.doi.org/10.1137/0202025) for the classical family of LL(κ) languages. The first result is that there is a language L0 defined by an LL(1) grammar in the Greibach normal form, to which every language L defined by an LL(1) grammar in the Greibach normal form can be reduced by a homomorphism, that is, w L if and only if h(w) L0. Then it is shown that this statement does not hold for the full class of LL(κ) languages. The other hardest language theorem is then established in the following form: there is a language L0 defined by an LL(1) grammar in the Greibach normal form, such that, for every language L defined by an LL(κ) grammar, with κ ≥ 1, there exists a homomorphism h, for which w L if and only if h(w) L0, where is a new symbol. The results lead to two robust language families: the closures of the languages defined by LL(1) grammars in the Greibach normal form under inverse homomorphisms and under inverse finite transductions.

KW - Context-free grammars

KW - LL grammars

KW - finite transducers

KW - hardest languages

KW - homomorphisms

KW - parsing

KW - simple grammars

UR - https://www.mendeley.com/catalogue/10e3f794-dfa0-396e-bfe7-14c783c5399f/

U2 - 10.1142/s012905412344001x

DO - 10.1142/s012905412344001x

M3 - Article

VL - 34

SP - 289

EP - 319

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 2&3

ER -