Class Automaton

Finite-state automaton with regular expression operations.

Class invariants:

  • An automaton is either represented explicitly (with State and Transition objects) or with a singleton string (see Singleton and ExpandSingleton()) in case the automaton is known to accept exactly one string. (Implicitly, all states and transitions of an automaton are reachable from its initial state.)
  • Automata are always reduced (see Reduce()) and have no transitions to dead states (see RemoveDeadTransitions()).
  • If an automaton is nondeterministic, then IsDeterministic returns false (but the converse is not required).
  • Automata provided as input to operations are generally assumed to be disjoint.

If the states or transitions are manipulated manually, the RestoreInvariant() method and IsDeterministic setter should be used afterwards to restore representation invariants that are assumed by the built-in automata operations.

Note: this class has internal mutable state and is not thread safe. It is the caller's responsibility to ensure any necessary synchronization if you wish to use the same Automaton from multiple threads. In general it is instead recommended to use a RunAutomaton for multithreaded matching: it is immutable, thread safe, and much faster.

This is a Lucene.NET EXPERIMENTAL API, use at your own risk
Inheritance
System.Object
Automaton
Namespace: Lucene.Net.Util.Automaton
Assembly: Lucene.Net.dll
Syntax
public class Automaton : object

Constructors

| Improve this Doc View Source

Automaton()

Declaration
public Automaton()
| Improve this Doc View Source

Automaton(State)

Constructs a new automaton that accepts the empty language. Using this constructor, automata can be constructed manually from State and Transition objects.

Declaration
public Automaton(State initial)
Parameters
Type Name Description
State initial
See Also

Fields

| Improve this Doc View Source

MINIMIZE_HOPCROFT

Minimize using Hopcroft's O(n log n) algorithm. this is regarded as one of the most generally efficient algorithms that exist.

Declaration
public const int MINIMIZE_HOPCROFT = null
Field Value
Type Description
System.Int32
See Also

Properties

| Improve this Doc View Source

Info

Associates extra information with this automaton.

Declaration
public virtual object Info { get; set; }
Property Value
Type Description
System.Object
| Improve this Doc View Source

IsDeterministic

Returns deterministic flag for this automaton.

Declaration
public virtual bool IsDeterministic { get; set; }
Property Value
Type Description
System.Boolean

true if the automaton is definitely deterministic, false if the automaton may be nondeterministic

| Improve this Doc View Source

IsEmptyString

See IsEmptyString(Automaton).

Declaration
public virtual bool IsEmptyString { get; }
Property Value
Type Description
System.Boolean
| Improve this Doc View Source

Singleton

Returns the singleton string for this automaton. An automaton that accepts exactly one string may be represented in singleton mode. In that case, this method may be used to obtain the string.

Declaration
public virtual string Singleton { get; }
Property Value
Type Description
System.String

String, null if this automaton is not in singleton mode.

Methods

| Improve this Doc View Source

ClearNumberedStates()

Declaration
public virtual void ClearNumberedStates()
| Improve this Doc View Source

Clone()

Returns a clone of this automaton.

Declaration
public virtual object Clone()
Returns
Type Description
System.Object
| Improve this Doc View Source

Complement()

See Complement(Automaton).

Declaration
public virtual Automaton Complement()
Returns
Type Description
Automaton
| Improve this Doc View Source

Concatenate(IList<Automaton>)

See Concatenate(IList<Automaton>).

Declaration
public static Automaton Concatenate(IList<Automaton> l)
Parameters
Type Name Description
IList<Automaton> l
Returns
Type Description
Automaton
| Improve this Doc View Source

Concatenate(Automaton)

See Concatenate(Automaton, Automaton).

Declaration
public virtual Automaton Concatenate(Automaton a)
Parameters
Type Name Description
Automaton a
Returns
Type Description
Automaton
| Improve this Doc View Source

Determinize()

See Determinize(Automaton).

Declaration
public virtual void Determinize()
| Improve this Doc View Source

Equals(Object)

Declaration
public override bool Equals(object obj)
Parameters
Type Name Description
System.Object obj
Returns
Type Description
System.Boolean
| Improve this Doc View Source

ExpandSingleton()

Expands singleton representation to normal representation. Does nothing if not in singleton representation.

Declaration
public virtual void ExpandSingleton()
| Improve this Doc View Source

GetAcceptStates()

Returns the set of reachable accept states.

Declaration
public virtual ISet<State> GetAcceptStates()
Returns
Type Description
ISet<State>

Set of State objects.

| Improve this Doc View Source

GetHashCode()

Declaration
public override int GetHashCode()
Returns
Type Description
System.Int32
| Improve this Doc View Source

GetInitialState()

Gets initial state.

Declaration
public virtual State GetInitialState()
Returns
Type Description
State

state

| Improve this Doc View Source

GetNumberedStates()

Declaration
public virtual State[] GetNumberedStates()
Returns
Type Description
State[]
| Improve this Doc View Source

GetNumberOfStates()

Returns the number of states in this automaton.

Declaration
public virtual int GetNumberOfStates()
Returns
Type Description
System.Int32
| Improve this Doc View Source

GetNumberOfTransitions()

Returns the number of transitions in this automaton. This number is counted as the total number of edges, where one edge may be a character interval.

