Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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 language | English |
---|---|
Title of host publication | Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings |
Editors | Nelma Moreira, Rogério Reis |
Publisher | Springer Nature |
Pages | 304-315 |
Number of pages | 12 |
ISBN (Print) | 9783030815073 |
DOIs | |
State | Published - 2021 |
Event | 25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online Duration: 16 Aug 2021 → 20 Aug 2021 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12811 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 25th International Conference on Developments in Language Theory, DLT 2021 |
---|---|
City | Virtual, Online |
Period | 16/08/21 → 20/08/21 |
ID: 85900779