Class Mfa

Minimal Finite-state Automaton (MFA).

Inheritance

object

Fsa

FsaDet

Mfa

Implements

IEquatable<Mfa>

Inherited Members

FsaDet.IsEpsilonFree

FsaDet.AcceptsEpsilon

FsaDet.HasInitialState

FsaDet.IsInitial(int)

FsaDet.TryTransition(int, int, out int)

FsaDet.EpsilonTransitions()

FsaDet.Accepts(IEnumerable<int>)

FsaDet.Accepts(IEnumerable<string>)

FsaDet.StatePath(IEnumerable<int>)

FsaDet.StatePath(IEnumerable<string>)

Fsa.Alphabet

object.Equals(object, object)

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: Automata.Core

Assembly: Automata.Core.dll

Syntax

public class Mfa : FsaDet, IEquatable<Mfa>

Remarks

Mfa is the most optimized automaton representation, characterized by:

1. Deterministic and Minimal: The least possible states and transitions.
2. Minimal memory footprint: Uses a contiguous memory block for data, with minimal overhead.
3. Performance-optimized for efficient readonly operations.
4. Immutable: Guarantees structural and behavioral invariance.
5. Contiguous states: States are in range [0..MaxState].
6. Initial state is always 0 for a non-empty Mfa.
7. Canonical topology: States and transitions are canonically ordered.
8. Two Mfas recognizing the same language are guaranteed to be identical.

Constructors

Mfa(Dfa)

Initializes a new instance of the Mfa class from an existing Dfa.

Declaration

public Mfa(Dfa dfa)

Parameters

Type	Name	Description
Dfa	dfa	A DFA to create from.

Mfa(string, Alphabet)

Creates a singleton Mfa that accepts only the single symbol once.

Declaration

public Mfa(string singleSymbol, Alphabet alphabet)

Parameters

Type	Name	Description
string	singleSymbol	Symbol to be accepted by the MFA.
Alphabet	alphabet	Alphabet used by the MFA.

Properties

FinalStates

Final states of the MFA.

Declaration

public override IReadOnlyCollection<int> FinalStates { get; }

Property Value

Type	Description
IReadOnlyCollection<int>

Overrides

Fsa.FinalStates

InitialState

Initial state. Always 0 for a non-empty Mfa.

For an empty Mfa, the initial state is InvalidState.

Declaration

public override int InitialState { get; }

Property Value

Type	Description
int

Overrides

FsaDet.InitialState

Remarks

An MFA without an initial state is completely empty (= IsEmptyLanguage).

IsEmptyLanguage

Indicates whether the language of the MFA is the empty language (∅). This means the MFA does not accept anything, including the empty string (ϵ).

Declaration

public bool IsEmptyLanguage { get; }

Property Value

Type	Description
bool

Remarks

Returns true only if either; the MFA has no states.

MaxState

The state number with the highest value.

Declaration

public override int MaxState { get; }

Property Value

Type	Description
int	The maximum state number, or InvalidState (= -1) if the MFA is empty (has no states).

Overrides

FsaDet.MaxState

StateCount

Number of states in the MFA.

Declaration

public int StateCount { get; }

Property Value

Type	Description
int

StateRange

Range covering all states in the automaton.

Declaration

public override Range StateRange { get; }

Property Value

Type	Description
Range

Overrides

FsaDet.StateRange

Remarks

States are contiguous without gaps; all states lie within this range. The exclusive End equals both StateCount and the next unused state ID.

For non-empty automata: StateRange = [0, StateCount).

For empty automata: StateRange = [−1, −1).

TransitionCount

Number of transitions in the automaton.

Declaration

public override int TransitionCount { get; }

Property Value

Type	Description
int

Overrides

FsaDet.TransitionCount

Methods

CreateEmpty(Alphabet)

Creates a Mfa that represents the empty language (∅), with a specified alphabet. The MFA has zero states and zero transitions.

Declaration

public static Mfa CreateEmpty(Alphabet alphabet)

Parameters

Type	Name	Description
Alphabet	alphabet	Alphabet used by the MFA.

Returns

Type	Description
Mfa

CreateEpsilonAccepting(Alphabet)

Creates a Mfa that represents the language {ϵ}, with a specified alphabet. The MFA has a single initial, final state and zero transitions.

Declaration

public static Mfa CreateEpsilonAccepting(Alphabet alphabet)

Parameters

Type	Name	Description
Alphabet	alphabet	Alphabet used by the MFA.

Returns

Type	Description
Mfa

CreateWildcard(Alphabet)

