Solving the State Elimination Case Study using Epsilon Mohammadreza Sharbaf Shekoufeh Kolahdouz-Rahimi Bahman Zamani m.sharbaf@eng.ui.ac.ir sh.rahimi@eng.ui.ac.ir zamani@eng.ui.ac.ir MDSE Research Group Department of Software Engineering University of Isfahan, Iran Abstract The transformation of a finite state automaton into an equivalent reg- ular expression is a challenging topic which is presented in TTC 2017. This paper presents a solution to State Elimination case using the Ep- silon framework. 1 Introduction 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 Ex- pressions (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 transforma- tions. 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. 2 Epsilon Overview Epsilon is a Java-based comprehensive framework which includes several languages for model management tasks such as model transformation, code generation, model refactoring and validation [2]. Following are the Epsilon languages which are used in our solution: • Epsilon Object Language (EOL): EOL is an imperative language which is the core of Epsilon and can be used as a standalone generic language or used within other Epsilon model management languages. For tackling the state elimination problem, we have benefited from EOL in creation and deletion of states and transitions. Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Garcia-Dominguez, G. Hinkel, and Filip Křikava (eds.): Proceedings of the 10th Transformation Tool Contest, Marburg, Germany, 21-07-2017, published at http://ceur-ws.org 1 https://github.com/MSharbaf/TTC2017-StateElimination 2 https://www.eclipse.org/epsilon • Epsilon Transformation Language (ETL): ETL is a declarative model-to-model transformation lan- guage, 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 Solving the State Elimination Case Study using Epsilon In TTC 2017 a state elimination case study [3] based on the state elimination algorithm for FSA has announced. This case study includes a main task and two extensions. The main task is to convert a uniform FSA to the equivalent RE. An FSA is uniformed if it has a unique initial state with no incoming transitions and a unique final state with no outgoing transitions. A regular expression is a mathematical expression which specifies the language generated or accepted by a uniform FSA. The first extension is to transform a non-uniform FSA into a uniform one. The second extension is to convert a probabilistic FSA to a stochastic RE. 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 Overview of the Main Task Solution 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. Phase 1: Transformation of a uniform FSA to a GTG 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. Step 1: Creation of GTG 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. 1 rule StateAddition 2 transform S1: input!State to S2: output!State{ 3 guard : S1.isInitial or S1.isFinal 4 S2.id = S1.id ; 5 S2.isInitial = S1.isInitial ; 6 S2.isFinal = S1.isFinal ; 7 if(S1.isInitial){ 8 trans.source = S2 ; 9 S2.outgoing ::= trans ; 10 } 11 if(S1.isFinal){ 12 trans.target = S2 ; 13 S2.incoming ::= trans ; 14 } 15 } Listing 1: ETL Rule demonstrating the State Addition operation Step 2: Deletion of Intermediate states and transitions 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 [3]. 1 var lbl_PKQ = "" ; 2 var flag_lbl_PKQ = false ; 3 for(tp in P.outgoing.select(tr|tr.target == K)){ 4 for(tq in Q.incoming.select(tr|tr.source == K)){ 5 if(flag_lbl_PKQ == true) 6 lbl_PKQ += "+" ; 7 lbl_PKQ += tp.label + lbl_K_Self_Loop + tq.label ; 8 flag_lbl_PKQ = true ; 9 } 10 delete tp ; 11 } Listing 2: EOL expression to calculate the label of new transitions corresponding to eliminated states Step 3: Labelling the unlabeled transition in the GTG 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. Phase 2: Transformation of a GTG to a final regular expression 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 Overview of the First Extension Solution 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 1 [% 2 var sb := new Native("java.lang.StringBuilder"); 3 sb.append(Transition.allInstances.selectOne(s|s.label.isDefined()).label); 4 %] 5 [%=sb.toString()%] Listing 3: EGL template for transforming a GTG into an equivalent RE Table 1: Abstraction level for our solution Element Abstraction level Main Task Phase 1 Transformation of a Uniform FSA to a GTG Medium Phase 2 Transformation of a GTG to a final regular expression High Overall solution Medium Extension 1 Overall solution Medium 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 Execution of the Solution 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 Evaluation In the case study description [3] a set of quality characteristics with its measurable attributes are defined for systematic evaluation of each solution. In the following sections the evaluation of our solution according to the correctness, suitability, performance and scalability are provided. 4.1 Correctness 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 Suitability 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. 4.3 Performance 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. Table 2: Evaluation results for our solution includes execution times and scalability level Model name (FSA uniform) Correct Execution Time (s) Scalability leader3_2 (26) yes 0.1476 leader4_2 (61) yes 0.1617 leader3_3 (69) yes 0.1769 leader5_2 (141) yes 0.2252 leader3_4 (147) yes 0.2398 leader3_5 (273) yes 0.3877 leader4_3 (274) yes 0.3639 leader6_2 (335) yes 0.4528 leader3_6 (459) yes 0.71 leader4_4 (812) yes 1 leader5_3 (1050) yes 2 leader3_8 (1059) yes 2 leader4_5 (1933) yes 7 leader6_3 (3759) yes 23 leader4_6 (3962) yes 29 leader5_4 (4244) yes 31 leader5_5 (12709) yes 341.6 leader6_4 (20884) yes 920.8 leader6_5 (78784) yes 9834.34 leader6_6 (234210) yes 102602 Leader6_6 4.4 Scalability 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. 5 Conclusion In this paper we used Epsilon languages to transform a finite state automaton into an equivalent regular ex- pression. 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 exe- cution 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. References [1] D. Steinberg, F. Budinsky, E. Merks, and M. Paternostro, EMF: eclipse modeling framework. 2008. [2] D. Kolovos, L. Rose, R. Paige, and A. Garcıa-Domınguez, The Epsilon Book. 2016. [3] S. Getir, D. A. Vu, F. Peverali, and T. Kehrer, “State Elimination as Model Transformation Problem,” in Proceedings of the 10th Transformation Tool Contest, a part of the Software Technologies: Applications and Foundations (STAF 2017) federation of conferences (A. Garcia-Dominguez, G. Hinkel, and F. Krikava, eds.), CEUR Workshop Proceedings, CEUR-WS.org, July 2017.