@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",

}