Finite Automata Tool
Manual

# 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).
• sQ is the start or initial state;
• F is a subset of Q; elements of F are called accept or final states.
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.
• Δ is a function
Δ : Q x Σ → 2Q,
where 2Q denotes the power set of Q or the set of all subsets of Q:
2Q = {A | AQ}.
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 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.