Declaration
public virtual int GetNumberOfTransitions()
Returns
Type Description
System.Int32
| Improve this Doc View Source

GetSortedTransitions()

Returns a sorted array of transitions for each state (and sets state numbers).

Declaration
public virtual Transition[][] GetSortedTransitions()
Returns
Type Description
Transition[][]
| Improve this Doc View Source

GetStartPoints()

Returns sorted array of all interval start points.

Declaration
public virtual int[] GetStartPoints()
Returns
Type Description
System.Int32[]
| Improve this Doc View Source

Intersection(Automaton)

See Intersection(Automaton, Automaton).

Declaration
public virtual Automaton Intersection(Automaton a)
Parameters
Type Name Description
Automaton a
Returns
Type Description
Automaton
| Improve this Doc View Source

Minimize(Automaton)

See Minimize(Automaton). Returns the automaton being given as argument.

Declaration
public static Automaton Minimize(Automaton a)
Parameters
Type Name Description
Automaton a
Returns
Type Description
Automaton
| Improve this Doc View Source

Minus(Automaton)

See Minus(Automaton, Automaton).

Declaration
public virtual Automaton Minus(Automaton a)
Parameters
Type Name Description
Automaton a
Returns
Type Description
Automaton
| Improve this Doc View Source

Optional()

See Optional(Automaton).

Declaration
public virtual Automaton Optional()
Returns
Type Description
Automaton
| Improve this Doc View Source

Reduce()

Reduces this automaton. An automaton is "reduced" by combining overlapping and adjacent edge intervals with same destination.

Declaration
public virtual void Reduce()
| Improve this Doc View Source

RemoveDeadTransitions()

Removes transitions to dead states and calls Reduce(). (A state is "dead" if no accept state is reachable from it.)

Declaration
public virtual void RemoveDeadTransitions()
| Improve this Doc View Source

Repeat()

See Repeat(Automaton).

Declaration
public virtual Automaton Repeat()
Returns
Type Description
Automaton
| Improve this Doc View Source

Repeat(Int32)

See Repeat(Automaton, Int32).

Declaration
public virtual Automaton Repeat(int min)
Parameters
Type Name Description
System.Int32 min
Returns
Type Description
Automaton
| Improve this Doc View Source

Repeat(Int32, Int32)

See Repeat(Automaton, Int32, Int32).

Declaration
public virtual Automaton Repeat(int min, int max)
Parameters
Type Name Description
System.Int32 min
System.Int32 max
Returns
Type Description
Automaton
| Improve this Doc View Source

RestoreInvariant()

Restores representation invariant. This method must be invoked before any built-in automata operation is performed if automaton states or transitions are manipulated manually.

Declaration
public virtual void RestoreInvariant()
See Also
| Improve this Doc View Source

SetAllowMutate(Boolean)

Sets or resets allow mutate flag. If this flag is set, then all automata operations may modify automata given as input; otherwise, operations will always leave input automata languages unmodified. By default, the flag is not set.

Declaration
public static bool SetAllowMutate(bool flag)
Parameters
Type Name Description
System.Boolean flag

if true, the flag is set

Returns
Type Description
System.Boolean

previous value of the flag

| Improve this Doc View Source

SetMinimization(Int32)

Selects minimization algorithm (default: MINIMIZE_HOPCROFT).

Declaration
public static void SetMinimization(int algorithm)
Parameters
Type Name Description
System.Int32 algorithm

minimization algorithm

| Improve this Doc View Source

SetMinimizeAlways(Boolean)

Sets or resets minimize always flag. If this flag is set, then Minimize(Automaton) will automatically be invoked after all operations that otherwise may produce non-minimal automata. By default, the flag is not set.

Declaration
public static void SetMinimizeAlways(bool flag)
Parameters
Type Name Description
System.Boolean flag

if true, the flag is set

| Improve this Doc View Source

SetNumberedStates(State[])

Declaration
public virtual void SetNumberedStates(State[] states)
Parameters
Type Name Description
State[] states
| Improve this Doc View Source

SetNumberedStates(State[], Int32)

Declaration
public virtual void SetNumberedStates(State[] states, int count)
Parameters
Type Name Description
State[] states
System.Int32 count
| Improve this Doc View Source

SubsetOf(Automaton)

See SubsetOf(Automaton, Automaton).

Declaration
public virtual bool SubsetOf(Automaton a)
Parameters
Type Name Description
Automaton a
Returns
Type Description
System.Boolean
| Improve this Doc View Source

ToDot()

Returns Graphviz Dot representation of this automaton.

Declaration
public virtual string ToDot()
Returns
Type Description
System.String
| Improve this Doc View Source

ToString()

Returns a string representation of this automaton.

Declaration
public override string ToString()
Returns
Type Description
System.String
| Improve this Doc View Source

Union(ICollection<Automaton>)

See Union(ICollection<Automaton>).

Declaration
public static Automaton Union(ICollection<Automaton> l)
Parameters
Type Name Description
ICollection<Automaton> l
Returns
Type Description
Automaton
| Improve this Doc View Source

Union(Automaton)

See Union(Automaton, Automaton).

Declaration
public virtual Automaton Union(Automaton a)
Parameters
Type Name Description
Automaton a
Returns
Type Description
Automaton