Regular Expression Transformations to Extend Regular Languages

**
Robson da Luz,
Martin Musicante.
**

We consider the problem of extending a regular language using one positive and one negative example. This problem can be stated as follows: given (i) a regular expression E and (ii) a pair of words w, w´, such that w ? L(E) and w´? L(E) (L(E) is the language associated to E), supposing that w´ is obtained from w by adding or removing one or more symbols, then we are interested in building new regular expressions E´ such that they are similar to E and such that L(E) ? {w´} ? L(E´). A previous paper proposes a solution to this problem by defining a graph-transformation algorithm called GREC. GREC performs changes on the graph of a finite-state automaton accepting L(E), in order to derive the new regular expressions E´. In this paper, a new, graphless, version of GREC is defined. Our algorithm (called dGREC) obtains the same solutions as the original GREC, but working on the regular expression. The main advantage of dGREC over GREC is its simplicity, since it manipulates regular expressions and not automata graphs. The algorithm proposed here is being used as a part of a tool for the conservative extension of schemata for XML.

http://www.lbd.dcc.ufmg.br/colecoes/lsfa/2006/006.pdf

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br