Premium
A compiler‐based toolkit to teach and learn finite automata
Author(s) -
Chakraborty Pinaki,
Saxena P. C.,
Katti C. P.
Publication year - 2013
Publication title -
computer applications in engineering education
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.478
H-Index - 29
eISSN - 1099-0542
pISSN - 1061-3773
DOI - 10.1002/cae.20492
Subject(s) - computer science , compiler , nondeterministic finite automaton , deterministic finite automaton , state diagram , programming language , two way deterministic finite automaton , deterministic automaton , büchi automaton , finite state machine , theoretical computer science , string (physics) , automaton , automata theory , mathematics , mathematical physics
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. © 2010 Wiley Periodicals, Inc. Comput Appl Eng Educ 21: 467–474, 2013