Deterministic Finite Automat

Deterministic finite automaton . It is the finite automaton that has all its non-empty transitions and that for each symbol from a state of origin, a single destination state is reached.

AFDs are ideal definitions within regular languages due to their formal closeness towards the creation of fundamentally lexicographic recognition machines, while their transitions are unique by symbol, being able to be performed more easily at the time of their implementation in software , mathematics and physics. .

Summary

[ hide ]

• 1 Definition
• 2 consequences
  • 1 Transformation from AFD to regular grammars.
• 3 See also
• 4 Sources

Definition

Let be a finite automaton defined by the 5-tuple A = <Q, T, g, F, q ₀ > , where Q is the set of states, T the alphabet of terminal symbols, the relation of transitions or (read: of the state q _i through terminal x goes to q _j ), F are the final or arrival states within Q , q ₀ is the initial or starting state; it is said that A is a deterministic finite automaton (AFD) if and only if the following properties are satisfied in g:

• Every transition of gis not empty (which is true in this case, due to the particular definition of g that excludes empty strings from the transition symbols, which is not the case in the general definition of a finite automaton where ).
• From any state and with the same terminal you only go to one and only one state, that is .

In flat terms, this means that you can only go from a state A through terminal x to a single state B :

and the following cases:

• <A,, B>.

they are transitions of finite non-deterministic automata .

Consequences

The formal definition of AFD is based on the consideration that multiple transitions for the same symbol and gaps are undesirable, above all for the material, mainly mechanical, implementation of finite automata. In the case of one of the most frequent uses of these, the modeling of lexicographic analyzers of the grammatical elements of programming languages, the exclusion of indeterminism frees the system from said behavior and makes it more specific and therefore more powerful.

An evident result of the AFD definition is that in the transition tables of the same there is only one state in each box, making the interpretation and recognition of strings using the recognizer clearer.

In short, AFDs are the ideal finite automata, although they cannot always be formalized the first time and are not infrequently the result of the debugging of AFND and AFNDTV. Where it is good to point out that this transformation is always possible.

Transformation from AFD to regular grammars.

Let AFD be A = <Q, T, g, F, q ₀ > , it can be transformed into regular grammar G = <Q, T, P, q ₀ > ( Q , set of nonterminals; T , set of terminal symbols ; P , system of productions of G and q ₀ is the beginning symbol), as it can be seen the elements of the 5-tuple of the finite automaton are transformed directly to those of the 4-upla of the regular grammar. Then the production system P is built from the transitions g by the steps:

1. Transition: <A, x, B> or becomes .
2. Transition to final state: <A, x, B> where B is a final state, or becomes .
3. Loop: <A, x, A> ó becomes .
4. End state loop: <A, x, A> where A is an end state, or becomes .