Generalized nondeterministic finite state machine
- Generalized nondeterministic finite state machine
In the theory of computation, a generalized nondeterministic finite state machine or generalized nondeterministic finite automaton (GNFA) is a NFA where each transition may be 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.
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 Σ.
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.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Nondeterministic finite-state machine — In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes … Wikipedia
Nondeterministic finite state machine — In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes … Wikipedia
State diagram — State diagrams is a diagram used in the field of computer science, representing the behavior of a system, which is composed of a finite number of states. There are many forms of state diagrams, which differ slightly and have different semantics.… … Wikipedia
List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… … Wikipedia
Pushdown automaton — In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data. Operation Pushdown automata differ from normal finite state machines in two ways: # They can use the top of the stack to decide… … Wikipedia
Garden of Eden (cellular automaton) — An orphan pattern in Conway s Game of Life, discovered by R. Banks in 1971.[1] … Wikipedia
Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… … Wikipedia
List of computing and IT abbreviations — This is a list of computing and IT acronyms and abbreviations. Contents: 0–9 A B C D E F G H I J K L M N O P Q R S T U V W X Y … Wikipedia
Regular expression — In computing, a regular expression provides a concise and flexible means for matching (specifying and recognizing) strings of text, such as particular characters, words, or patterns of characters. Abbreviations for regular expression include… … Wikipedia
Actor model — In computer science, the Actor model is a mathematical model of concurrent computation that treats actors as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions … Wikipedia
