Abstract:

"Automaton" - originating from the greek word “αυτόματο” – implies a “self-acting” machine following predetermined sequences of operations automatically. Automata theory has always been an indispensable part of a core curriculum in computer science and engineering. In the context of computer science, automata are mathematical models for abstract machines which describe what can be done with computers of varying amounts of memory. They do so by recognizing languages (i.e., finite or infinite sets of strings) defined over alphabets (i.e., finite sets of symbols). There are various types of automata. Finite automata recognize regular languages, a particular class of languages which describe what can be done with computers of very limited memory (in a similar way that Turing machines abstract what can be done with ordinary computers). Regular expressions are strings of finite length which describe regular languages. There is at least one regular expression describing any language recognized by a finite automaton (and vice versa).

In this work, we present FARE, an online application which computes an equivalent regular expression for the language recognized by an input finite automaton whose transition diagram is just graphically designed. More precisely, users create the transition diagram of a finite automaton by graphically adding states and transitions among them via a simple and easy-to-use graphical environment. Using as input the user-created transition diagram of a finite automaton, FARE computes and returns as output an equivalent regular expression via a provably correct constructive procedure (i.e., the GNFA-based algorithm). This procedure gradually eliminates states and transitions among them and replaces them with equivalent regular expressions, which are eventually combined into a single regular expression. FARE has been developed using unity and C++. It is a lightweight and user-friendly application.

Finite automata have several real-world applications in software (e.g., compilers, text editors, video games, pattern and speech recognition, security analysis, protocol analysis, search engines) and hardware industry (e.g., cpu control units, hardware design verification, sequential circuit design, model checking, elevators, vending machines, traffic-sensitive traffic lights). FARE can certainly be of practical usefulness especially due to the graphical design environment via which the procedure of providing the input finite automaton is significantly simplified compared to few other existing approaches where the input is provided via text of complex and sophisticated structure. Furthermore, our online application can be exploited for student education and training both in real or virtual learning environments, in an online or offline manner. In the context of courses on Theory of Computation or Computational Complexity, students are expected to understand and design finite automata and regular expressions; they are also expected to understand and exploit their equivalence. FARE can certainly assist students in their study and help them enhance their understanding, knowledge and skills.

Keywords:

Finite automata, regular expressions, GNFA-based algorithm, online application, graphical environment, Unity, C#, education, training.