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>>
@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:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    class 
    NAutomaton.Trace
    Iterator-like mutable API for tracking the consumption of an input sequence of code points by an automaton.

    Nested classes/interfaces inherited from class eu.bandm.tools.lexic.Automaton

    Automaton.State, Automaton.Transformer<B,R>

  • Field Summary

    Fields inherited from class eu.bandm.tools.lexic.Automaton

    initial, table

  • Constructor Summary

    Constructors
    Constructor
    Description
    NAutomaton(Automaton.State initial, Map<Automaton.State,Behavior<Set<V>,Set<Automaton.State>>> table)
    Creates a new instance.

  • Method Summary

    Modifier and Type
    Method
    Description
    NAutomaton<V>
    complement(V negValue)
    Returns an automaton that differs from this automaton by switching accepted and rejected inputs.
    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.
    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.
    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.
    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.
    NAutomaton<V>
    copy()
    Returns an automaton that is equivalent to this automaton, but uses a set of fresh states.
    (package private) NAutomaton<V>
    copyPartial(Predicate<? super Automaton.State> mustCopy)
    Returns an automaton that is equivalent to this automaton, but uses fresh states as required.
    DAutomaton<V>
    determinate()
    Returns a deterministic automaton that is equivalent to this automaton.
    static <V> NAutomaton<V>
    empty()
    Returns an automaton that accepts no input.
    <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.
    <F> F
    format(FormatServer<F> server)
    Represent this or the underlying object in a human-readable, pretty-printable way.
    <F> F
    format(FormatServer<F> server, Function<? super V,? extends F> onValue)
    Returns a pretty-printable representation of this automaton.
    boolean
    isClosed()
    Checks whether the behavior of this automaton is closed.
    NAutomaton<V>
    loop()
    Returns an automaton that differs from this automaton by restarting from every accepting state.
    NAutomaton<V>
    loop(Predicate<? super V> pred)
    Returns an automaton that differs from this automaton by restarting every state with a selected value.
    <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.
    static <V> NAutomaton<V>
    of(V value)
    Returns an automaton that accepts an input of length zero with the given value.
    (package private) NAutomaton<V>
    orElse(NAutomaton<V> other)
    Returns an automaton that combines the successful transitions and value sets of this and another automaton.
    String
    toString()
    Automaton.Trace<Set<V>>
    trace()
    Returns a fresh trace.
    static <V> NAutomaton<V>
    union(Collection<NAutomaton<V>> parts)
    Returns an automaton that combines the successful transitions and value sets of the given automata.

    Methods inherited from class eu.bandm.tools.lexic.Automaton

    size

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • 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

    • 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

    • 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

      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}