Non-deterministic finite automaton . It is the finite automaton that has empty transitions or that for each symbol from an origin state, more than one destination state is reached.
AFNDs are not so desirable definitions within regular languages because they hinder their mechanical and computer implementation; although in most of the transformations inside the LR ( regular expressions to AF, regular grammars to AF) they lead to AFND. The AFND, therefore, are essential in the lexicographic analysis and design of the programming languages .
Summary
[ hide ]
- 1 Definition
- 2 consequences
- 3 See also
- 4 Sources
Definition
Let be a finite automaton defined by the 5-tuple A = <Q, T, g, F, q 0 > , where Q is the set of states, T the terminal symbol alphabet , 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 0 is the initial or starting state; It is said that A is a nondeterministic finite automaton (AFDC) iff there in g at least one of the following transitions:
- or <q i, x, q j > and <q i , x, q k > are transitions of g and .
- <q i, , q j > .
Consequences
The formal definition of AFND is based on the consideration that often according to the algorithms of transformation of expressions and regular grammars to AF end up obtaining automata with multiple transitions for the same symbol or empty transitions. Regardless of whether they are undesirable, especially for the material, fundamentally 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, and text strings. , operators, etc.
