Class Nfa

Nondeterministic finite automaton (NFA).

Inheritance

object

Fsa

Nfa

Inherited Members

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 Nfa : Fsa

Remarks

States are represented simply as integers (int), which essentially are just unique IDs.

NFAs are defined mainly by two sets of transitions (symbolic and epsilon), which are kept separate for performance.

In addition, there are two sets defining the initial states and final states respectively.

NFAs (in contrast to DFAs) can have multiple initial states.

Constructors

Nfa(Alphabet)

Initializes a new empty instance of the Nfa.

Declaration

public Nfa(Alphabet alphabet)

Parameters

Type	Name	Description
Alphabet	alphabet	Alphabet to use for the NFA.

Nfa(Nfa)

Initializes a new clone of given Nfa with a new cloned alphabet.

Declaration

public Nfa(Nfa nfa)

Parameters

Type	Name	Description
Nfa	nfa	NFA to clone.

Nfa(IEnumerable<IEnumerable<string>>)

Initializes a new instance of a Nfa class to accept a set of sequences.

Declaration

public Nfa(IEnumerable<IEnumerable<string>> sequences)

Parameters

Type	Name	Description
IEnumerable<IEnumerable<string>>	sequences	Sequences to add to the NFA.

Properties

AcceptsEpsilon

Indicates whether the NFA accepts ϵ - the empty sting.

Declaration

public override bool AcceptsEpsilon { get; }

Property Value

Type	Description
bool

Overrides

Fsa.AcceptsEpsilon

Remarks

Returns trueiff the NFA has a final state that is either an initial state or can be reached from an initial state on only epsilon transitions.

FinalStates

Final states of the NFA.

Declaration

public override IReadOnlyCollection<int> FinalStates { get; }

Property Value

Type	Description
IReadOnlyCollection<int>

Overrides

Fsa.FinalStates

HasInitialState

Indicates whether the NFA has any initial states.

Declaration

public override bool HasInitialState { get; }

Property Value

Type	Description
bool	true iff the NFA has at least one initial state.

Overrides

Fsa.HasInitialState

InitialStates

Initial states of the NFA.

Declaration

public IReadOnlySet<int> InitialStates { get; }

Property Value

Type	Description
IReadOnlySet<int>

IsEpsilonFree

Indicates whether the NFA is epsilon-free.

Declaration

public override bool IsEpsilonFree { get; }

Property Value

Type	Description
bool

Overrides

Fsa.IsEpsilonFree

MaxState

Upper bound for the maximum state number in the NFA.

Declaration

public int MaxState { get; }

Property Value

Type	Description
int

Remarks

This values denotes an upper bound for the state numbers in the NFA. The actual maximum state number may be lower (but not higher), since we do not keep track of removed states for performance reasons.

Methods

Add(EpsilonTransition)

Adds an epsilon transition to the NFA.

Declaration

public void Add(EpsilonTransition transition)

Parameters

Type	Name	Description
EpsilonTransition	transition	Transition to add.

Add(Transition)

Adds a symbolic (non-epsilon) transition to the NFA.

Declaration

public void Add(Transition transition)

Parameters

Type	Name	Description
Transition	transition	Transition to add.

AvailableSymbols(IEnumerable<int>)

Returns the set of symbols that can be used to transition directly from the given states.

Declaration

public IntSet AvailableSymbols(IEnumerable<int> fromStates)

Parameters

Type	Name	Description
IEnumerable<int>	fromStates	States from which to start.

Returns

Type	Description
IntSet	Set of symbols that can be used to transition directly from the given states.

ClearAll()

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

Declaration

public void ClearAll()

Remarks

The alphabet is not cleared.

ClearFinalStates()

Clears all final states.

Declaration

public void ClearFinalStates()

ClearInitialStates()

Clears all initial states.

Declaration

public void ClearInitialStates()

EpsilonTransitions()

Epsilon transitions of the DFA, which is always empty.

Declaration

public override IReadOnlyCollection<EpsilonTransition> EpsilonTransitions()

Returns

Type	Description
IReadOnlyCollection<EpsilonTransition>	A collection of EpsilonTransition.

Overrides

Fsa.EpsilonTransitions()

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; otherwise, false.

Overrides

Fsa.IsFinal(int)

IsInitial(int)

Indicates whether the specified state is an initial state.

Declaration

public override bool IsInitial(int state)

Parameters

Type	Name	Description
int	state	State to check.

