Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
It is proved that every LL(k)-linear grammar can be transformed to an equivalent LL(1)-linear grammar. The transformation incurs a blow-up in the number of nonterminal symbols by a factor of (formula presented), where m is the size of the alphabet. A close lower bound is established: for certain LL(k)-linear grammars with n nonterminal symbols, every equivalent LL(1)-linear grammar must have at least (formula presented) nonterminal symbols.
Original language | English |
---|---|
Title of host publication | Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings |
Editors | Henning Fernau |
Publisher | Springer Nature |
Pages | 328-340 |
Number of pages | 13 |
ISBN (Print) | 9783030500252 |
DOIs | |
State | Published - 1 Jun 2020 |
Event | 15th International Computer Science Symposium in Russia, CSR 2020 - Yekaterinburg, Russian Federation Duration: 29 Jun 2020 → 3 Jul 2020 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12159 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 15th International Computer Science Symposium in Russia, CSR 2020 |
---|---|
Country/Territory | Russian Federation |
City | Yekaterinburg |
Period | 29/06/20 → 3/07/20 |
ID: 61323684