DOI

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.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory - 25th International Conference, DLT 2021, Proceedings
РедакторыNelma Moreira, Rogério Reis
ИздательSpringer Nature
Страницы304-315
Число страниц12
ISBN (печатное издание)9783030815073
DOI
СостояниеОпубликовано - 2021
Событие25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online
Продолжительность: 16 авг 202120 авг 2021

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12811 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция25th International Conference on Developments in Language Theory, DLT 2021
ГородVirtual, Online
Период16/08/2120/08/21

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 85900779