Non-deterministic finite automaton with empty transition

Non-deterministic finite automaton with empty transitions , AFND-TV , AFND-V or . It is the finite automaton that has at least one empty transition.

AFND-TVs are definitions of AFND within regular languages that hinder their mechanical and computer implementation; but it is common to obtain them from transformations inside the LR ( regular expressions to AF, regular grammars to AF). Then they are vital for lexicographical analysis during the design of programming languages .

Summary

[ hide ]

• 1 Definition
• 2 consequences
  • 1 Transformation from AFND-V to AFND
• 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 terminal symbol alphabet , the relation of transitions , F are the final states or arrival within Q , q ₀ is the initial or starting state; It is said that A is a nondeterministic finite automaton with empty transitions (AFDC-TV, or AFDC-V ) iff there in g at least one empty the transition <q _i , , q _j> Where q _i and q _j are any states of A .

Consequences

The formal definition of AFND-V is based on the consideration that often according to algorithms for the transformation of expressions and regular grammars to AF, automata end up with multiple transitions for the same symbol or empty transitions.

Regardless of whether they are undesirable, especially for the material, mainly mechanical, implementation of finite automata; they are essential during the modeling of lexicographic analyzers of the grammatical elements of programming languages, called tokens, such as numeric literals, identifiers, text strings, operators, etc.

Transformation from AFND-V to AFND

Main article “Transformation from AFND-V to AFND”

AFND-Vs can be transformed to non-deterministic finite automata by a series of transformations that are based on reduction to only states with significant transitions determined by the closure , following the steps:

1. A = closure-v (q ₀) is calculated , which will correspond to the initial state of the new automaton.
2. For each symbol of the alphabet T, the achievable states are verified from some state contained in A , and the closure-v of said achievable states is calculated. If these v-closures produce new sets other than A , that is, sets A _i , these will be new states that will be accessed from A and the corresponding symbol.
3. The above is repeated for each new set A _iobtained in (2), until there are no possible transitions for any symbol of the alphabet.