Formal Definition
A GNFA can be defined as a 5-tuple, (S, Σ, T, s, a), consisting of
- a finite set of states (S);
- a finite set called the alphabet (Σ);
- a transition function (T : (S ∖ {a}) × (S ∖ {s}) → R);
- a start state (s ∈ S);
- an accept state (a ∈ S);
where R is the collection of all regular expressions over the alphabet Σ.
The transition function takes as its argument a pair of two states and outputs a regular expression (the label of the transition). This differs from other finite state machines, which take as input a single state and an input from the alphabet (or the empty string in the case of nondeterministic finite state machines) and outputs the next state (or the set of possible states in the case of nondeterministic finite state machines). A DFA or NFA can easily be converted into a GNFA and then the GNFA can be easily converted into a regular expression by repeatedly collapsing parts of it to single edges until S = {s, a}. Similarly, GNFAs can be reduced to NFAs by changing regular expression operators into new edges until each edge is labelled with a regular expression matching a single string of length at most 1. NFAs, in turn, can be reduced to DFAs using the powerset construction. This shows that GNFAs recognize the same set of formal languages as DFAs and NFAs.
Read more about this topic: Generalized Nondeterministic Finite Automaton
Famous quotes containing the words formal and/or definition:
“True variety is in that plenitude of real and unexpected elements, in the branch charged with blue flowers thrusting itself, against all expectations, from the springtime hedge which seems already too full, while the purely formal imitation of variety ... is but void and uniformity, that is, that which is most opposed to variety....”
—Marcel Proust (1871–1922)
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)