Represents nondeterministic finite automata with ε-moves. More...

#include <nfa.h>

Classes
struct	equal_to_reference_string_const
	Provides std::unordered_set::key_eq for state_set. More...

struct	hash_reference_string_const
	Provides std::unordered_set::hash_function for state_set. More...

struct	impl
	Private implementation details of NFAs. More...

Public Types
typedef std::unordered_set< std::reference_wrapper< std::string const >, hash_reference_string_const, equal_to_reference_string_const >	state_set
	Nicer name for sets of names of states. Should store references to existing state names. More...

Public Member Functions
	nfa ()
	Constructs an NFA accepting the empty language ∅. More...

	nfa (std::vector< char32_t > &&alphabet, std::vector< std::vector< std::valarray< bool >>> &&transitions, std::vector< std::string > &&labels, std::valarray< bool > &&acceptingStates)
	Constructs NFA with a private implementation object with provided members. More...

	nfa (fabuilder &b)
	Constructs an NFA from a builder by calling its buils method. More...

	nfa (nfa const &n)
	Copy-constructs an NFA by copying another one's private implementation object. More...

	nfa (nfa &&n)
	Move-constructs an NFA by stealing another one's private implementation object. More...

nfa &	operator= (nfa const &n)
	Copy-assigns this NFA by copying another one's private implementation object. More...

nfa &	operator= (nfa &&n)
	Move-assigns this NFA by stealing another one's private implementation object. More...

	operator dfa const & () const
	Returns a DFA accepting the same language as this NFA. More...

bool	operator== (nfa const &n) const
	Checks whether this NFA describes the same regular language as another object. More...

bool	operator!= (nfa const &n) const
	Checks whether this NFA describes a different regular language than another object. More...

std::valarray< bool > const &	delta (size_t qi, size_t si) const
	Computes this NFA's transition function for a state index and a symbol index. More...

std::valarray< bool > const &	delta (size_t qi, std::string const &symbol) const
	Computes this NFA's transition function for a state index and a UTF-8-encoded symbol. More...

state_set	delta (std::string const &q, std::string const &symbol) const
	Computes this NFA's transition function for a state label and a UTF-8-encoded symbol. More...

std::valarray< bool > const &	delta_ (size_t qi, char32_t u32symbol) const
	Computes this NFA's transition function for a state index and a UTF-32-encoded symbol. More...

state_set	delta_ (std::string const &q, char32_t u32symbol) const
	Computes this NFA's transition function for a state index and a UTF-32-encoded symbol. More...

std::valarray< bool >	deltaHat (size_t qi, std::string const &word) const
	Computes this DFA's transition function recursively for a UTF-8-encoded string of symbols, starting in a state specified by its index. More...

state_set	deltaHat (std::string const &q, std::string const &word) const
	Computes this NFA's transition function recursively for a UTF-8-encoded string of symbols, starting in a state specified by its name. More...

std::valarray< bool >	deltaHat (std::valarray< bool > const &qs, std::string const &word) const
	Computes this NFA's transition function recursively for a string of UTF-8-encoded symbols, starting in multiple specified states. More...

state_set	deltaHat (state_set const &qs, std::string const &word) const
	Computes this NFA's transition function recursively for a string of UTF-8-encoded symbols, starting in multiple states specified by their names. More...

std::valarray< bool >	deltaHat_ (size_t qi, std::u32string const &u32word) const
	Computes this NFA's transition function recursively for a string of symbols, starting in a state specified by its index. More...

state_set	deltaHat_ (std::string const &q, std::u32string const &u32word) const
	Computes this NFA's transition function recursively for a string of symbols, starting in a state specified by its name. More...

std::valarray< bool >	deltaHat_ (std::valarray< bool > const &qs, std::u32string const &u32word) const
	Computes this NFA's transition function recursively for a string of UTF-32-encoded symbols, starting in multiple specified states. More...

state_set	deltaHat_ (state_set const &qs, std::u32string const &u32word) const
	Computes this NFA's transition function recursively for a string of UTF-32-encoded symbols, starting in multiple states specified by their names. More...

std::valarray< bool > const &	epsilonClosure (size_t qi) const
	Computes a state's ε-closure. More...

