FA2RE-SE



Objective of the project: Develop a framework that transforms finite automatas (FA's) into Regular Expressions using the state elimination method.

This interface allows the user to perform the operation mentioned above, presenting the results and some useful information about the process at the end.

The main feature of this interface is the possibility to specify how nodes must be "ranked" when selecting which should be removed at each stage. To do this, the user must specify an expression indicating how the "score" of each node is to be calculated, as specified by our DSL (see the About section)



Instructions:

  1. 1 - Import ".DOT" file
  2. 2 - Select node ranking method
  3. 3 - See the results in the propper section


FA2RE-SE


Step 1 - Load ".dot" file


Please specify the ".dot" file containing the information of the finite automata you wish to convert to a regular expression.


"DOT" is a graph description language, implementing rules that allow it to fully define all sorts of graphs. In this case, we will use a subset of the language to represent finite automatas, which are in fact a specific sort of graphs with some rules. For more information on the ".dot" format and to see some examples, click here.


Note: Please choose a valid file!

Demo of the automata (see the .dot content of the automata below):




FA2RE-SE


Step 2 - Specify node ranking method


Below, you can specify an expression that determines how the node ranking should be calculated. Node ranking is used to choose the order in which nodes are removed from the automata, and it has a huge impact on the resulting regular expression.

Feel free to use one of the examples we have created using the buttons directly below the box, or use "Parse DSL" to validate your own expression and find if it has any errors. Don't forget that the grammar must follow thisspecific format.


Note: Please choose a valid dsl!!
static sum(in : #ins_nl) { in.weight * #outdeg_nl } + sum(out : #outs_nl) { out.weight * #indeg_nl } + #nloops * (#indeg_nl * #outdeg_nl);

Success

FA2RE-SE


Results


Regular Expression:



State elimination steps

Nodes removed in this order:


Error: ".dot" file missing. Please see "Step 1"


Error: ranking expression missing. Please see "Step 2"


About

FA2RE-SE was a project developed for the "Compilers" course of the Integrated Master's in Informatics and Computer Engineering of the Faculty of Engineering of the University of Porto.

To use the API, follow the instructions on the project's API documentation..

Check out the project on GitHub.

Developers:
André Lago (GitHub profile)
Carolina Moreira (GitHub profile)
Gustavo Silva (GitHub profile)
Leonardo Ferreira (GitHub profile)

DSL used:

s : (manual SEMICOLON) | (auto SEMICOLON s1 ) | RANDOM;
s1 : EOF|s; manual : INT (COMMA INT)*;
auto : type e;
type : STATIC | DYNAMIC;
e : t e1;
e1 : ((PLUS | MINUS) t e1)?;
t : f t1;
t1 : ((ASTERISK | SLASH) f t1)?;
f : v | RESERVED | INT | REAL | loop | (OPEN1 e CLOSE1);
loop : (SUM | MUL) OPEN1 IDENTIFIER COLON RESERVED CLOSE1 OPEN2 e CLOSE2;
v : IDENTIFIER (DOT IDENTIFIER)?;

WHITESPACE : [ \t\r\n]+ -> skip;

RANDOM : 'random';
STATIC : 'static';
DYNAMIC : 'dynamic';
SUM : 'sum';
MUL : 'mul';
OPEN1 : '(';
CLOSE1 : ')';
OPEN2 : '{';
CLOSE2 : '}';
COMMA : ',';
COLON : ':';
SEMICOLON : ';';
DOT : '.';
PLUS : '+';
MINUS : '-';
ASTERISK : '*';
SLASH : '/';
INT : [0-9]+;
REAL : [0-9]* '.' [0-9]+;
IDENTIFIER : [a-zA-Z_]+ [a-zA-Z_0-9]*;
RESERVED : '#' ('ins' | 'outs' | 'indeg' | 'outdeg' | 'ins_nl' | 'outs_nl' | 'indeg_nl' | 'outdeg_nl' | 'nloops');