Removing Useless Productions of a Context Free Grammar through Petri Net
Abstract
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.
DOI: https://doi.org/10.3844/jcssp.2007.494.498
Copyright: © 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.
- 2,659 Views
- 5,128 Downloads
- 0 Citations
Download
Keywords
- Formal methods
- context- free grammar
- useless productions
- petri net