A compiler-based toolkit to teach and learn finite automata

This paper introduces a compiler technology based approach to model and simulate finite automata for pedagogical purposes. The compiler technology helps to define a language to formally model finite automata and to develop a toolkit to simulate them efficiently. The language is called Finite Automaton Description Language (FADL) and the toolkit is based on it. A fast single-pass compiler is used to compile a finite automaton defined in FADL. Then an interpreter is used to simulate the working of the compiled finite automaton for any input string. The nondeterminism of a Nondeterministic Finite Automaton (NFA) is simulated using backtracking. A tool to view the transition diagram of the finite automaton is provided. A Deterministic Finite Automaton (DFA) can be additionally compiled using an optimizing compiler that also minimizes the number of states. Tools for converting an NFA to a DFA and for converting a DFA to a Turing machine are also provided. A preliminary testing of the toolkit has been performed in which the participating students observed that the toolkit is an interesting teaching tool and it helped them to acquire a better perception about finite automata. (c) 2010 Wiley Periodicals, Inc. Comput Appl Eng Educ 21: 467-474, 2013