state_set	epsilonClosure (std::string const &q) const
	Computes a state's ε-closure. More...

std::valarray< bool >	epsilonClosure (std::valarray< bool > const &qs) const
	Computes the union of multiple states' ε-closures. More...

state_set	epsilonClosure (state_set const &qs) const
	Computes the union of multiple states' ε-closures. More...

std::string	to_string (std::valarray< bool > const &qs) const
	Puts a name to a set of indices. More...

std::string	to_string (state_set const &qs) const
	Puts a name to a set of states. More...

state_set	decodeSet (std::valarray< bool > const &qs) const
	Translates a set of states from bool to set representation. More...

std::valarray< bool >	encodeSet (state_set const &qs) const
	Translates a set of states from set to bool representation. More...

std::string const &	getInitialState () const
	Names this NFA's initial state. More...

std::vector< std::string > const &	getStates () const
	Fetches this NFA's set of states in order of internal representation. More...

state_set	getStatesSet () const
	Fetches this NFA's set of states as a set of (references to) strings. More...

std::valarray< bool >	getStatesBools () const
	Fetches this NFA's set of states encoded as an array of bools. More...

std::vector< std::string > const &	getAlphabet () const
	Fetches this NFA's set of processable symbols as UTF-8-encoded strings. More...

std::vector< char32_t > const &	getAlphabet_ () const
	Fetches this NFA's set of processable symbols. More...

bool	isAccepting (size_t qi) const
	Tests whether a state is an accept state within this NFA. More...

bool	isAccepting (std::string const &q) const
	Tests whether a state is an accept state within this NFA. More...

bool	isAccepting (std::valarray< bool > const &qs) const
	Tests whether a set of states contains an accept state within this NFA. More...

bool	isAccepting (state_set const &qs) const
	Tests whether a set of states contains an accept state within this NFA. More...

Static Public Member Functions
static fabuilder	unite (nfa const &n1, nfa const &n2)
	Creates a builder for an NFA accepting the union of the languages of two NFAs. More...

static fabuilder	intersect (nfa const &n1, nfa const &n2)
	Creates a builder for an NFA accepting the intersection of the languages of two NFAs. More...

static fabuilder	subtract (nfa const &n1, nfa const &n2)
	Creates a builder for an NFA accepting the set difference of the languages of two NFAs. More...

static fabuilder	complement (nfa const &n)
	Creates a builder for an NFA accepting the complement of the language of an NFA. More...

Friends
std::string	findShortestWord (nfa const &n)
	Same as above for a UTF-8-encoded word. More...

std::u32string	findShortestWord_ (nfa const &n)
	Searches the shortest UTF-32-encoded word accepted by a given NFA. More...

Detailed Description

Represents nondeterministic finite automata with ε-moves.

Instances of this class are completely immutable. The builder class is the preferred means to construct NFAs.

By convention, the state with index 0 is the initial state.

Definition at line 38 of file nfa.h.

Member Typedef Documentation

◆ state_set

typedef std::unordered_set< std::reference_wrapper<std::string const>, hash_reference_string_const, equal_to_reference_string_const> reg::nfa::state_set

Nicer name for sets of names of states. Should store references to existing state names.

Definition at line 41 of file nfa.h.

Constructor & Destructor Documentation

◆ nfa() [1/5]

reg::nfa::nfa ( )

Constructs an NFA accepting the empty language ∅.

Definition at line 93 of file nfa.cpp.

◆ nfa() [2/5]

reg::nfa::nfa	(	std::vector< char32_t > &&	alphabet,
		std::vector< std::vector< std::valarray< bool >>> &&	transitions,
		std::vector< std::string > &&	labels,
		std::valarray< bool > &&	acceptingStates
	)

Constructs NFA with a private implementation object with provided members.

Definition at line 101 of file nfa.cpp.

◆ nfa() [3/5]

reg::nfa::nfa ( fabuilder & b )

Constructs an NFA from a builder by calling its buils method.

Definition at line 97 of file nfa.cpp.

◆ nfa() [4/5]

reg::nfa::nfa ( nfa const & n )

