Removing useless productions of a context free grammar through Petri Net.(Technical report)

INTRODUCTION

Considerable interest has been shown in Petri Nets (PNs) as suitable models for representing and studying concurrent systems because of its potential advantages.The major use of Petri Net has been the modeling of systems in which it is possible for some events to occur concurrently and or sequentially. They have been found to be useful for describing and analyzing many systems such as production, automatic control, communication protocol, circuit analysis, physics and systems involving human activity such as management and office information systems, legal systems, teaching and knowledge representation (2-6). In order to allow easy verification and hierarchical decomposition of the system, the reduction method of PNs without changing the properties has also been studied (7). However, there are still some areas where either this versatile model has not been used at all or used to a very limited extent.Formal languages and automata theory is one of such areas. Algorithms to minimize the context free grammars using the Petri net concept have been published (1),(8),(9) in which a petri net representation of the CFG has been given and techniques to eliminate [lambda] and unit-productions have been provided. The object of this paper is to exploit this PN model to remove Uselessproductions of a Context-Free Grammar (CFG). We assume that [lambda]- and unit-productions have already been removed. First the CFG is represented by a PN. Then algorithm is developed to eliminate Uselessproductions.The algorithm is analyzed and implemented in Pascal. using examples of a CFG . The proposed technique is novel in the sense that it provides a better representation and understanding of the problem. It is simple, requires less computation and is easily implemented on computers. Another technique proposed in (3) in which a given finite or infinite labeled transition graphs defined by a graph grammar, in which an algorithm decides whether this graph is isomorphic to the reachable state graph of some finite unlabeled Petri net. The algorithm aims to produce a minimal net realizing the graph. In (10) the Petri net models are established for right linear grammar, expression grammar and property tree formal grammar. The structure algorithms of these models are given and the properties of models are discussed. It is aimed at generating a language process based on Petri net models. These models are intuitional and dynamic

Petri net: A Petri net is an abstract, formal model of information flow (6). PNs are composed of two basic components: a set of places, P and a set of transitions, T. The relationship between the places and the transitions are defined by the input and the output functions. The input function I defines, for each transition [t.sub.j], the set of input places for the transition I([t.sub.j]). The output function O defines, for each transition [t.sub.j], the set of output places …