Returns

Type	Description
bool	true iff the specified state is an initial state; otherwise, false.

Overrides

Fsa.IsInitial(int)

ReachableStates(IEnumerable<int>, int)

Returns the states reachable from the given states on the given symbol, including epsilon closures.

Declaration

public IntSet ReachableStates(IEnumerable<int> fromStates, int symbol)

Parameters

Type	Name	Description
IEnumerable<int>	fromStates	States from which to start.
int	symbol	Symbol to transition on.

Returns

Type	Description
IntSet	States reachable from the given states on the given symbol, including epsilon closures.

Exceptions

Type	Condition
ArgumentOutOfRangeException	symbol is negative.

ReachableStatesOnEpsilonInPlace(HashSet<int>)

Extends the provided set of states with their epsilon closure in place.

Declaration

public void ReachableStatesOnEpsilonInPlace(HashSet<int> fromStates)

Parameters

Type	Name	Description
HashSet<int>	fromStates	Set of states to extend.

Remarks

Epsilon closure is all reachable states on epsilon transitions.

ReachableStatesOnSingleEpsilon(int)

Returns the states reachable from the given state on a single epsilon transition. If the input state has an epsilon loop on itself, it will be included in the result.

Declaration

public IEnumerable<int> ReachableStatesOnSingleEpsilon(int fromState)

Parameters

Type	Name	Description
int	fromState	State from which to start.

Returns

Type	Description
IEnumerable<int>	States reachable from the given state on a single epsilon transition.

Exceptions

Type	Condition
ArgumentOutOfRangeException	fromState is negative.

ReachableStatesOnSingleSymbol(int, int)

Returns the states reachable from the given state with the given symbol.

Declaration

public IEnumerable<int> ReachableStatesOnSingleSymbol(int fromState, int symbol)

Parameters

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

Returns

Type	Description
IEnumerable<int>	States reachable from the given state on the given symbol.

Exceptions

Type	Condition
ArgumentOutOfRangeException	fromState or symbol is negative.

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(IEnumerable<int>, bool)

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

Declaration

public void SetInitial(IEnumerable<int> states, bool initial = true)

Parameters

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

SetInitial(int, bool)

Sets the specified state as an initial state or removes it from the initial states.

Declaration

public void SetInitial(int state, bool initial = true)

Parameters

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

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

Transitions()

Transitions of the DFA.

Declaration

public override IReadOnlyCollection<Transition> Transitions()

Returns

Type	Description
IReadOnlyCollection<Transition>	A collection of transitions.

Overrides

Fsa.Transitions()

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.

Exceptions

Type	Condition
ArgumentOutOfRangeException	fromState is negative.

Transitions(int, int)

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

Declaration

public SortedSet<Transition> Transitions(int fromState, int symbol)

Parameters

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

Returns

Type	Description
SortedSet<Transition>	Transitions from the given state on the given symbol.

Exceptions

Type	Condition
ArgumentOutOfRangeException	fromState or symbol is negative.

UnionWith(IEnumerable<EpsilonTransition>)

Adds multiple epsilon transitions to the NFA.

Declaration

public void UnionWith(IEnumerable<EpsilonTransition> transitions)

Parameters

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

UnionWith(IEnumerable<Transition>)

Adds multiple symbolic transitions to the NFA.

Declaration

public void UnionWith(IEnumerable<Transition> transitions)

Parameters

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

UnionWith(IEnumerable<IEnumerable<string>>)

Adds a set of sequences to be accepted by the NFA.

Declaration

public void UnionWith(IEnumerable<IEnumerable<string>> sequences)

Parameters

Type	Name	Description
IEnumerable<IEnumerable<string>>	sequences	Sequences to add to the NFA.

Remarks

Any missing symbols in the alphabet will be added to the alphabet.

UnionWith(IEnumerable<string>)

Adds a sequence of symbols to be accepted by the NFA.

Declaration

public void UnionWith(IEnumerable<string> sequence)

Parameters

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

Remarks

Any missing symbols in the alphabet will be added to the alphabet.

Extension Methods

Converter.AsDeterministic(Fsa)

Converter.AsMfa(Fsa)

Converter.AsNfa(Fsa)

Ops.ConcatenationWith(Nfa, FsaDet)

Ops.KleenePlusWith(Nfa)

Ops.KleeneStarWith(Nfa)

Ops.OptionWith(Nfa)

Ops.UnionWith(Nfa, FsaDet)