Readonly finalsThe set of final states of the NFA.
This set may be empty or contain nodes not reachable from the initial state.
Readonly initialThe initial state of the NFA.
Readonly maxThe maximum character that is part of the alphabet of the words that this FA can accept.
Returns whether this FA accepts the empty language meaning that it doesn't accept any words.
Returns whether the formal language accepted by this FA contains finitely many words.
Note: Finite does not mean that all words can be iterated in practice. E.g. the set of all Unicode words with 10 or less characters contains 2.6e54 many words and can be accepted by a DFA with only 11 states.
Whether this NFA is in its normal form.
Modifies this NFA to accept the concatenation of this NFA and the given FA.
Modifies this NFA to accept the concatenation of this NFA and the given FA.
This is implemented by simply moving the nodes from the given NFA into this NFA. The given NFA will be empty after this operation as nodes are moved, not shared.
Create a mutable copy of this NFA.
Returns the number of nodes reachable from the initial state including the initial state.
This returns the number of nodes returned by nodes.
Yields all nodes reachable from the initial state including the initial state.
This may include trap states, but it will not include unreachable final states.
The order in which nodes will be returned is implementation defined and may change after any operation that modifies the NFA.
Modifying the NFA while iterating will result in implementation-defined behavior. The implementation may stop the iteration or yield an nodes.
This operation runs in O(E + V) where E is the number of nodes reachable from the initial state and V is the number of transitions.
Brings this NFA is in its normal form.
This operation will create at most 1 node with the given factory.
Modifies this NFA to accept the concatenation of the given NFA and this FA.
Modifies this NFA to accept the concatenation of the given NFA and this FA.
This is implemented by simply moving the nodes from the given NFA into this NFA. The given NFA will be empty after this operation as nodes are moved, not shared.
Modifies this NFA to accept at least min and at most max concatenations of itself.
Both min and max both have to be non-negative integers with min <= max.
max is also allowed to be Infinity.
Returns whether this FA accepts the given word.
The characters of the word to test.
Returns the string representation of this FA in the DOT format.
The output of this function can passed to any graph visualization program. This can be a local installation or an online editor.
By default, toUnicodeString is used to represent CharSets. It's possible to provide a
custom stringify function using the charSetToString parameter.
Returns the string representation of this FA in the Mermaid format.
By default, toUnicodeString is used to represent CharSets. It's possible to provide a
custom stringify function using the charSetToString parameter.
Returns the AST of a regular expression that accepts the same language as this FA.
Optional options: Readonly<ToRegexOptions>Modifies this NFA to accept all words from this NFA and the given FA.
Modifies this NFA to accept all words from this NFA and the given NFA.
This is implemented by simply moving the nodes from the given NFA into this NFA. The given NFA will be empty after this operation as nodes are moved, not shared.
Returns an iterable that will yield all word sets accepted by this FA. Word sets are yielded by ascending length.
If this FA accepts infinitely many words, the iterable will never end. If this FA is finite, the iterable will
end after at most 2^O(n) word sets (n = number of states).
If you analyse the words of an FA, consider using this method instead of words. If this method yields k word
sets, then words will yield up to O(k * m ^ l) words (m = number of possible characters, l = the maximum
length of any of the k word sets).
Static allStatic emptyCreates a new NFA which matches no words. The language of the returned NFA is empty.
This operation will create exactly 1 node with the given factory.
Static emptyCreates a new NFA which matches only the empty word.
This operation will create exactly 1 node with the given factory.
Static fromStatic fromCreates a new NFA which matches the given characters.
This operation will create at most 2 nodes with the given factory.
Static fromFAOptional factory: NodeFactory<NFA.Node>Static fromReturns a new NFA which is equivalent to the intersection of the two given FA.
Static fromOptional creationOptions: Readonly<NFA.FromRegexOptions>Optional factory: NodeFactory<NFA.Node>Optional creationOptions: Readonly<NFA.FromRegexOptions>Optional factory: NodeFactory<NFA.Node>Static fromStatic fromCreates a new NFA which matches all and only all of the given word sets.
Static fromCreates a new NFA which matches all and only all of the given words.
A nondeterministic finite automaton.
This class implements NFAs with the following properties:
There is exactly one initial state.
There may be any number of final states.
This is implemented using a
Setof states.No epsilon transitions.
A transitions always consumes a character.
(All character sets are guaranteed to be non-empty.)
Transitions are unordered.
As a consequence,
/aa|bb/and/bb|aa/have the same state machine in this NFA implementation.(The underlying data structure may be a JavaScript
Mapbut the key order is ignored.)Between any two states, there can at most be one transition.
This means that all transitions between two nodes will be merged into one. This is implemented as a simple union. As a consequence,
/a|a/and/a/have the same state machine in this NFA implementation.Normal form
The normal form of this NFA implementation has the following restriction:
Non-normalized NFAs will either be tolerated or normalized by operations.