A new proof technique to establish equivalence of the original and the generated λ-free CFG with linear increase in size Article

Navlakha, J. (1982). A new proof technique to establish equivalence of the original and the generated λ-free CFG with linear increase in size . BIT, 22(1), 17-26. 10.1007/BF01934392

cited authors

  • Navlakha, J

authors

abstract

  • To generate an equivalent λ-free context free grammar from an arbitrary CFG, the most efficient algorithms described in the literature increase the size of the grammar by a factor, polynomial in terms of the number of nonterminals maximally occuring on the right hand side of a production. In this paper, we present an algorithm to generate a λ-free CFG whose total space requirement (or its size) is limited to seven times the initial size. The correctness of our algorithm is established by using a new proof technique based on the structure of the derivation trees and using a counting argument to establish that if a terminal string can be derived in one grammar, it can also be derived in the other. © 1982 BIT Foundations.

publication date

  • January 1, 1982

published in

  • BIT  Journal

Digital Object Identifier (DOI)

start page

  • 17

end page

  • 26

volume

  • 22

issue

  • 1