REGULAR GRAMMAR TRANSFORMATION INSPIRED BY THE GRAPH DISTANCE USING GA
This paper introduces a method how to transform one regular grammar to the second one. The transformation is based on regular grammar distance computation. Regular grammars are equivalent to finite states machines and they are represented by oriented graphs or by transition matrices, respectively. Thus, the regular grammar distance is defined analogously to the distance between two graphs. The distance is measured as the minimal count of elementary operations over the grammar which transform the first grammar to the second one. The distance is computed by searching an optimal mapping of non-terminal symbols of both grammars. The computation itself is done by the genetic algorithm because the exhaustive evaluation of mapping leads to combinatorial explosion. Transformation steps are derived from differences in matrices. Differences are identified during the computation of the distance.
graph graph distance regular grammar distance finite state machine genetic algorithm automata