The Transformation Tool Contest 2017 State Elimination Case [SECase] asks for the reduction of a Finite State Automaton into an equivalent regular expression. Basically, one replaces states with transitions that combine the regular expressions attached to incomming and outgoing transitions of the removed state. This paper shows the SDMLib [SDMLib] solution to this case. Figure 1 shows in graphical notation the SDMLib transformation rule that adds a new initial state to the current automaton and connects this new state to all previous initial states with empty transitions.
Transformation uniformInitial() starts by matching the pattern object graph to the TransitionGraph object passed as parameter. Next, pattern object newI creates a new initial state. Then the sub-pattern rendered within two stacked boxes is executed. The pattern object oldI searches for old initial State objects attached to our TransitionGraph via a states link and with an isInital attribute equal to true. The <<allmatches>> sterotype attached to the sub-pattern shown in Figure 1 causes the sub-pattern to be executed for each match of oldI. Thus, for each old initial state a new Transition t with empty label is created. The new transition connects the new initial state newI and the current old initial state. In addition, the isInitial attribute of oldI is set to false.
We use a similar rule called uniformFinal() to introduce a single nal state into the current automaton. The case description also proposes to add theta transitions between all states that are not yet connected via a transition. Then the reduction algorithm is save to assume that each pair of states is connected via a transition. Similarly, multiple transitions between two states are combined into a single transition. This reduces the number of case distinctions within the algorithm but increases the runtime. Thus, the SDMLib approach does not perform these normalization steps but deals with these cases in its transformation rules.
Figure2 shows our eliminateStates() transformation. Again we start with a pattern object graph that matches the root of our nite automaton, passed as parameter. Next we look up State k, the state that shall be replaced by transitions. State k shall neither be isFinal nor isInitial. Then, the sub-pattern <<allmatches 2>> looks up a State p that has a Transition pk going to State k and a State q that is reached from State k via Transition kq. The sub-pattern <<allmatches 2>> is iterated, that means it is executed for all possible matches. For each match, we call the pseudo path expression p.getOrCreatePQ(q). This operation tries to nd an existing Transition pq that connects the States p and q. The path expression creates such a Transition, otherwise. Operation setLabel(pq, pk, kq, kk) generates a label for transition pq computed as pq.label + pk.label kk.label* kq.label. The cases that pq.label is empty or that kk is null or that kk.label is empty are handled, speci cally. Once all matches of sub-pattern allmatches 2 are handled, sub-pattern allmatches 3 and allmatches 4 remove all old Transitions leading to or leaving State k, respectively. Finally, State k itself is destroyed. The whole top level pattern is iterated itself through the stereotype <<allmatches 5>>. Thus, transformation eliminateStates eliminates all states except the unique initial and nal states introduced at the beginning. These initial and nal states are then connected by exactly one Transition and this Transition has a regular expression as label that is equivalent to the original nite automaton. 3
SDMlib mit Evaluation 0.0385514360 0.0866275960 0.0993657960 1.1262002710 0.1605883720 0.5394560420 35.3694409170 24.6645100420 0.9771501780 8452.815857866
SDMlib ohne Evaluation JFLAP 0.052127528 0.09 0.081792921 0.14 0.063173148 0.49 0.239402017 3.46 0.098499445 4.37 0.294551276 58.6 7.921832035 57.78 3.029549227 143.12 0.771568491 461.64 too big for memory timeout
Overall, the solution was quite straight forward although our state elimination transformation needs quite a number of sub-pattern and we use some helper methods to handle di erent cases, uniformly. [SDMLib] SDMLib - Story Driven Modeling Library www.sdmlib.org May, 2017.