Generalized nondeterministic finite state machine
Encyclopedia
In the theory of computation
, a generalized nondeterministic finite state machine, also known as expression automaton
or generalized nondeterministic finite automaton (GNFA) is an NFA
where each transition is labeled with any regular expression
. The GNFA reads blocks of symbols from the input which constitute a string as defined by the regular expression on the transition. There are several differences between a standard finite state machine and a generalized nondeterministic finite state machine. A gNFA must have only one start state and one accept state, and these cannot be the same state, where as a NFA or DFA both may have several accept states, and the start state can be an accept state. A gNFA must have only one transition between any two states, where as a NFA or DFA both allow for numerous transitions between states. In a gNFA, a state has a single transition to every state in the machine, although often it is a convention to ignore the transitions that are labelled with the empty set when drawing generalized nondeterministic finite state machines.
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 language
s as DFAs and NFAs.
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
, a generalized nondeterministic finite state machine, also known as expression automaton
or generalized nondeterministic finite automaton (GNFA) is an NFA
Nondeterministic finite state machine
In the automata theory, a nondeterministic finite state machine or nondeterministic finite automaton is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states...
where each transition is labeled with any regular expression
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
. The GNFA reads blocks of symbols from the input which constitute a string as defined by the regular expression on the transition. There are several differences between a standard finite state machine and a generalized nondeterministic finite state machine. A gNFA must have only one start state and one accept state, and these cannot be the same state, where as a NFA or DFA both may have several accept states, and the start state can be an accept state. A gNFA must have only one transition between any two states, where as a NFA or DFA both allow for numerous transitions between states. In a gNFA, a state has a single transition to every state in the machine, although often it is a convention to ignore the transitions that are labelled with the empty set when drawing generalized nondeterministic finite state machines.
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 functionFunction (mathematics)In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
(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
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
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
Powerset construction
In the theory of computation and Automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton into a deterministic finite automaton which recognizes the same formal language...
. This shows that GNFAs recognize the same set of formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s as DFAs and NFAs.
External links
- A graphical description of GNFAs and the process of converting an NFA to a regular expression using GNFAs, can be found at http://www.cs.sunysb.edu/~cse350/slides/rgExp2.pdf