Package eu.bandm.tools.lexic

Class NAutomaton<V>

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

Automaton states are labeled with sets of values. This is a generalization of accepting automata: Roughly, an accepting state corresponds to a state labeled with a non-empty set 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

    • of

      public static <V> NAutomaton<V> of(V value)
      Returns an automaton that accepts an input of length zero with the given value.
      Type Parameters:
      V - the label value type
      Parameters:
      value - the label value
      Returns:
      an automaton that accepts an input of length zero with the given value (in a singleton set)

    • empty

      public static <V> NAutomaton<V> empty()
      Returns an automaton that accepts no input.
      Type Parameters:
      V - the label value type
      Returns:
      an automaton that accepts no input

    • consume

      public static <V> NAutomaton<V> consume(int codePoint, NAutomaton<V> next)
      Returns an automaton that accepts only a given input code point and then behaves like a given automaton.
      Type Parameters:
      V - the label value type
      Parameters:
      codePoint - the code point to consume first
      next - the automaton to emulate next
      Returns:
      an automaton that accepts the given input code point and then behaves like the given automaton

    • consume

      public static <V> NAutomaton<V> consume(String text, NAutomaton<V> next)
      Returns an automaton that accepts only a given sequence of input code point and then behaves like a given automaton.
      Type Parameters:
      V - the label value type
      Parameters:
      text - the code point sequence to consume first
      next - the automaton to emulate next
      Returns:
      an automaton that accepts the given input code points and then behaves like the given automaton

    • consumeAnyOf

      public static <V> NAutomaton<V> consumeAnyOf(int[] codePoints, NAutomaton<V> next)
      Returns an automaton that accepts any one of some given input code points and then behaves like a given automaton.
      Type Parameters:
      V - the label value type
      Parameters:
      codePoints - the choice of code points to consume first
      next - the automaton to emulate next
      Returns:
      an automaton that accepts any one of the given input code points and then behaves like the given automaton

    • consumeAnyOfRange

      public static <V> NAutomaton<V> consumeAnyOfRange(int first, int last, NAutomaton<V> next)
      Returns an automaton that accepts any one of the given interval of input code points and then behaves like a given automaton.
      Type Parameters:
      V - the label value type
      Parameters:
      first - the lowest code point to accept
      last - the highest code point to accept
      next - the automaton to emulate next
      Returns:
      an automaton that accepts any input code points greater or equal to first and less or equal to last, and then behaves like the given automaton

    • consumeAnyOfRange

      public static <V> NAutomaton<V> consumeAnyOfRange(int first, int last, IntPredicate cond, NAutomaton<V> next)
      Returns an automaton that accepts some of the given interval of input code points and then behaves like a given automaton.
      Type Parameters:
      V - the label value type
      Parameters:
      first - the lowest code point to accept
      last - the highest code point to accept
      cond - an additional predicate that code points must satisfy
      next - the automaton to emulate next
      Returns:
      an automaton that accepts any input code points greater or equal to first and less or equal to last, and for which cond returns true, and then behaves like the given automaton

    • consumeAnyOf

      public static <V> NAutomaton<V> consumeAnyOf(Collection<Integer> codePoints, NAutomaton<V> next)
      Returns an automaton that accepts any one of some given input code points and then behaves like a given automaton.
      Type Parameters:
      V - the label value type
      Parameters:
      codePoints - the choice of code points to consume first
      next - the automaton to emulate next
      Returns:
      an automaton that accepts any one of the given input code points and then behaves like the given automaton

    • consumeExcept

      public static <V> NAutomaton<V> consumeExcept(int[] codePoints, NAutomaton<V> next)
      Returns an automaton that accepts any one except some given input code points and then behaves like a given automaton.
      Type Parameters:
      V - the label value type
      Parameters:
      codePoints - the choice of code points not to consume first
      next - the automaton to emulate next
      Returns:
      an automaton that accepts any one except the given input code points and then behaves like the given automaton

    • map

      public <W> NAutomaton<W> map(Function<? super V,? extends W> fun)
      Returns an automaton that differs from this automaton by having a function applied to all values.

      Since values are transformed one to one in the value sets associated with states, the accepting behavior of the automaton is unchanged.

      Type Parameters:
      W - the target value type
      Parameters:
      fun - the function to apply to values
      Returns:
      an automaton that differs from this automaton by having a function applied to all values

    • copy

      public NAutomaton<V> copy()
      Returns an automaton that is equivalent to this automaton, but uses a set of fresh states.
      Returns:
      an automaton that is equivalent to this automaton, but uses a set of fresh states

    • copyPartial

      NAutomaton<V> copyPartial(Predicate<? super Automaton.State> mustCopy)
      Returns an automaton that is equivalent to this automaton, but uses fresh states as required.
      Parameters:
      mustCopy - a predicate that indicates whether to make a fresh copy of a state (true) or to retain the old one (false)
      Returns:
      an automaton that is equivalent to this automaton, but uses fresh states as required

    • disjoin

      public <W> NAutomaton<W> disjoin(NAutomaton<W> aut)
      Returns an automaton that equivalent to the given one, and does not share states with this automaton.
      Type Parameters:
      W - the target value type
      Parameters:
      aut - an automaton
      Returns:
      an automaton that has the same observable behavior as aut, and shares no state with this

    • prune

      public NAutomaton<V> prune()
      Returns an equivalent automaton that has no unreachable states.
      Returns:
      an automaton that has the same observable behavior as this and also the same reachable states, but no unreachable ones

    • orElse

      NAutomaton<V> orElse(NAutomaton<V> other)
      Returns an automaton that combines the successful transitions and value sets of this and another automaton.
      Parameters:
      other - the other automaton
      Returns:
      an automaton that combines the successful transitions and value sets of this and the other automaton
      See Also:

    • flatMap

      public <W> NAutomaton<W> flatMap(Function<? super V,NAutomaton<W>> fun)
      Returns an automaton that differs from this automaton by having each label value expanded into a subautomaton.
      Type Parameters:
      W - the target value type
      Parameters:
      fun - the function for expanding values to subautomata
      Returns:
      an automaton that differs from this automaton by having each label value expanded into a subautomaton by the given function

    • union

      @SafeVarargs public static <V> NAutomaton<V> union(NAutomaton<V>... parts)
      Returns an automaton that combines the successful transitions and value sets of the given automata.
      Type Parameters:
      V - the value type
      Parameters:
      parts - the automata to combine
      Returns:
      an automaton that combines the successful transitions and value sets of the given automata
      See Also:

    • union

      public static <V> NAutomaton<V> union(Collection<? extends NAutomaton<V>> parts)
      Returns an automaton that combines the successful transitions and value sets of the given automata.
      Type Parameters:
      V - the value type
      Parameters:
      parts - the automata to combine
      Returns:
      an automaton that combines the successful transitions and value sets of the given automata
      See Also:

    • loop

      public NAutomaton<V> loop()
      Returns an automaton that differs from this automaton by restarting from every accepting state.

      The resulting automaton behaves as if nondeterministically jumping to the initial state whenever a non-empty label value set is reached.

      Returns:
      an automaton that differs from this automaton by restarting from every accepting state

    • loop

      public NAutomaton<V> loop(Predicate<? super V> pred)
      Returns an automaton that differs from this automaton by restarting every state with a selected value.

      The resulting automaton behaves as if nondeterministically jumping to the initial state whenever a label value set is reached that contains some value selected by the given predicate.

      Parameters:
      pred - the predicate used to select values
      Returns:
      an automaton that differs from this automaton by restarting from every state with a selected value

    • determinate

      public DAutomaton<V> determinate()
      Returns a deterministic automaton that is equivalent to this automaton.

      In the worst case, the number of states can increase exponentially. However, this appears to be rare in practice.

      Returns:
      a deterministic automaton that is equivalent to this automaton
      See Also:

    • complement

      public NAutomaton<V> complement(V negValue)
      Returns an automaton that differs from this automaton by switching accepted and rejected inputs.

      This transformation involves temporary conversion to a deterministic automaton. In the worst case, the number of states can increase exponentially. However, this appears to be rare in practice.

      Parameters:
      negValue - the value to associated with each previously rejecting state
      Returns:
      an automaton that rejects inputs accepted by this automaton, and vice versa

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • format

      public <F> F format(FormatServer<F> server)
      Represent this or the underlying object in a human-readable, pretty-printable way.
      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 Automaton.Trace<Set<V>> trace()
      Description copied from interface: Traceable
      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

    • isClosed

      public boolean isClosed()
      Checks whether the behavior of this automaton is closed.

      This method is mostly useful for debugging; all automata obtained from public factory methods should satisfy this property by construction.

      Returns:
      true if all states referenced in behavior of reachable states also have entries in the table; false otherwise}

    • reverse

      public NAutomaton<V> reverse()
      Returns an automaton that differs from this automaton by accepting input sequences in reverse.
      Returns:
      an automaton that accepts the reverse of inputs accepted by this automaton

    • adjacency

      Multimap<Automaton.State,Automaton.State> adjacency()
      Returns a multimap of all state transitions, regardless of the consumed code point.

      The result does not contain information about state labels.

      Returns:
      a multimap that relates each pair of states that has a transition for some input code point
      See Also:

    • labeling

      Multimap<Automaton.State,V> labeling()
      Returns a multimap of all states and their associated label values.

      The result does not contain information about transitions.

      Returns:
      a multimap that relates each state to the values contained in its associated label set
      See Also:

    • translate

      public NAutomaton<V> translate(Multimap<Integer,Integer> trans)
      Returns an automaton where all accepted input sequences of this automaton have been translated code-point-wise according to a relational image.

      The resulting automaton accepts a sequence of code points y1...yn with the label set of the final state containing a label l, if and only if there is a corresponding sequence of code points x1...xn accepted by this automaton with the same label l, such that trans(xi, yi) returns true for all i.

      Parameters:
      trans - the translating relation
      Returns:
      a behavior where all transition keys of this behavior have been translated according to trans
      Throws:
      NullPointerException - if trans is null
      Since:
      1.1