Finite Automata Tool 


This is the manual of the finite automata tool (FAT). It should give an overview of what FAT is all about and provides the necessary prerequisites that are needed to understand it. Furthermore some aspects about the usability are given in order to answer arising questions when using FAT.


As the program name already indicates, FAT is all about automata, finite automata to be accurate. What is a finite automaton?

Consider any system, there we usually have some notion of state. Such a state gives all relevant information necessary to determine how the system can evolve from that point on. Clearly, these states can change over time. We call such changes of states transitions and they can happen either spontaneously or in response to external inputs.

Now, a system that consists only of finitely many states and transitions among them is called a finite-state transition system. We model these abstractly by a mathematical model called a finite automaton.

Finite Automata

Thus, a finite automaton is a model of behavior composed of a finite number of states and transitions among them. There are different types of finite automata, basically we distinguish between deterministic and nondeterministic ones.

Formally, a deterministic finite automaton (DFA) is a structure

M = (Q, Σ, δ, s, F),
where Determinism in this context means that for any state q and for any input a we exactly have one follow state. If we switch over to nondeterminism, then this is no longer the case. Here, for some states we can have more than one follow state on input a or no follow state at all. Accordingly the definition changes a bit.

A nondeterministic finite automaton (NFA) is a five-tuple

M = (Q, Σ, Δ, s, F),
where everything is the same as in a deterministic automaton, except for the following difference. Intuitively, Δ(q, a) gives the set of all states that M is allowed to move to from q in one step under input symbol a.

Further reading can be found in the literature or in the web, e.g. under one finds some examples of finite automata as well as some pointers to the literature.


When starting the tool, one can immediately see a big white presentation panel in the middle which is used for presenting automata and algorithms. At the right is a navigation bar for starting and controlling the algorithms. Additionally there is a menu, supporting the user with the most relevant functionality from the navigation bar and some further common entries.

Presentation Panel

The presentation panel is somehow the main panel of the tool. Here, automata are getting displayed graphically in the appropriate layout facets according to the chosen algorithm, new automata can be written by hand or existing ones are getting edited. The concrete syntax how to manage the latter two can be found in the grammar section.

It is clear that in order to fulfill all these requirements, the presentation panel's appearance has to change dynamically.

Navigation Bar

The navigation bar basically consists of two things, an automaton list holding the available and loaded automata and the possibility to initiate all kind of algorithms that are supported by FAT, depending on the current automata selection.

The set of basic operations - located at the left top corner of the navigation bar - contains operations to add new automata to the list, to edit existing and selected ones, to load or save automata in files, or to simply delete them from the list. A double-click on a particular automaton shows this automaton graphically in the presentation panel.

Note that when editing an automaton, there also is a useful operations to rename the states. This is helpful to shrink the length of the state names.

The full set of algorithms the tool supports, is listed and explained in the algorithm section in detail.

Behavior of the Tool

Depending on what kind of activity you have chosen, some components are hidden or getting disabled. For example, if you start an algorithm the user's attention is put on its visualization, therefore menu and navigation bar are hidden. Another example is the selection of automata. All algorithms which are not applicable on the current selection of automata become disabled.