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)

    • consumeAnyOfRange

      public static <V> NAutomaton<V> consumeAnyOfRange(int first, int last, IntPredicate cond, NAutomaton<V> next)

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

    • adjacency

      Multimap<Automaton.State,Automaton.State> adjacency()

    • labeling

      Multimap<Automaton.State,V> labeling()