Copy-constructs an NFA by copying another one's private implementation object.

Definition at line 775 of file nfa.cpp.

◆ nfa() [5/5]

reg::nfa::nfa ( nfa && n )

Move-constructs an NFA by stealing another one's private implementation object.

The other NFA will be accepting the empty language ∅ afterwards.

Definition at line 780 of file nfa.cpp.

Member Function Documentation

◆ complement()

fabuilder reg::nfa::complement ( nfa const & n )

static

Creates a builder for an NFA accepting the complement of the language of an NFA.

The input NFAs' state names will probably be mangled in the created NFA.

Parameters

n the NFA

Returns: builder for an NFA accepting all words not accepted by the input NFA (provided they can be built from symbols of that NFA's alphabet)

Definition at line 769 of file nfa.cpp.

◆ decodeSet()

nfa::state_set reg::nfa::decodeSet ( std::valarray< bool > const & qs ) const

Translates a set of states from bool to set representation.

Parameters

qs	valarray with `true` at indices of states in question

Returns: set of labels of the states in question

Definition at line 538 of file nfa.cpp.

◆ delta() [1/3]

valarray< bool > const & reg::nfa::delta	(	size_t	qi,
		size_t	si
	)		const

Computes this NFA's transition function for a state index and a symbol index.

Parameters

qi	the state's index (< getStates()`.size()`)
si	index of the symbol to process (< getAlphabet()`.size()`)

Returns: valarray with true at reached states' indices

Exceptions

state_not_found	if `qi` ≥ getStates()`.size()`
symbol_not_found	if `si` ≥ getAlphabet()`.size()`

Definition at line 146 of file nfa.cpp.

◆ delta() [2/3]

valarray< bool > const & reg::nfa::delta	(	size_t	qi,
		std::string const &	symbol
	)		const

Computes this NFA's transition function for a state index and a UTF-8-encoded symbol.

This converts symbol to UTF-32 and calls delta_(size_t,char32_t) const with the std::u32string's first char32_t. If you don't want that overhead and already have a char32_t on your hands, use that method.

Parameters

qi	the state's index (< getStates()`.size()`)
symbol	the symbol to process (∈ getAlphabet())

Returns: valarray with true at reached states' indices

Exceptions

state_not_found	if `qi` ≥ getStates()`.size()`
symbol_not_found	if `symbol` ∉ getAlphabet()

Definition at line 193 of file nfa.cpp.

◆ delta() [3/3]

nfa::state_set reg::nfa::delta	(	std::string const &	q,
		std::string const &	symbol
	)		const

Computes this NFA's transition function for a state label and a UTF-8-encoded symbol.

This converts symbol to UTF-32 and calls delta_(std::string const&,char32_t) const with the std::u32string's first char32_t. If you don't want that overhead and already have a char32_t on your hands, use that method.

Parameters

q	the state's label (∈ getStates())
symbol	the symbol to process (∈ getAlphabet())

Returns: set of reached states' labels

Exceptions

state_not_found	if `q` ∉ getStates()
symbol_not_found	if `symbol` ∉ getAlphabet()

Definition at line 234 of file nfa.cpp.

◆ delta_() [1/2]

valarray< bool > const & reg::nfa::delta_	(	size_t	qi,
		char32_t	u32symbol
	)		const

Computes this NFA's transition function for a state index and a UTF-32-encoded symbol.

This looks up the index_of u32symbol within getAlphabet_() and calls delta(size_t, size_t) const. If you don't want that overhead and already have a symbol index on your hands, use that method.

Parameters

qi	the state's index (< getStates()`.size()`)
u32symbol	the symbol to process (∈ getAlphabet_())

Returns: valarray with true at reached states' indices

Exceptions

state_not_found	if `qi` ≥ getStates()`.size()`
symbol_not_found	if `u32symbol` ∉ getAlphabet_()

Definition at line 170 of file nfa.cpp.

◆ delta_() [2/2]

nfa::state_set reg::nfa::delta_	(	std::string const &	q,
		char32_t	u32symbol
	)		const

Computes this NFA's transition function for a state index and a UTF-32-encoded symbol.

This looks up the index_of q within getStates() and calls delta_(size_t,char32_t) const. If you don't want that overhead and already have a state index on your hands, use that method.

Parameters

q	the state's label (∈ getStates)
u32symbol	the symbol to process (∈ getAlphabet_())

Returns: set of reached states' labels

Exceptions

state_not_found	if `qi` ≥ getStates()`.size()`
symbol_not_found	if `u32symbol` ∉ getAlphabet_()

Definition at line 211 of file nfa.cpp.

◆ deltaHat() [1/4]

valarray< bool > reg::nfa::deltaHat	(	size_t	qi,
		std::string const &	word
	)		const

Computes this DFA's transition function recursively for a UTF-8-encoded string of symbols, starting in a state specified by its index.

This converts word to UTF-32 and calls deltaHat_(size_t, std::u32string const&) const. If you don't want that overhead and already have a std::u32string on your hands, use that method.

Parameters

qi	the starting state's index (< getStates()`.size()`)
word	the string of symbols to process (all of which ∈ getAlphabet())

Returns: valarray with true at reached states' indices

Exceptions

state_not_found	if `qi` ≥ getStates()`.size()`
symbol_not_found	if one of the `word` symbols ∉ getAlphabet()

Definition at line 275 of file nfa.cpp.

◆ deltaHat() [2/4]

nfa::state_set reg::nfa::deltaHat	(	std::string const &	q,
		std::string const &	word
	)		const

Computes this NFA's transition function recursively for a UTF-8-encoded string of symbols, starting in a state specified by its name.

This converts word to UTF-32 and calls deltaHat_(std::string const&, std::u32string const&) const. If you don't want that overhead and already have a std::u32string on your hands, use that method.

Parameters

q	the starting state's label (∈ getStates())
word	the string of symbols to process (all of which ∈ getAlphabet())

Returns: set of reached states' labels

Exceptions

state_not_found	if `q` ∉ getStates()
symbol_not_found	if one of the `word` symbols ∉ getAlphabet()

Definition at line 319 of file nfa.cpp.

◆ deltaHat() [3/4]

valarray< bool > reg::nfa::deltaHat	(	std::valarray< bool > const &	qs,
		std::string const &	word
	)		const

Computes this NFA's transition function recursively for a string of UTF-8-encoded symbols, starting in multiple specified states.

This converts word to UTF-32 and calls deltaHat_(std::valarray<bool> const&, std::u32string const&) const. If you don't want that overhead and already have a std::u32string on your hands, use that method.

Parameters

qs	valarray with `true` at starting states' indices
word	the string of symbols to process (all of which ∈ getAlphabet())

Returns: valarray with true at reached states' indices

Exceptions

symbol_not_found if one of the word symbols ∉ getAlphabet()

Definition at line 365 of file nfa.cpp.

◆ deltaHat() [4/4]

nfa::state_set reg::nfa::deltaHat	(	nfa::state_set const &	qs,
		std::string const &	word
	)		const

Computes this NFA's transition function recursively for a string of UTF-8-encoded symbols, starting in multiple states specified by their names.

This converts word to UTF-32 and calls deltaHat_(std::valarray<bool> const&, std::u32string const&) const. If you don't want that overhead and already have a std::u32string on your hands, use that method.

Parameters

qs	set of starting states' labels
word	the string of symbols to process (all of which ∈ getAlphabet_())

Returns: set of reached states' labels

Exceptions

symbol_not_found if one of the u32word symbols ∉ getAlphabet_()

Definition at line 406 of file nfa.cpp.

◆ deltaHat_() [1/4]

valarray< bool > reg::nfa::deltaHat_	(	size_t	qi,
		std::u32string const &	u32word
	)		const

Computes this NFA's transition function recursively for a string of symbols, starting in a state specified by its index.

Parameters

qi	the starting state's index (< getStates()`.size()`)
u32word	the string of symbols to process (all of which ∈ getAlphabet_())

Returns: valarray with true at reached states' indices

Exceptions

state_not_found	if `qi` ≥ getStates()`.size()`
symbol_not_found	if one the `u32word` symbols ∉ getAlphabet_()

Definition at line 250 of file nfa.cpp.

◆ deltaHat_() [2/4]

nfa::state_set reg::nfa::deltaHat_	(	std::string const &	q,
		std::u32string const &	u32word
	)		const

Computes this NFA's transition function recursively for a string of symbols, starting in a state specified by its name.

This looks up the index_of q within getStates() and calls deltaHat_(size_t,std::u32string const&) const. If you don't want that overhead and already have a state index on your hands, use that method.

Parameters

q	the starting state's label (∈ getStates())
u32word	the string of symbols to process (all of which ∈ getAlphabet_())

Returns: set of reached states' labels

Exceptions

state_not_found	if `q` ∉ getStates
symbol_not_found	if one the `u32word` symbols ∉ getAlphabet_()

Definition at line 295 of file nfa.cpp.

◆ deltaHat_() [3/4]

valarray< bool > reg::nfa::deltaHat_	(	std::valarray< bool > const &	qs,
		std::u32string const &	u32word
	)		const

Computes this NFA's transition function recursively for a string of UTF-32-encoded symbols, starting in multiple specified states.

Parameters

qs	valarray with `true` at starting states' indices
u32word	the string of symbols to process (all of which ∈ getAlphabet_())

Returns: valarray with true at reached states' indices

Exceptions

symbol_not_found if one of the u32word symbols ∉ getAlphabet_()

Definition at line 333 of file nfa.cpp.

◆ deltaHat_() [4/4]

nfa::state_set reg::nfa::deltaHat_	(	nfa::state_set const &	qs,
		std::u32string const &	u32word
	)		const

Computes this NFA's transition function recursively for a string of UTF-32-encoded symbols, starting in multiple states specified by their names.

This encodes qs in a std::valarray<bool> and calls deltaHat_(std::valarray<bool> const&, std::u32string const&) const. If you don't want that overhead and already have a std::valarray<bool> on your hands, use that method.

Parameters

qs	set of starting states' labels
u32word	the string of symbols to process (all of which ∈ getAlphabet_())

Returns: set of reached states' labels

Exceptions

symbol_not_found if one of the u32word symbols ∉ getAlphabet_()

Definition at line 386 of file nfa.cpp.

◆ encodeSet()

valarray< bool > reg::nfa::encodeSet ( nfa::state_set const & qs ) const

Translates a set of states from set to bool representation.

Parameters

qs	set of labels of the states in question

Returns: valarray with true at indices of states in question

Definition at line 555 of file nfa.cpp.

◆ epsilonClosure() [1/4]

valarray< bool > const & reg::nfa::epsilonClosure ( size_t qi ) const

Computes a state's ε-closure.

Parameters

qi	the state's index (< getStates()`.size()`)

Returns: valarray with true at indices of states reachable without actual inputs

Exceptions

state_not_found if qi ≥ getStates().size()

Definition at line 418 of file nfa.cpp.

◆ epsilonClosure() [2/4]

nfa::state_set reg::nfa::epsilonClosure ( std::string const & q ) const

Computes a state's ε-closure.

This looks up the index_of q within getStates() and calls epsilonClosure(size_t) const. If you don't want that overhead and already have a state index on your hands, use that method.

Parameters

q	the state's label (∈ getStates)

Returns: set of labels of states reachable without actual inputs

Exceptions

state_not_found if q ≥ getStates().size()

Definition at line 461 of file nfa.cpp.

◆ epsilonClosure() [3/4]

valarray< bool > reg::nfa::epsilonClosure ( std::valarray< bool > const & qs ) const

Computes the union of multiple states' ε-closures.

Parameters

qs	valarray with `true` at indices of states in question

Returns: valarray with true at indices of states reachable without actual inputs

Definition at line 475 of file nfa.cpp.

◆ epsilonClosure() [4/4]

nfa::state_set reg::nfa::epsilonClosure ( nfa::state_set const & qs ) const

Computes the union of multiple states' ε-closures.

This encodes qs in a std::valarray<bool> and calls epsilonClosure(std::valarray<bool> const&) const. If you don't want that overhead and already have a std::valarray<bool> on your hands, use that method.

Parameters

qs	set of labels of states in question

Returns: set of labels of states reachable without actual inputs

Definition at line 496 of file nfa.cpp.

◆ getAlphabet()

vector< string > const & reg::nfa::getAlphabet ( ) const

Fetches this NFA's set of processable symbols as UTF-8-encoded strings.

Returns: a vector containing all the valid symbol inputs for delta and deltaHat

Definition at line 605 of file nfa.cpp.

◆ getAlphabet_()

vector< char32_t > const & reg::nfa::getAlphabet_ ( ) const

Fetches this NFA's set of processable symbols.

Returns: a vector containing all the valid symbol inputs for delta and deltaHat

Definition at line 598 of file nfa.cpp.

◆ getInitialState()

string const & reg::nfa::getInitialState ( ) const

Names this NFA's initial state.

Returns: the initial state's name

Definition at line 567 of file nfa.cpp.

◆ getStates()

vector< string > const & reg::nfa::getStates ( ) const

Fetches this NFA's set of states in order of internal representation.

Returns: a vector containing the names of states that can be used as input for delta and deltaHat

Definition at line 574 of file nfa.cpp.

◆ getStatesBools()

valarray< bool > reg::nfa::getStatesBools ( ) const

Fetches this NFA's set of states encoded as an array of bools.

Returns: an array of length getStates().size(), filled with true values

Definition at line 589 of file nfa.cpp.

◆ getStatesSet()

nfa::state_set reg::nfa::getStatesSet ( ) const

Fetches this NFA's set of states as a set of (references to) strings.

Returns: a set containing references to the original state names

Definition at line 580 of file nfa.cpp.

◆ intersect()

fabuilder reg::nfa::intersect	(	nfa const &	n1,
		nfa const &	n2
	)

static

Creates a builder for an NFA accepting the intersection of the languages of two NFAs.

The input NFAs' state names will be concatenated and collisions resolved by appending _ in the created NFA.

Parameters

n1	the first NFA
n2	the other NFA

Returns: builder for an NFA accepting all the words accepted by both of the input NFAs

Definition at line 736 of file nfa.cpp.

◆ isAccepting() [1/4]

bool reg::nfa::isAccepting ( size_t qi ) const

Tests whether a state is an accept state within this NFA.

Parameters

qi	the state's index (< getStates()`.size()`)

Returns: true if the state is in the set of accept states, false else

Exceptions

state_not_found if qi ≥ getStates().size()

Definition at line 613 of file nfa.cpp.

◆ isAccepting() [2/4]

bool reg::nfa::isAccepting ( std::string const & q ) const

Tests whether a state is an accept state within this NFA.

Parameters

q	the state's label (∈ getStates)

Returns: true if the state is in the set of accept states, false else

Exceptions

state_not_found if q ∉ getStates

Definition at line 626 of file nfa.cpp.

◆ isAccepting() [3/4]

bool reg::nfa::isAccepting ( std::valarray< bool > const & qs ) const

Tests whether a set of states contains an accept state within this NFA.

Parameters

qs	valarray with `true` at indices of states in question

Returns: true if the set of states contains an accept states, false else

Definition at line 639 of file nfa.cpp.

◆ isAccepting() [4/4]

bool reg::nfa::isAccepting ( nfa::state_set const & qs ) const

Tests whether a set of states contains an accept state within this NFA.

This encodes qs in a std::valarray<bool> and calls isAccepting(std::valarray<bool> const&) const. If you don't want that overhead and already have a std::valarray<bool> on your hands, use that method.

Parameters

qs	set of labels of states in question

Returns: true if the set of states contains an accept states, false else

Definition at line 659 of file nfa.cpp.

◆ operator dfa const &()

reg::nfa::operator dfa const & ( ) const

Returns a DFA accepting the same language as this NFA.

◆ operator!=()

bool reg::nfa::operator!= ( nfa const & n ) const

Checks whether this NFA describes a different regular language than another object.

Returns: false if this NFA's language is exactly the same as the other object's, true else

Definition at line 133 of file nfa.cpp.

◆ operator=() [1/2]

nfa & reg::nfa::operator= ( nfa const & n )

Copy-assigns this NFA by copying another one's private implementation object.

Definition at line 784 of file nfa.cpp.

◆ operator=() [2/2]

nfa & reg::nfa::operator= ( nfa && n )

Move-assigns this NFA by stealing another one's private implementation object.

The other NFA will be accepting the empty language ∅ afterwards.

Definition at line 794 of file nfa.cpp.

◆ operator==()

bool reg::nfa::operator== ( nfa const & n ) const

Checks whether this NFA describes the same regular language as another object.

Returns: false if this NFA's language is exactly the same as the other object's, true else

Definition at line 123 of file nfa.cpp.

◆ subtract()

fabuilder reg::nfa::subtract	(	nfa const &	n1,
		nfa const &	n2
	)

static

Creates a builder for an NFA accepting the set difference of the languages of two NFAs.

The input NFAs' state names will probably be mangled in the created NFA.

Parameters

n1	the first NFA
n2	the other NFA

Returns: builder for an NFA accepting all the words accepted by the first but not the other input NFA

Definition at line 750 of file nfa.cpp.

◆ to_string() [1/2]

string reg::nfa::to_string ( std::valarray< bool > const & qs ) const

Puts a name to a set of indices.

Parameters

qs	valarray with `true` at indices of states in question

Returns: a comma-separated list of the states' names, surrounded by curly brackets

Definition at line 506 of file nfa.cpp.

◆ to_string() [2/2]

string reg::nfa::to_string ( nfa::state_set const & qs ) const

Puts a name to a set of states.

Parameters

qs	set of labels of states in question

Returns: a comma-separated list of the states' names, surrounded by curly brackets

Definition at line 529 of file nfa.cpp.

◆ unite()

fabuilder reg::nfa::unite	(	nfa const &	n1,
		nfa const &	n2
	)

static

Creates a builder for an NFA accepting the union of the languages of two NFAs.

Concatenates the names of states defined so far with the other NFA's state names and resolves conflicts by appending _.

Parameters

n1	the first NFA
n2	the other NFA

Returns: builder for an NFA accepting all the words accepted by any of the input NFAs

Definition at line 721 of file nfa.cpp.

Friends And Related Function Documentation

◆ findShortestWord

std::string findShortestWord ( nfa const & n )

friend

Same as above for a UTF-8-encoded word.

Definition at line 706 of file nfa.cpp.

◆ findShortestWord_

std::u32string findShortestWord_ ( nfa const & n )

friend

Searches the shortest UTF-32-encoded word accepted by a given NFA.

Parameters

n the NFA

Returns: the shortest word leading to one of the NFA's accept states

Exceptions

std::logic_error if the NFA doesn't accept any words

Definition at line 674 of file nfa.cpp.

The documentation for this class was generated from the following files:

Classes

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ state_set

Constructor & Destructor Documentation

◆ nfa() [1/5]

◆ nfa() [2/5]

◆ nfa() [3/5]

◆ nfa() [4/5]

◆ nfa() [5/5]

Member Function Documentation

◆ complement()

◆ decodeSet()

◆ delta() [1/3]

◆ delta() [2/3]

◆ delta() [3/3]

◆ delta_() [1/2]

◆ delta_() [2/2]

◆ deltaHat() [1/4]

◆ deltaHat() [2/4]

◆ deltaHat() [3/4]

◆ deltaHat() [4/4]

◆ deltaHat_() [1/4]

◆ deltaHat_() [2/4]

◆ deltaHat_() [3/4]

◆ deltaHat_() [4/4]

◆ encodeSet()

◆ epsilonClosure() [1/4]

◆ epsilonClosure() [2/4]

◆ epsilonClosure() [3/4]

◆ epsilonClosure() [4/4]

◆ getAlphabet()

◆ getAlphabet_()

◆ getInitialState()

◆ getStates()

◆ getStatesBools()

◆ getStatesSet()

◆ intersect()

◆ isAccepting() [1/4]

◆ isAccepting() [2/4]

◆ isAccepting() [3/4]

◆ isAccepting() [4/4]

◆ operator dfa const &()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ subtract()

◆ to_string() [1/2]

◆ to_string() [2/2]

◆ unite()

Friends And Related Function Documentation

◆ findShortestWord

◆ findShortestWord_