Class BasicOperations

Basic automata operations.

Note

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

Inheritance

System.Object

BasicOperations

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: Lucene.Net.Util.Automaton

Assembly: Lucene.Net.dll

Syntax

public static class BasicOperations

Methods

| Improve this Doc View Source

AddEpsilons(Automaton, ICollection<StatePair>)

Adds epsilon transitions to the given automaton. This method adds extra character interval transitions that are equivalent to the given set of epsilon transitions.

Declaration

public static void AddEpsilons(Automaton a, ICollection<StatePair> pairs)

Parameters

Type	Name	Description
Automaton	a	Automaton.
System.Collections.Generic.ICollection<StatePair>	pairs	Collection of StatePair objects representing pairs of source/destination states where epsilon transitions should be added.

| Improve this Doc View Source

Complement(Automaton)

Returns a (deterministic) automaton that accepts the complement of the language of the given automaton.

Complexity: linear in number of states (if already deterministic).

Declaration

public static Automaton Complement(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
Automaton

| Improve this Doc View Source

Concatenate(Automaton, Automaton)

Returns an automaton that accepts the concatenation of the languages of the given automata.

Complexity: linear in number of states.

Declaration

public static Automaton Concatenate(Automaton a1, Automaton a2)

Parameters

Type	Name	Description
Automaton	a1
Automaton	a2

Returns

Type	Description
Automaton

| Improve this Doc View Source

Concatenate(IList<Automaton>)

Returns an automaton that accepts the concatenation of the languages of the given automata.

Complexity: linear in total number of states.

Declaration

public static Automaton Concatenate(IList<Automaton> l)

Parameters

Type	Name	Description
System.Collections.Generic.IList<Automaton>	l

Returns

Type	Description
Automaton

| Improve this Doc View Source

Determinize(Automaton)

Determinizes the given automaton.

Worst case complexity: exponential in number of states.

Declaration

public static void Determinize(Automaton a)

Parameters

Type	Name	Description
Automaton	a

| Improve this Doc View Source

Intersection(Automaton, Automaton)

Returns an automaton that accepts the intersection of the languages of the given automata. Never modifies the input automata languages.

Complexity: quadratic in number of states.

Declaration

public static Automaton Intersection(Automaton a1, Automaton a2)

Parameters

Type	Name	Description
Automaton	a1
Automaton	a2

Returns

Type	Description
Automaton

| Improve this Doc View Source

IsEmpty(Automaton)

Returns true if the given automaton accepts no strings.

Declaration

public static bool IsEmpty(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

IsEmptyString(Automaton)

Returns true if the given automaton accepts the empty string and nothing else.

Declaration

public static bool IsEmptyString(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

IsTotal(Automaton)

Returns true if the given automaton accepts all strings.

Declaration

public static bool IsTotal(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

Minus(Automaton, Automaton)

Returns a (deterministic) automaton that accepts the intersection of the language of a1 and the complement of the language of a2. As a side-effect, the automata may be determinized, if not already deterministic.

Complexity: quadratic in number of states (if already deterministic).

Declaration

public static Automaton Minus(Automaton a1, Automaton a2)

Parameters

Type	Name	Description
Automaton	a1
Automaton	a2

Returns

Type	Description
Automaton

| Improve this Doc View Source

Optional(Automaton)

Returns an automaton that accepts the union of the empty string and the language of the given automaton.

Complexity: linear in number of states.

Declaration

public static Automaton Optional(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
Automaton

| Improve this Doc View Source

Repeat(Automaton)

Returns an automaton that accepts the Kleene star (zero or more concatenated repetitions) of the language of the given automaton. Never modifies the input automaton language.

Complexity: linear in number of states.

Declaration

public static Automaton Repeat(Automaton a)

Parameters

Type	Name	Description
Automaton	a

Returns

Type	Description
Automaton

| Improve this Doc View Source

Repeat(Automaton, Int32)

Returns an automaton that accepts min or more concatenated repetitions of the language of the given automaton.

Complexity: linear in number of states and in min.

Declaration

public static Automaton Repeat(Automaton a, int min)

Parameters

Type	Name	Description
Automaton	a
System.Int32	min

Returns

Type	Description
Automaton

| Improve this Doc View Source

Repeat(Automaton, Int32, Int32)

Returns an automaton that accepts between min and max (including both) concatenated repetitions of the language of the given automaton.

Complexity: linear in number of states and in min and max.

Declaration

public static Automaton Repeat(Automaton a, int min, int max)

Parameters

Type	Name	Description
Automaton	a
System.Int32	min
System.Int32	max

Returns

Type	Description
Automaton

| Improve this Doc View Source

Run(Automaton, String)

Returns true if the given string is accepted by the automaton.

Complexity: linear in the length of the string.

Note: for full performance, use the RunAutomaton class.

Declaration

public static bool Run(Automaton a, string s)

Parameters

Type	Name	Description
Automaton	a
System.String	s

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

SameLanguage(Automaton, Automaton)

Returns true if these two automata accept exactly the same language. This is a costly computation! Note also that a1 and a2 will be determinized as a side effect.

Declaration

public static bool SameLanguage(Automaton a1, Automaton a2)

Parameters

Type	Name	Description
Automaton	a1
Automaton	a2

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

SubsetOf(Automaton, Automaton)

Returns true if the language of a1 is a subset of the language of a2. As a side-effect, a2 is determinized if not already marked as deterministic.

Complexity: quadratic in number of states.

Declaration

public static bool SubsetOf(Automaton a1, Automaton a2)

Parameters

Type	Name	Description
Automaton	a1
Automaton	a2

Returns

Type	Description
System.Boolean

| Improve this Doc View Source

Union(Automaton, Automaton)

Returns an automaton that accepts the union of the languages of the given automata.

Complexity: linear in number of states.

Declaration

public static Automaton Union(Automaton a1, Automaton a2)

Parameters

Type	Name	Description
Automaton	a1
Automaton	a2

Returns

Type	Description
Automaton

| Improve this Doc View Source

Union(ICollection<Automaton>)

Returns an automaton that accepts the union of the languages of the given automata.

Complexity: linear in number of states.

Declaration

public static Automaton Union(ICollection<Automaton> l)

Parameters

Type	Name	Description
System.Collections.Generic.ICollection<Automaton>	l

Returns

Type	Description
Automaton