Class Dfa

Deterministic finite automaton (DFA).

Inheritance

object

Fsa

FsaDet

Dfa

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.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 : FsaDet

Remarks

A DFA is a finite state machine that accepts or rejects finite sequences of symbols.

· A DFA cannot contain epsilon transitions

· Any mutation of a DFA is guaranteed to preserve its deterministic property.

· Mutation can make certain states unreachable (contain Dead states).

Constructors

Dfa(Alphabet)

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

Declaration

public Dfa(Alphabet alphabet)

Parameters

Type	Name	Description
Alphabet	alphabet	Alphabet used by the DFA.

Dfa(Mfa)

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

The resulting DFA is not only isomorphic to the original MFA but also graphically identical, preserving identical state and transition IDs, and MaxState.

Declaration

public Dfa(Mfa mfa)

Parameters

Type	Name	Description
Mfa	mfa	The MFA to convert into a DFA.

Properties

FinalStates

Final states of the DFA.

Declaration

public override IReadOnlyCollection<int> FinalStates { get; }

Property Value

Type	Description
IReadOnlyCollection<int>

Overrides

Fsa.FinalStates

InitialState

Initial state of the DFA.

Declaration

public override int InitialState { get; }

Property Value

Type	Description
int

Overrides

FsaDet.InitialState

Remarks

Returns InvalidState if the DFA has no initial state.

MaxState

Upper limit for the maximum state number in the DFA.

A value (MaxState + 1) is guaranteed to be an unused state number.

Declaration

public override int MaxState { get; }

Property Value

Type	Description
int

Overrides

FsaDet.MaxState

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.

StateRange

Range encompassing all states of the automaton.

Declaration

public override Range StateRange { get; }

Property Value

Type	Description
Range

Overrides

FsaDet.StateRange

Remarks

All states lies inside this range; but contiguity of states is not guaranteed.

Exclusive End equals the minimal unused state ID.

Non-empty automata: StateRange = [0, MaxState + 1).

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

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.

ClearAll()

Clears all states and transitions. The DFA will be equivalent to the empty language (∅).

Declaration

public void ClearAll()

Remarks

The alphabet is not cleared.

CreateEmpty(Alphabet)

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

Declaration

public static Dfa CreateEmpty(Alphabet alphabet)

Parameters

Type	Name	Description
Alphabet	alphabet	Alphabet used by the MFA.

Returns

Type	Description
Dfa

CreateEpsilonAccepting(Alphabet)

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

Declaration

public static Dfa CreateEpsilonAccepting(Alphabet alphabet)

Parameters

Type	Name	Description
Alphabet	alphabet	Alphabet used by the DFA.

Returns

Type	Description
Dfa

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)

Minimal(bool)

Returns a new minimal DFA. Uses Hopcroft's algorithm as default.

Declaration

public Dfa Minimal(bool useHopcroftAlgorithm = true)

Parameters

Type	Name	Description
bool	useHopcroftAlgorithm	If true, uses Hopcroft's algorithm; otherwise, uses Brzozowski's algorithm.

Returns

Type	Description
Dfa	A new minimal DFA.

See Also

Minimal_Hopcroft()

Minimal_Brzozowski()

Minimal_Hopcroft()

Returns a new minimal DFA using Hopcroft's algorithm. Current instance will be trimmed (to only include states and transitions that are both accessible and co-accessible).

Declaration

public Dfa Minimal_Hopcroft()

Returns

Type	Description
Dfa	A new minimal DFA.

See Also

Trim()

Minimal_Brzozowski()

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

Exceptions

Type	Condition
ArgumentOutOfRangeException	fromState is negative.

Symbols(int)

Returns the set of symbols (no duplicates) for transitions from the specified state.

Declaration

public IEnumerable<int> Symbols(int fromState)

Parameters

Type	Name	Description
int	fromState	State from which to get the symbols.

Returns

Type	Description
IEnumerable<int>	An enumerable collection of symbols for transitions from the specified state.

ToCanonicalString()

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

Declaration

public override string ToCanonicalString()

Returns

Type	Description
string

Overrides

Fsa.ToCanonicalString()

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

Declaration

public override IReadOnlyCollection<Transition> Transitions()

Returns

Type	Description
IReadOnlyCollection<Transition>	An collection of transitions.

Overrides

Fsa.Transitions()

Trim()

Trim the DFA in-place to only include states and transitions that are both accessible and co-accessible. Thus, all states and transitions that are not on a path from the initial state to a final state are removed.

Declaration

public (HashSet<int> allStates, Transition[] reverseTransitions) Trim()

Returns

Type	Description
(HashSet<int> allStates, Transition[] reverseTransitions)	A tuple containing post-trim information: Remaining trimmed states. Remaining transitions in reversed form. This can be used for back-tracking in the DFA.

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.

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)