Returns an automaton that accepts one occurrence of any symbol in the specified alphabet. It corresponds directly to the "." in Alang expressions.

Declaration

public static Mfa CreateWildcard(Alphabet alphabet)

Parameters

Type	Name	Description
Alphabet	alphabet	Alphabet containing the set of symbols

Returns

Type	Description
Mfa	An automaton representing any symbol accepted exactly once.

Equals(Mfa?)

Indicates whether this MFA is equal to the specified MFA.

Declaration

public bool Equals(Mfa? other)

Parameters

Type	Name	Description
Mfa	other	MFA to compare with.

Returns

Type	Description
bool	true iff the current Mfa is equal to other.

Remarks

This method is similar to LanguageEquals(Mfa) but is stricter:

It also requires the alphabets of both MFAs to be equal (not just the referenced symbols).

See Also

LanguageEquals(Mfa)

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)

GetHashCode()

Hash code for the current MFA.

Declaration

public override int GetHashCode()

Returns

Type	Description
int	A hash code for the MFA.

Overrides

object.GetHashCode()

IsFinal(int)

Indicates whether the specified state is a final state.

Declaration

public override bool IsFinal(int state)

Parameters

Type	Name	Description
int	state	State to check.

Returns

Type	Description
bool	true iff the specified state is a final state.

Overrides

Fsa.IsFinal(int)

LanguageEquals(Mfa)

Indicates whether this MFA represent the exact same language as the specified MFA: Language Equality.

Declaration

public bool LanguageEquals(Mfa other)

Parameters

Type	Name	Description
Mfa	other	MFA to check language equality against.

Returns

Type	Description
bool	true iff the current Mfa represents the same language asother.

Remarks

Language Equality means both MFAs represent the same language. Due to the canonical property, Language Equality also means the MFAs are completely identical (identical states, and identical transition arrays).

The alphabets need however not need to be equal, but every referenced symbol must have the same index in both alphabets.

State(int)

Returns a view of the specified state.

Declaration

public override StateView State(int fromState)

Parameters

Type	Name	Description
int	fromState	The state origin.

Returns

Type	Description
StateView	A StateView for the given state.

Overrides

FsaDet.State(int)

ToCanonicalString()

Returns a canonical string representation of the MFA's data. Used by unit tests and for debugging.

Declaration

public override string ToCanonicalString()

Returns

Type	Description
string

Overrides

Fsa.ToCanonicalString()

Examples

Canonical string for a 2-state MFA, with 2 states, 2 transitions and 1 final state, that accepts the language {a | b}:

S#=2, F#=1: [1]: T#=2: [0->1 a, 0->1 b]

Transition(int, int)

Returns the state reachable from the given state on the given symbol.

Declaration

public override int Transition(int fromState, int symbol)

Parameters

Type	Name	Description
int	fromState	The state origin of the transition.
int	symbol	Symbol for the transition.

Returns

Type	Description
int	The state reachable from the given state on the given symbol. If no such transition exists, InvalidState is returned.

Overrides

FsaDet.Transition(int, int)

Exceptions

Type	Condition
ArgumentOutOfRangeException	fromState is negative.

See Also

TryTransition(int, int, out int)

Transitions()

Gets the transitions of the MFA.

Declaration

public override IReadOnlyCollection<Transition> Transitions()

Returns

Type	Description
IReadOnlyCollection<Transition>	An collection of transitions.

Overrides

Fsa.Transitions()

Operators

operator ==(Mfa, Mfa)

Indicates whether two specified instances of Mfa are equal.

Declaration

public static bool operator ==(Mfa left, Mfa right)

Parameters

Type	Name	Description
Mfa	left	First Mfa to compare.
Mfa	right	Second Mfa to compare.

Returns

Type	Description
bool	true iff the two Mfa instances are equal.

operator !=(Mfa, Mfa)

Indicates whether two specified instances of Mfa are not equal.

Declaration

public static bool operator !=(Mfa left, Mfa right)

Parameters

Type	Name	Description
Mfa	left	First Mfa to compare.
Mfa	right	Second Mfa to compare.

Returns

Type	Description
bool	false iff the two Mfa instances are not equal.

Implements

IEquatable<T>

Extension Methods

Converter.AsDeterministic(Fsa)

Converter.AsMfa(Fsa)

Converter.AsNfa(Fsa)

Ops.Difference(FsaDet, Mfa)

Ops.Intersection(FsaDet, FsaDet)

Ops.Overlaps(FsaDet, FsaDet)

Ops.Reversal(FsaDet)

Ops.Complement(Mfa)

Ops.PrefixClosure(Mfa)