This paper establishes an analogue of Greibach’s hardest language theorem (“The hardest context-free language”, SIAM J. Comp., 1973) for the subfamily 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 LL(k) languages. The second 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(k) grammar, there exists a homomorphism h, for which w∈ L if and only if h(w$ ) ∈ L0, where $ is a new symbol.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 25th International Conference, DLT 2021, Proceedings
EditorsNelma Moreira, Rogério Reis
PublisherSpringer Nature
Pages304-315
Number of pages12
ISBN (Print)9783030815073
DOIs
StatePublished - 2021
Event25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12811 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on Developments in Language Theory, DLT 2021
CityVirtual, Online
Period16/08/2120/08/21

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 85900779