Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 авг 2021 → 20 авг 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/21 → 20/08/21 |
ID: 85900779