Manual
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.Prerequisites
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
- Q is a finite set; elements of Q are called states;
- Σ is a finite set; the input alphabet;
- δ : Q x Σ → Q is the transition function. Intuitively, δ is a function that tells which state to move to (follow state) in response to an input: if M is in state q and sees input a, it moves to state δ(q, a).
- s ∈ Q is the start or initial state;
- F is a subset of Q; elements of F are called accept or final states.
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.
-
Δ is a function
Δ : Q x Σ → 2Q,
where 2Q denotes the power set of Q or the set of all subsets of Q:2Q = {A | A ⊆ Q}.
Further reading can be found in the literature or in the web, e.g. under http://de.wikipedia.org/wiki/Endlicher_Automat one finds some examples of finite automata as well as some pointers to the literature.
Usability
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.