DFA, virtual automaton

A DFA (Deterministic Finite-state Automaton) is a program whose outcome depends only initial entries and is not dependent on any event, any action by a user.
A DFA may be used to program a machine, to make a compiler.

This is also called Finite State Machine. DFA can also mean Data Flow Analysis, but this is not the subject of this page.

flowchart
Flowchart

The DFA may be conceived as a collection of states with transitions between states. A transition is a set of action which let pass from a state to the next state.
It assumes a "machine", a program that moves from one state to another.

In the case of code generation, the DFA is generated by a parser from the definition of the grammar of a language. This produces a program capable of compiling source codes conform to this grammar to produce an object code.

Determinism

The outcome depends entirely on the code and the application of the rules. There was no input by the user or any kind of event that could affect the outcome.

Finite states

The number of states is finite, as well as the number of transitions between states.

These two properties imply that it is always possible to solve cases that may present a syntactically correct program because the grammar provides all cases without ambiguity. It is not possible from a given state of the compilation to reach different results.

Flowchart

The flow chart, a sort of diagram, is the visual representation of the stages of a program. The arrows correspond to the states while the rectangles contain actions. It also represent conditions in the form of diamonds.
We may have a multiple condition (such as a switch statement) displayed by breaking the conditions in two-state elements.

The progress of a program depends not only on the states, it depends on external interventions such as mouse movements. In the case of a game for example, the course is difficult to predict. The flow chart is a simplified and necessarily deterministic view of the execution of a program.

Even if a flow chart can provide a representation of a DFA or a program, a program is not a DFA because it depends on external interventions. The program is to the DFA what the robot is to the automaton.

Grammar

A grammar is an expression of the syntax of a language in the form of rules written according conventions recognized by a parser. A DFA can describe the grammar of human language like that of a programming language.

Example of computer grammar:

exp : ( id | addition )
addition: id '+' exp 

These rules, which are recursive in this example, are recognized by the YACC parser. The DFA principle is put into practice in the compiler generator Bison, a GNU free version of YACC. It convert the source code of a program to binary, and use for that the grammar of the language (stored as a DFA) in which is written the program. According to my experience, the implementation in Bison is inferior to what is possible with an alternative such as ANTLR in the complexity of a language. It seems that DFA is more suitable for simpler grammars.