Class Nfa

Nondeterministic finite automaton (NFA).

Inheritance

object

Nfa

Implements

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

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

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

Declaration

public Nfa()

Nfa(MutableAlphabet)

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

Declaration

public Nfa(MutableAlphabet alphabet)

Parameters

Type	Name	Description
MutableAlphabet	alphabet	Alphabet used by the NFA.

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

Alphabet

Alphabet used by the NFA.

Declaration

public MutableAlphabet Alphabet { get; }

Property Value

Type	Description
MutableAlphabet

FinalStates

Final states of the NFA.

Declaration

public IReadOnlySet<int> FinalStates { get; }

Property Value

Type	Description
IReadOnlySet<int>

InitialStates

Initial states of the NFA.

Declaration

public IReadOnlySet<int> InitialStates { get; }

Property Value

Type	Description
IReadOnlySet<int>

IsEmpty

Indicates whether the NFA is empty.

Declaration

public bool IsEmpty { get; }

Property Value

Type	Description
bool

IsEpsilonFree

Indicates whether the NFA is epsilon-free.

Declaration

public bool IsEpsilonFree { get; }

Property Value

Type	Description
bool

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.

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

IsInitial(int)

Indicates whether the specified state is an 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 an initial state; otherwise, false.

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.

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.

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.

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.

ToCfa()

Converts the NFA to a CFA.

Declaration

public Cfa ToCfa()

Returns

Type	Description
Cfa	A CFA representing the NFA.

ToDfa()

Converts the NFA to a DFA.

Declaration

public Dfa ToDfa()

Returns

Type	Description
Dfa	A DFA representing the NFA.

ToMinimizedDFA()

Converts the NFA to a minimized DFA.

Declaration

public Dfa ToMinimizedDFA()

Returns

Type	Description
Dfa	A minimized DFA representing the NFA.

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.

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.

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.

Implements

IFsa