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.

Note

This API is experimental and might change in incompatible ways in the next release.

Inheritance

object

Automaton

Inherited Members

object.Equals(object, object)

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

Namespace: Lucene.Net.Util.Automaton

Assembly: Lucene.Net.dll

Syntax

public class Automaton

Constructors

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.

Note

This API is experimental and might change in incompatible ways in the next release.

Declaration

public Automaton()

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

State

Transition

Fields

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 = 2

Field Value

Type	Description
int

See Also

SetMinimization(int)

Properties

Info

Associates extra information with this automaton.

Declaration

public virtual object Info { get; set; }

Property Value

Type	Description
object

IsDeterministic

Returns deterministic flag for this automaton.

Declaration

public virtual bool IsDeterministic { get; set; }

Property Value

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

IsEmptyString

See IsEmptyString(Automaton).

Declaration

public virtual bool IsEmptyString { get; }

Property Value

Type	Description
bool

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
string	String, null if this automaton is not in singleton mode.

Methods

ClearNumberedStates()

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.

Note

This API is experimental and might change in incompatible ways in the next release.

Declaration

public virtual void ClearNumberedStates()

Clone()

Returns a clone of this automaton.

Declaration

public virtual object Clone()

Returns

Type	Description
object

Complement()

See Complement(Automaton).

Declaration

public virtual Automaton Complement()

Returns

Type	Description
Automaton

Concatenate(Automaton)

See Concatenate(Automaton, Automaton).

Declaration

public virtual Automaton Concatenate(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
Automaton

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

Determinize()

See Determinize(Automaton).

Declaration

public virtual void Determinize()

Equals(object)

Determines whether the specified object is equal to the current object.

Declaration

public override bool Equals(object obj)

Parameters

Type	Name	Description
object	obj	The object to compare with the current object.

Returns

Type	Description
bool	true if the specified object is equal to the current object; otherwise, false.

Overrides

object.Equals(object)

ExpandSingleton()

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

Declaration

public virtual void ExpandSingleton()

GetAcceptStates()

Returns the set of reachable accept states.

Declaration

public virtual ISet<State> GetAcceptStates()

Returns

Type	Description
ISet<State>	Set of State objects.

GetHashCode()

Serves as the default hash function.

Declaration

public override int GetHashCode()

Returns

Type	Description
int	A hash code for the current object.

Overrides

object.GetHashCode()

GetInitialState()

Gets initial state.

Declaration

public virtual State GetInitialState()

Returns

Type	Description
State	state

GetNumberOfStates()

Returns the number of states in this automaton.

Declaration

public virtual int GetNumberOfStates()

Returns

Type	Description
int

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
int

GetNumberedStates()

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.

Note

This API is experimental and might change in incompatible ways in the next release.

Declaration

public virtual State[] GetNumberedStates()

Returns

Type	Description
State[]

GetSortedTransitions()

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

Declaration

public virtual Transition[][] GetSortedTransitions()

Returns

Type	Description
Transition[][]

GetStartPoints()

Returns sorted array of all interval start points.

Declaration

public virtual int[] GetStartPoints()

Returns

Type	Description
int[]

Intersection(Automaton)

See Intersection(Automaton, Automaton).

Declaration

public virtual Automaton Intersection(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
Automaton

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

Minus(Automaton)

See Minus(Automaton, Automaton).

Declaration

public virtual Automaton Minus(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
Automaton

Optional()

See Optional(Automaton).

Declaration

public virtual Automaton Optional()

Returns

Type	Description
Automaton

Reduce()

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

Declaration

public virtual void Reduce()

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

Repeat()

See Repeat(Automaton).

Declaration

public virtual Automaton Repeat()

Returns

Type	Description
Automaton

Repeat(int)

See Repeat(Automaton, int).

Declaration

public virtual Automaton Repeat(int min)

Parameters

Type	Name	Description
int	min

Returns

Type	Description
Automaton

Repeat(int, int)

See Repeat(Automaton, int, int).

Declaration

public virtual Automaton Repeat(int min, int max)

Parameters

Type	Name	Description
int	min
int	max

Returns

Type	Description
Automaton

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

IsDeterministic

SetAllowMutate(bool)

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
bool	flag	if true, the flag is set

Returns

Type	Description
bool	previous value of the flag

SetMinimization(int)

Selects minimization algorithm (default: MINIMIZE_HOPCROFT).

Declaration

public static void SetMinimization(int algorithm)

Parameters

Type	Name	Description
int	algorithm	minimization algorithm

SetMinimizeAlways(bool)

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
bool	flag	if true, the flag is set

SetNumberedStates(State[])

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.

Note

This API is experimental and might change in incompatible ways in the next release.

Declaration

public virtual void SetNumberedStates(State[] states)

Parameters

Type	Name	Description
State[]	states

SetNumberedStates(State[], int)

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.

Note

This API is experimental and might change in incompatible ways in the next release.

Declaration

public virtual void SetNumberedStates(State[] states, int count)

Parameters

Type	Name	Description
State[]	states
int	count

SubsetOf(Automaton)

See SubsetOf(Automaton, Automaton).

Declaration

public virtual bool SubsetOf(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
bool

ToDot()

Returns Graphviz Dot representation of this automaton.

Declaration

public virtual string ToDot()

Returns

Type	Description
string

ToString()

Returns a string representation of this automaton.

Declaration

public override string ToString()

Returns

Type	Description
string

Overrides

object.ToString()

Union(Automaton)

See Union(Automaton, Automaton).

Declaration

public virtual Automaton Union(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
Automaton

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