FARE: AN ONLINE APPLICATION FOR GRAPHICALLY DESIGNING FINITE AUTOMATA AND COMPUTING EQUIVALENT REGULAR EXPRESSIONS

Appears in: ICERI2022 Proceedings

Publication year: 2022

Pages: 7445-7453

ISBN: 978-84-09-45476-1

ISSN: 2340-1095

doi: 10.21125/iceri.2022.1894

Publication year: 2022

Pages: 7445-7453

ISBN: 978-84-09-45476-1

ISSN: 2340-1095

doi: 10.21125/iceri.2022.1894

Conference name: 15th annual International Conference of Education, Research and Innovation

Dates: 7-9 November, 2022

Location: Seville, Spain

Dates: 7-9 November, 2022

Location: Seville, Spain

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.

Citation copied to the clipboard successfully.

Sorry, but the download of this paper is restricted to authorized users only.