@inproceedings{1ad5f85b8cb44949acf62cd47aa7e0c5,
title = "On the transformation of ll(k)-linear grammars to ll(1)-linear",
abstract = "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.",
author = "Alexander Okhotin and Ilya Olkhovsky",
year = "2020",
month = jun,
day = "1",
doi = "10.1007/978-3-030-50026-9_24",
language = "English",
isbn = "9783030500252",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "328--340",
editor = "Henning Fernau",
booktitle = "Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings",
address = "Germany",
note = "15th International Computer Science Symposium in Russia, CSR 2020 ; Conference date: 29-06-2020 Through 03-07-2020",
}