Class Dfa

Deterministic finite automaton (DFA).

Inheritance

object

Dfa

Implements

IDfa

IFsa

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: Automata.Core

Assembly: Automata.Core.dll

Syntax

public class Dfa : IDfa, IFsa

Remarks

A DFA is a finite state machine that accepts or rejects finite sequences of symbols. It is always deterministic and does not contain epsilon transitions.

Constructors

Dfa()

Initializes a new instance of the Dfa class with an empty alphabet.

Declaration

public Dfa()

Dfa(MutableAlphabet)

Initializes a new instance of the Dfa class with the specified alphabet.

Declaration

public Dfa(MutableAlphabet alphabet)

Parameters

Type	Name	Description
MutableAlphabet	alphabet	Alphabet used by the DFA.

Properties

Alphabet

Alphabet used by the DFA.

Declaration

public MutableAlphabet Alphabet { get; }

Property Value

Type	Description
MutableAlphabet

FinalStates

Final states of the DFA.

Declaration

public IReadOnlySet<int> FinalStates { get; }

Property Value

Type	Description
IReadOnlySet<int>

InitialState

Initial state of the DFA.

Declaration

public int InitialState { get; }

Property Value

Type	Description
int

Remarks

Returns InvalidState if the DFA has no initial state.

IsEmpty

Indicates whether the DFA is empty. A DFA is considered empty if it has no initial state.

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

MaxState

Upper bound for the maximum state number in the DFA.

Declaration

public int MaxState { get; }

Property Value

Type	Description
int

Remarks

This value represents an upper limit for state numbers in the DFA. The actual maximum state number may be lower, as removed states are not tracked for performance reasons.

Methods

Accepts(IEnumerable<string>)

Indicates whether the DFA accepts the given sequence of symbols.

Declaration

public bool Accepts(IEnumerable<string> sequence)

Parameters

Type	Name	Description
IEnumerable<string>	sequence	Sequence of symbols to check.

Returns

Type	Description
bool	true iff the DFA accepts the sequence.

Remarks

The DFA processes each symbol in the sequence, transitioning between states according to its transition function. If the DFA reaches a final state after processing all symbols, the sequence is accepted.

Add(Transition)

Adds a transition to the DFA, ensuring it remains deterministic.

Declaration

public bool Add(Transition transition)

Parameters

Type	Name	Description
Transition	transition	Transition to add.

Returns

Type	Description
bool	true iff the transition was added.

Remarks

If adding the transition would introduce nondeterminism (i.e., a transition with the same from-state and symbol already exists), the new transition will not be added.

EpsilonTransitions()

Gets the epsilon transitions of the DFA, which is always empty.

Declaration

public IEnumerable<EpsilonTransition> EpsilonTransitions()

Returns

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

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.

Minimized()

Minimizes the DFA using Brzozowski's algorithm.

Declaration

public Dfa Minimized()

Returns

Type	Description
Dfa	A minimized DFA.

Remarks

This algorithm involves reversing the DFA, determinizing it, reversing it again, and determinizing it once more.

ReachableState(int, int)

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

Declaration

public int ReachableState(int fromState, int symbol)

Parameters

Type	Name	Description
int	fromState	State from which to start.
int	symbol	Symbol to transition on.

Returns

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

Reversed()

Creates a new NFA that recognizes the reverse of the language accepted by this DFA.

Declaration

public Nfa Reversed()

Returns

Type	Description
Nfa	An NFA representing the reversed DFA.

SetFinal(IEnumerable<int>, bool)

Sets the specified states as final states or removes them from the final states.

Declaration

public void SetFinal(IEnumerable<int> states, bool final = true)

Parameters

Type	Name	Description
IEnumerable<int>	states	States to set or remove as final states.
bool	final	If true, the states are added to the final states; otherwise, they are removed.

SetFinal(int, bool)

Sets the specified state as a final state or removes it from the final states.

Declaration

public void SetFinal(int state, bool final = true)

Parameters

Type	Name	Description
int	state	State to set or remove as a final state.
bool	final	If true, the state is added to the final states; otherwise, it is removed.

SetInitial(int)

Sets the initial state of the DFA, updating the maximum state number if necessary.

Declaration

public void SetInitial(int state)

Parameters

Type	Name	Description
int	state	State to set as the initial state.

State(int)

Returns a StateView of the given state.

Declaration

public StateView State(int fromState)

Parameters

Type	Name	Description
int	fromState	From state.

Returns

Type	Description
StateView	A StateView for the given state.

Remarks

This method provides a read-only view of the state transitions from the specified state. It is primarily for compatibility with contiguous memory representations like Cfa. When possible, use Transitions(int), which avoids memory allocation and has less overhead.

SymbolicTransitions()

Gets the transitions of the DFA.

Declaration

public IEnumerable<Transition> SymbolicTransitions()

Returns

Type	Description
IEnumerable<Transition>	An enumerable collection of transitions.

ToCFA()

Converts the DFA to a canonical finite automaton (CFA).

Declaration

public Cfa ToCFA()

Returns

Type	Description
Cfa	A CFA representing the DFA.

ToNFA()

Converts the DFA to a nondeterministic finite automaton (NFA).

Declaration

public Nfa ToNFA()

Returns

Type	Description
Nfa	An NFA representing the DFA.

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	State from which to start.
int	symbol	Symbol to transition on.

Returns

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

Transitions(int)

Returns the set of transitions from the given state.

Declaration

public SortedSet<Transition> Transitions(int fromState)

Parameters

Type	Name	Description
int	fromState	State from which to start.

Returns

Type	Description
SortedSet<Transition>	Set of transitions from the given state.

UnionWith(IEnumerable<Transition>)

Adds all provided transitions that are currently not present in the set.

Declaration

public void UnionWith(IEnumerable<Transition> transitions)

Parameters

Type	Name	Description
IEnumerable<Transition>	transitions	Transitions to add.

Implements

IDfa

IFsa