The transformation of a finite state automaton into an equivalent regular expression is a challenging topic which is presented in TTC 2017. This paper presents a solution to State Elimination case using the Epsilon framework. The State Elimination case study includes both a model to model and a model to text transformation, which aims to transform Finite State Automata (FSA) or Finite State Machines (FSM) into equivalent Regular Expressions (RE). This is a challenging and expensive transformation. In this paper, we provide a solution to the transformation problem which eliminates states in an iterative manner. Our solution is based on random selection of a state and eliminating it from FSA. The solution is available as a Github repository1. Our solution is implemented using Epsilon2 invoked from a Java application. Epsilon is an extensible set of languages and tools for model management which is built atop the Eclipse Modeling Framework (EMF) [1]. Epsilon can be used to perform all model management tasks, including in-place and out-place model transformations. Epsilon is an appropriate tool for solving the above mentioned case study that involves model modification, before generating equivalent regular expressions based on finite stated automata. The remainder of this paper is structured as follows. Section 2 provides an introduction to the fundamental parts of Epsilon which are used for solving this problem. Section 3 provides our solution to the case study. Evaluation of the proposed solution is presented in section 4. Finally, section 5 summarizes our findings.
Epsilon Transformation Language (ETL): ETL is a declarative model-to-model transformation language, which inherits the imperative feature of EOL to perform complex transformations. It accepts multiple input models and is able to generate multiple target models. However, for this solution, we only used a single source and target model. Each ETL program consists of several ETL modules. A module can contain any number of transformation rules, operations and optional pre and post blocks, which are executed before and after the transformation rules, respectively.
Epsilon Generation Language (EGL): EGL is a template-based language for text generation, which facilitates the construction of model-to-text transformations. Each EGL template consists of static and dynamic parts that reuses the EOL mechanism for defining declarative operations.
The aforementioned languages are used to create scripts (Epsilon codes) that take one or more models and transform them into another model or text. The ETL and EGL scripts can be executed with launch configuration facilities or alternatively invoked directly from a Java program. 3
In TTC 2017 a state elimination case study [
The state elimination algorithm for the main task takes a uniform FSA and generates an equivalent regular expression. In this paper the Epsilon framework is used to solve the main task and the first extension. In the following sections the description of the solutions are provided in more detail. 3.1
In order to solve the main task problem, the transformation specification takes the uniform FSA as input model, and generates the equivalent regular expression as output model. The transformation eliminates each state with corresponding transitions and adds a new equivalent transition for predecessor and successor states in each iteration, until there is only one initial and one final state. In this solution the transformation chain includes two main phases:
Phase 1: Transformation of a uniform FSA to a generalized transition graph (GTG)
Phase 2: Transformation of a GTG to a final regular expression In the following section each phase is explained in more detail.
This phase is a model-to-model transformation, which is divided into three steps as follows: Step 1: Creating a GTG, with initial and final states, and an unlabeled transition between them Step 2: Selection and deletion of intermediate states (i.e., states other than initial and final) of FSA and their incoming and outgoing transitions Step 3: Labelled transition between initial and final states in GTG, equivalent to all transitions of the input FSA These steps are implemented in an ETL module, which consists of ETL rules and sets of operations. In the following more details of this transformation is provided.
In this step a GTG with a single initial and final state, and a single outgoing and incoming transitions is generated. Listing 1 illustrates the implementation of this rule in ETL. In this rule the initial and final states of input model is given to the transformation, and it then generates the model in the output with initial state, final state and a transition between them. Calculation of transition label is performed in the second and third steps.
In this step all the intermediate states and related transitions are eliminated and new labeled transitions
corresponding to them are generated. The implementation of this step is provided in Listing 2. The EOL
operations and expressions are used here for identification and deletion of the elements in the source model.
In order to calculate the label of transition it is required to delete each intermediate state of FSA (for instance
K), and transform its transitions into a new one with respect to its predecessor (P) and successor states (Q).
These states are detected by examining the incoming and outgoing transitions for the intermediate state.
In addition it is required to check the existence of loop, i.e., a transition with an identical initial and final
state, in the selected state (K) and to identify the direct transitions between predecessor (P) and successor
(Q) states. Following that all the transitions between predecessor (P) and successor states are eliminated
and new transitions are generated. Finally a transition is labeled according to the ( pk *kk kq) formula [
lbl_PKQ += "+" ; lbl_PKQ += tp.label + lbl_K_Self_Loop + tq.label ; flag_lbl_PKQ = true ; } } delete tp ;
Listing 2: EOL expression to calculate the label of new transitions corresponding to eliminated states
In this step a single initial and final state with one or more transitions between them are remained in FSA. Additionally, it may be possible for each state to have loop. The transformation in this step generates a label equivalent to all the labels of transitions existed or generated in the previous step based on the state elimination rule. This label is then attached to the new transition between initial and final states in the GTG. The EOL statements are used for implementation of this part in the post condition of ETL module.
In this phase the generated GTG is transformed to a textual file that only contains a final regular expression, which is implemented with an EGL script as indicated in listing 3. EGL has been used to transform model to textual artifact and automatically generate a textual file. 3.2
For the main task it was assumed that the input FSA is uniformed. However, in the first extension it is possible to have more than one initial and final states. The extension is a model-to-model transformation. In our solution
Transformation of a Uniform FSA to a GTG Transformation of a GTG to a final regular expression Overall solution
Overall solution
we have used ETL and EOL to solve this extension. In order to apply the state elimination algorithm to this cases, we should add a new initial state and change its isInitial property to true. Following that, a transition with a null label should be inserted from the new initial state to each original initial states and their isInitial property is changed to false. For the elimination of final states into a single state, we have followed a similar procedure.
In the proposed solution an operation is added to the ETL transformation for transforming non-uniform to uniform FSA, which generates a single initial and final state with its corresponding transitions. This operation is called in the pre-condition of the ETL module written for this extension. 3.3
The proposed solution in this paper requires Epsilon Core for execution of EOL, ETL and EGL scripts. Therefore, we use the Eclipse Distribution which contains most of the required prerequisites of Epsilon. The complete solution uses the ANT Epsilon tasks to execute transformation chains in the specific workflow and enables the user to run it from the Eclipse toolbar. 4
4.1
In the case study description [
According to the evaluation criteria, a solution for the main task is correct when the RE obtained as a final result of the State Elimination passes all sets of positive and negative test cases. Each test case is a set of strings to which the produced Regular Expression should match or should not match, which can be checked by the Evaluation Framework provided in the case description. Regarding the result of Evaluation Framework, our main task solution is correct and passed all the positive and negative test cases.
Additionally, the correctness of the solution for the first extension task generates a uniform FSA which is equivalent to the input FSA with some initial and final states. The Epsilon solution in this paper generates a correct output model for each input model in the extension part. 4.2
The suitability in this case study is evaluated by the level of abstraction of transformation language, which is High for primarily declarative language and Low for primarily imperative language. Although our solution combines imperative EOL statements with ETL and uses EGL script as textual file generator which are primarily declarative, the overall level of abstraction in this solution is Medium. Table 1 shows the abstraction level for each phase of the main task, and an overall value for solutions of the main task and first extension. The solution performance should be measured as the seconds spent for executing two transformation phases with the provided input models. This includes the loading of input FSA models and generating a text file as the equivalent regular expression output. The following table shows the execution time for our solution in seconds. We measured execution time automatically by Ant builder. This measures are the average execution time of ten consecutive executions of Ant builder with the specified input model. All tests were carried out on a standard Windows 7 PC using an Intel R CoreTM i7 with 3.6 GHz processor and 8GB RAM.
Correct yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes
Execution Time (s) 0.1476 0.1617 0.1769 0.2252 0.2398 0.3877 0.3639 0.4528 0.71 1 2 2 7 23 29 31 341.6 920.8 9834.34 102602
4.4
5
According to the evaluation criteria, scalability is a model with a maximum number of states which is correctly converted to an equivalent regular expression. According to the table 2 the transformation generates result for all the test cases specially for model leader6_6 with 234210 states.
In this paper we used Epsilon languages to transform a finite state automaton into an equivalent regular expression. The suitability of transformation languages in this solution is medium for implementation of the main task and first extension. Transformation generates correct results for all the test cases and the result of execution is extensively better than the results provided in the case description. Additionally, the scalability of transformation is high as it managed to execute the largest test case with 234210 states.