Package eu.bandm.tools.lexic

Class DAutomaton<V>

java.lang.Object
eu.bandm.tools.lexic.Automaton<List<V>,Automaton.State>
eu.bandm.tools.lexic.DAutomaton<V>
Type Parameters:
V - the label value type
All Implemented Interfaces:
FormatClient, Traceable<List<V>>, Serializable
public class DAutomaton<V> extends Automaton<List<V>,Automaton.State> implements Traceable<List<V>>
Deterministic finite-state labeled automaton.

Automaton states are labeled with lists of values. This is a generalization of accepting automata: Roughly, an accepting state corresponds to a state labeled with a non-empty list of values.

This class has no public constructor. Instances can be obtained from factory methods, and by conversion from other types of automata.

See Also:

  • Constructor Details

  • Method Details

    • toString

      public String toString()
      Returns a human-readable representation of this automaton.
      Overrides:
      toString in class Object

    • deflate

      public ZAutomaton<V> deflate()
      Returns a zero-overhead automaton equivalent to this automaton.
      Returns:
      a zero-overhead automaton equivalent to this automaton

    • totalize

      public DAutomaton<V> totalize()
      Returns an automaton that differs from this automaton by having successful transitions for all inputs. Inputs rejected by this automaton lead to dead states in the new automaton, i.e., they are labeled with the empty list of values.
      Returns:
      an automaton that differs from this automaton by having successful transitions for all inputs
      See Also:

    • getLiveStates

      public Set<Automaton.State> getLiveStates()
      Returns the set of live states of this automaton. A state is live, if itself or any reachable state is labeled with a non-empty list; otherwise it is dead.
      Returns:
      a set containing the live states of this automaton

    • abbreviate

      public DAutomaton<V> abbreviate()
      Returns an automaton that differs from this automaton by retaining only live states. For inputs that are eventually rejected, the resulting automaton fails to make a transition at the earliest certain position.
      Returns:
      an automaton that differs from this automaton by retaining only live states

    • complement

      public DAutomaton<V> complement(V negValue)
      Returns an automaton that differs from this automaton by switching accepted and rejected inputs.
      Parameters:
      negValue - the value to associated with each previously rejecting state
      Returns:
      an automaton that rejects inputs accepted by this automaton, and vice versa

    • intersection

      public DAutomaton<V> intersection(DAutomaton<V> other, BinaryOperator<V> combo)
      Returns an automaton that behaves like performing transitions of this and the other given automaton simultaneously.

      The resulting automaton accepts only input that is accepted by both given automata, and combines the result values.

      In the worst case, the number of states of the resulting automaton is the product of the numbers of states of the given automata.

      Parameters:
      other - the other automaton
      combo - the operation for combining the values for an accepted input
      Returns:
      an automaton that behaves like performing transitions of the two automata simultaneously

    • nondeterminate

      public NAutomaton<V> nondeterminate()
      Returns a nondeterministic automaton that is equivalent to this automaton.
      Returns:
      a nondeterministic automaton that is equivalent to this automaton
      See Also:

    • mapList

      public <W> DAutomaton<W> mapList(Function<? super List<V>,? extends List<W>> fun)
      Returns an automaton that differs from this automaton by having a function applied to the list of values associated with each reachable state.
      Type Parameters:
      W - the target value type
      Parameters:
      fun - the function to apply to each list of values
      Returns:
      an automaton that differs from this automaton by having the given function applied to the list of values associated with each reachable state

    • distinguishingCodePoints

      Set<Integer> distinguishingCodePoints()
      Returns the set of distinguishing code points of this automaton.

      This set contains all code points that occur explicitly in the behavior associated with any state, plus one code point that only occurs with default values. It is used for Hopcroft's minimization algorithm.

      Returns:
      the set of distinguishing code points of this automaton
      See Also:

    • minimize

      public DAutomaton<V> minimize()
      Returns an automaton that is equivalent to this automaton but uses the least possible number of states.
      Returns:
      an automaton that is equivalent to this automaton but uses the least possible number of states

    • format

      public <F> F format(FormatServer<F> server)
      Returns a pretty-printable representation of this automaton.
      Specified by:
      format in interface FormatClient
      Type Parameters:
      F - the type of format objects to produce
      Parameters:
      server - a factory object that can produce format objects
      Returns:
      a format object produced by the server

    • format

      public <F> F format(FormatServer<F> server, Function<? super V,? extends F> onValue)
      Returns a pretty-printable representation of this automaton.
      Type Parameters:
      F - the type of format objects to produce
      Parameters:
      server - a factory object that can produce format objects
      onValue - the operation to compute a representation of a value
      Returns:
      a pretty-printable representation of this automaton

    • trace

      public DAutomaton<V>.Trace trace()
      Returns a fresh trace.

      Objects obtained as return values from multiple calls to this method do not share mutable state with each other, and can be used safely in concurrency.

      Specified by:
      trace in interface Traceable<V>
      Returns:
      a fresh trace