Class DFA

A deterministic finite automaton.

This class implements DFAs with the following properties:

  • There is exactly one initial state.

  • There may be any number of final states.

    This is implemented using a Set of 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.

  • Between any two states, there can at most be one transition.

Hierarchy

  • DFA

Implements

Properties

finals: Set<DFA.Node> = ...

The set of final states of the DFA.

This set may be empty or contain nodes not reachable from the initial state.

initial: DFA.Node

The initial state of the DFA.

maxCharacter: Char

The maximum character that is part of the alphabet of the words that this FA can accept.

Accessors

  • get isEmpty(): boolean
  • Returns whether this FA accepts the empty language meaning that it doesn't accept any words.

    Returns boolean

  • get isFinite(): boolean
  • 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.

    Returns boolean

Methods

  • Complements this DFA.

    This DFA after calling this function will accept all words that are not accepted by this DFA before calling this function.

    This operation will create at most 1 node with the given factory.

    Parameters

    Returns void

  • Returns the number of nodes reachable from the initial state including the initial state.

    This returns the number of nodes returned by nodes.

    Returns number

  • Minimizes this DFA.

    Returns void

  • 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 DFA.

    Modifying the DFA 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.

    Returns Iterable<DFA.Node>

  • Modifies this DFA such that all prefixes of all accepted words are also accepted.

    If the language of this DFA is empty, then it will remain empty.

    Unreachable states will be removed by this operation.

    Returns void

  • Returns void

  • Returns whether this and the given DFA are structurally equal meaning that all nodes and all transitions are equal.

    Parameters

    Returns boolean

  • Returns whether this FA accepts the given word.

    Parameters

    Returns boolean

  • 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.

    Parameters

    • Optional charSetToString: ((charSet: CharSet) => string)
        • (charSet: CharSet): string
        • Parameters

          Returns string

    Returns string

  • 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.

    Parameters

    • Optional charSetToString: ((charSet: CharSet) => string)
        • (charSet: CharSet): string
        • Parameters

          Returns string

    Returns string

  • Returns a string representation of this FA.

    Returns string

  • 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).

    Returns Iterable<WordSet>

  • Returns an iterable that will yield all words accepted by this FA. Words are yielded by ascending length.

    If this FA accepts infinitely many words, the iterable will never end.

    Returns Iterable<Word>

  • Creates a new DFA which matches no words. The language of the returned DFA is empty.

    This operation will create exactly 1 node with the given factory.

    Parameters

    Returns DFA