Class Cfa

Canonical Finite-state Automaton (CFA).

Inheritance

object

Cfa

Implements

IEquatable<Cfa>

IEnumerable<Transition>

IEnumerable

IDfa

IFsa

Inherited Members

object.Equals(object, object)

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: Automata.Core

Assembly: Automata.Core.dll

Syntax

public class Cfa : IEquatable<Cfa>, IEnumerable<Transition>, IEnumerable, IDfa, IFsa

Remarks

The Cfa is the most optimized automaton representation, characterized by:

1. Deterministic and Minimal: The least possible states and transitions (Similarly to a minimized DFA).
2. Canonical alphabet: Reduced, contiguous, and lexicographically ordered.
3. Canonical states and transitions: contiguously indexed, optimized, and fully ordered.
4. Immutable: Guarantees structural and behavioral invariance.
5. Performance-optimized for efficient read-only operations. Minimal memory footprint.

Key attribute for CFAs:

For any language, there exists exactly one specific Cfa.

Any two automata that accept the same language will, when converted, yield two Cfa that are precisely identical in all aspects.

Constructors

Cfa(IFsa)

Initializes a new instance of the Cfa class from an existing FSA.

Declaration

public Cfa(IFsa fsa)

Parameters

Type	Name	Description
IFsa	fsa	Finite state automaton to convert.

Fields

FinalStates

Final states of the CFA.

Declaration

public readonly FrozenSet<int> FinalStates

Field Value

Type	Description
FrozenSet<int>

StateCount

Number of states in the CFA.

Declaration

public readonly int StateCount

Field Value

Type	Description
int

Properties

Alphabet

Alphabet used by the CFA.

Declaration

public CanonicalAlphabet Alphabet { get; }

Property Value

Type	Description
CanonicalAlphabet

InitialState

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

For an empty Cfa, the initial state is InvalidState.

Declaration

public int InitialState { get; }

Property Value

Type	Description
int

IsEmpty

Indicates whether the CFA is empty.

Declaration

public bool IsEmpty { get; }

Property Value

Type	Description
bool

IsEpsilonFree

Indicates whether the DFA is epsilon-free. Always returns true.

Declaration

public bool IsEpsilonFree { get; }

Property Value

Type	Description
bool

TransitionCount

Number of transitions in the automaton.

Declaration

public int TransitionCount { get; }

Property Value

Type	Description
int

Methods

EpsilonTransitions()

Gets an enumerable collection of the epsilon transitions, which is always empty.

Declaration

public IEnumerable<EpsilonTransition> EpsilonTransitions()

Returns

Type	Description
IEnumerable<EpsilonTransition>	An empty enumerable collection of EpsilonTransition.

Equals(Cfa?)

Indicates language equivalence between two CFAs.

Declaration

public bool Equals(Cfa? other)

Parameters

Type	Name	Description
Cfa	other	Object to compare with this object.

Returns

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

Remarks

Equality means both CFAs accept the same language, but will due to the canonical property, also be identical.

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)

GetEnumerator()

Returns an enumerator that iterates through the transitions.

Declaration

public IEnumerator<Transition> GetEnumerator()

Returns

Type	Description
IEnumerator<Transition>	An enumerator for the transitions.

GetHashCode()

Hash code for the current alphabet.

Declaration

public override int GetHashCode()

Returns

Type	Description
int	A hash code for the alphabet.

Overrides

object.GetHashCode()

IsFinal(int)

Indicates whether the specified state is a final state.

Declaration

public 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.

IsInitial(int)

Indicates whether the specified state is the initial state.

Declaration

public bool IsInitial(int state)

Parameters

Type	Name	Description
int	state	State to check.

Returns

Type	Description
bool	true iff the specified state is the initial state.

State(int)

Returns a StateView for the given state.

Declaration

public StateView State(int state)

Parameters

Type	Name	Description
int	state	State.

Returns

Type	Description
StateView	A StateView containing the transitions from the given state.

SymbolicTransitions()

Gets an enumerable collection of the symbolic transitions.

Declaration

public IEnumerable<Transition> SymbolicTransitions()

Returns

Type	Description
IEnumerable<Transition>	An enumerable collection of Transition(int, int).

Transition(int, int)

Returns the transition from the given state with the given symbol.

Declaration

public Transition Transition(int fromState, int symbol)

Parameters

Type	Name	Description
int	fromState	Source state.
int	symbol	Symbol of the transition.

Returns

Type	Description
Transition	The transition from the given state with the given symbol, or Invalid if no such transition exists.

Operators

operator ==(Cfa, Cfa)

Indicates whether two specified instances of Cfa are equal.

Declaration

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

Parameters

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

Returns

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

operator !=(Cfa, Cfa)

Indicates whether two specified instances of Cfa are not equal.

Declaration

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

Parameters

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

Returns

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

Implements

IEquatable<T>

IEnumerable<T>

IEnumerable

IDfa

IFsa