In the
theory of computation
In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., a ...
, a generalized nondeterministic finite automaton (GNFA), also known as an expression automaton or a generalized nondeterministic finite state machine, is a variation of a
nondeterministic finite automaton
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state ...
(NFA) where each transition is labeled with any
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
. 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, whereas an 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, whereas 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
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
of states (''S'');
* a finite set called the alphabet (Σ);
* a transition
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
(''T'' : (''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
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
by repeatedly collapsing parts of it to single edges until ''S'' = . 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
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the sa ...
. This shows that GNFAs recognize the same set of
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
s as DFAs and NFAs.
References
* Yo-Sub Han and
Derick Wood
Derick Wood (1940–2010) was an English computer scientist who worked for many years as a professor of computer science in Canada and Hong Kong. He was known for his research in automata theory and formal languages, much of which he published i ...
. "The Generalization of Generalized Automata: Expression Automata." In: 9th International
Conference on Implementation and Application of Automata
CIAA, the International Conference on Implementation and Application of Automata is an annual academic conference in the field of computer science.
Its purpose is to bring together members of the academic, research, and industrial community who h ...
, CIAA 2004, Kingston, Canada, July 22–24, 2004, Revised Selected Papers,
LNCS
''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973.
Overview
The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorials, ...
3317, pp. 156–166. {{doi, 10.1007/b105090
*
Michael Sipser
Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massa ...
. 2006. Introduction to the Theory of Computation (2nd ed.). International Thomson Publishing.
External links
* A graphical description of GNFAs and the process of converting an NFA to a regular expression using GNFAs, can be found a
Finite automata