On the transformation of ll(k)-linear grammars to ll(1)-linear

Research outputpeer-review

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.

Original languageEnglish
Title of host publicationComputer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings
EditorsHenning Fernau
PublisherSpringer Nature
Pages328-340
Number of pages13
ISBN (Print)9783030500252
DOIs
Publication statusPublished - 1 Jun 2020
Event15th International Computer Science Symposium in Russia, CSR 2020 - Yekaterinburg
Duration: 29 Jun 20203 Jul 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12159 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Computer Science Symposium in Russia, CSR 2020
CountryRussian Federation
CityYekaterinburg
Period29/06/203/07/20

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the transformation of ll(k)-linear grammars to ll(1)-linear'. Together they form a unique fingerprint.

Cite this