Journal of Computer Science

Removing Useless Productions of a Context Free Grammar through Petri Net

Mansoor Al-A'ali and Ali A. Khan

DOI : 10.3844/jcssp.2007.494.498

Journal of Computer Science

Volume 3, Issue 7

Pages 494-498


Following the proposal for a Petri Net (PN) representation of the Context Free Grammar (CFG)[1], we propose in this paper, an algorithm to eliminate the useless productions of CFG. First the CFG is represented by a PN. Then, based on the reachability, an algorithm is developed to eliminate Useless-productions. The algorithm is analyzed and implemented in Pascal using examples of a CFG. The proposed algorithm is better than the existing techniques in the sense that PN model is easy to understand and requires fewer computations and easily implemented on computers.


© 2007 Mansoor Al-A'ali and Ali A. Khan. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.