Represents deterministic finite automata. More...

#include <dfa.h>

Classes
struct	impl
	Private implementation details of DFAs. More...

Public Member Functions
	dfa ()
	Constructs a DFA accepting the empty language ∅. More...

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

	dfa (fabuilder &b, bool force=false)
	Constructs a DFA from a builder by calling its build method. More...

	dfa (dfa const &d)
	Copy-constructs a DFA by copying another one's private implementation object. More...

	dfa (dfa &&d)
	Move-constructs a DFA by stealing another one's private implementation object. More...

dfa &	operator= (dfa const &d)
	Copy-assigns this DFA by copying another one's private implementation object. More...

dfa &	operator= (dfa &&d)
	Move-assigns this DFA by stealing another one's private implementation object. More...

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

bool	operator== (dfa const &d) const
	Tests whether this DFA accepts exactly the same language as another one. More...

bool	operator!= (dfa const &d) const
	Tests whether this DFA doesn't accept the same language as another one. More...

bool	operator== (nfa const &d) const
	Tests whether this DFA accepts exactly the same language as another object. More...

bool	operator!= (nfa const &d) const
	Tests whether this DFA doesn't accept the same language as another object. More...

size_t	delta (size_t qi, size_t si) const
	Computes this DFA's transition function for a state index and a symbol index. More...

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

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

size_t	delta_ (size_t qi, char32_t u32symbol) const
	Computes this DFA's transition function for a state index and a UTF-32-encoded symbol. More...

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

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

std::string const &	deltaHat (std::string const &q, 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 name. More...

size_t	deltaHat_ (size_t qi, std::u32string const &u32word) const
	Computes this DFA's transition function recursively for a UTF-32-encoded string of symbols, starting in a state specified by its index. More...

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

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

std::vector< std::string > const &	getStates () const
	Fetches this DFA's set of states. More...

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

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

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

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

Static Public Member Functions
static fabuilder	unite (dfa const &d1, dfa const &d2)
	Creates a builder for a DFA accepting the union of the languages of two DFAs. More...

static fabuilder	intersect (dfa const &d1, dfa const &d2)
	Creates a builder for a DFA accepting the intersection of the languages of two DFAs. More...

static fabuilder	subtract (dfa const &d1, dfa const &d2)
	Creates a builder for a DFA accepting the set difference of the languages of two DFAs. More...

static fabuilder	complement (dfa const &d)
	Creates a builder for a DFA accepting the complement of the language of a DFA. More...

static std::vector< std::valarray< bool > >	indistinguishableStates (std::vector< std::vector< size_t >> const &transitions, std::valarray< bool > const &accepting)
	Builds the table of indistinguishable states w.r.t. a transition function. More...

Friends
std::string	findShortestWord (dfa const &d)
	Searches the shortest UTF-8-encoded word accepted by a given DFA. More...

std::u32string	findShortestWord_ (dfa const &d)
	Searches the shortest UTF-32-encoded word accepted by a given DFA. More...

Detailed Description

Represents deterministic finite automata.

Instances of this class are completely immutable. The builder class is the preferred way of constructing DFAs.

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

Definition at line 41 of file dfa.h.

Constructor & Destructor Documentation

◆ dfa() [1/5]

reg::dfa::dfa ( )

Constructs a DFA accepting the empty language ∅.

Definition at line 89 of file dfa.cpp.

◆ dfa() [2/5]

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

Constructs DFA with a private implementation object with provided members.

Definition at line 96 of file dfa.cpp.

◆ dfa() [3/5]

reg::dfa::dfa	(	fabuilder &	b,
		bool	force = `false`
	)

Constructs a DFA from a builder by calling its build method.

Definition at line 92 of file dfa.cpp.

◆ dfa() [4/5]

reg::dfa::dfa ( dfa const & d )

Copy-constructs a DFA by copying another one's private implementation object.

Definition at line 103 of file dfa.cpp.

◆ dfa() [5/5]

reg::dfa::dfa ( dfa && d )

Move-constructs a DFA by stealing another one's private implementation object.

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

Definition at line 108 of file dfa.cpp.

Member Function Documentation

◆ complement()

fabuilder reg::dfa::complement ( dfa const & d )

static

Creates a builder for a DFA accepting the complement of the language of a DFA.

The input DFAs' state names will be retained in the created DFA.

Parameters

d the DFA

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

Definition at line 546 of file dfa.cpp.

◆ delta() [1/3]

size_t reg::dfa::delta	(	size_t	qi,
		size_t	si
	)		const

Computes this DFA'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: the reached state's index

Exceptions

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

Definition at line 215 of file dfa.cpp.

◆ delta() [2/3]

size_t reg::dfa::delta	(	size_t	qi,
		std::string const &	symbol
	)		const

Computes this DFA'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: the reached state's index

Exceptions

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

Definition at line 262 of file dfa.cpp.

◆ delta() [3/3]

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

Computes this DFA'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: the reached state's label

Exceptions

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

Definition at line 303 of file dfa.cpp.

◆ delta_() [1/2]

size_t reg::dfa::delta_	(	size_t	qi,
		char32_t	u32symbol
	)		const

Computes this DFA'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: the reached state's index

Exceptions

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

Definition at line 239 of file dfa.cpp.

◆ delta_() [2/2]

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

Computes this DFA's transition function for a state label 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: the reached state's label

Exceptions

state_not_found	if `q` ∉ getStates()
symbol_not_found	if `u32symbol` ∉ getAlphabet_()

Definition at line 280 of file dfa.cpp.

◆ deltaHat() [1/2]

size_t reg::dfa::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: the reached state's index

Exceptions

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

Definition at line 343 of file dfa.cpp.

◆ deltaHat() [2/2]

string const & reg::dfa::deltaHat	(	std::string const &	q,
		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 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: the reached state's index

Exceptions

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

Definition at line 383 of file dfa.cpp.

◆ deltaHat_() [1/2]

size_t reg::dfa::deltaHat_	(	size_t	qi,
		std::u32string const &	u32word
	)		const

Computes this DFA's transition function recursively for a UTF-32-encoded 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: the reached state's index

Exceptions

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

Definition at line 320 of file dfa.cpp.

◆ deltaHat_() [2/2]

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

Computes this DFA's transition function recursively for a UTF-32-encoded 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: the reached state's index

Exceptions

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

Definition at line 363 of file dfa.cpp.

◆ getAlphabet()

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

Fetches this DFA'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 412 of file dfa.cpp.

◆ getAlphabet_()

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

Fetches this DFA's set of processable symbols.

Returns: a vector containing all the valid symbol inputs for delta_() and deltaHat_()

Definition at line 405 of file dfa.cpp.

◆ getInitialState()

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

Names this DFA's initial state.

Returns: the initial state's name

Definition at line 391 of file dfa.cpp.

◆ getStates()

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

Fetches this DFA's set of states.

Returns: a vector containing the names of states that can be used as input for delta(), deltaHat(), delta_(), and deltaHat_()

Definition at line 398 of file dfa.cpp.

◆ indistinguishableStates()

vector< valarray< bool > > reg::dfa::indistinguishableStates	(	std::vector< std::vector< size_t >> const &	transitions,
		std::valarray< bool > const &	accepting
	)

static

Builds the table of indistinguishable states w.r.t. a transition function.

Parameters

transitions	the transition function to base indistinguishability computation off
accepting	the set of states that's trivially distinguishable from the rest

Returns: state index × state index table where true values mark indistinguishable states

Definition at line 557 of file dfa.cpp.

◆ intersect()

fabuilder reg::dfa::intersect	(	dfa const &	d1,
		dfa const &	d2
	)

static

Creates a builder for a DFA accepting the intersection of the languages of two DFAs.

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

Parameters

d1	the first DFA
d2	the other DFA

Returns: builder for a DFA accepting all the words accepted by both of the input DFAs

Definition at line 513 of file dfa.cpp.

◆ isAccepting() [1/2]

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

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

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 420 of file dfa.cpp.

◆ isAccepting() [2/2]

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

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

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 433 of file dfa.cpp.

◆ operator nfa const &()

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

Returns an NFA accepting the same language as this DFA.

◆ operator!=() [1/2]

bool reg::dfa::operator!= ( dfa const & d ) const

Tests whether this DFA doesn't accept the same language as another one.

Definition at line 194 of file dfa.cpp.

◆ operator!=() [2/2]

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

Tests whether this DFA doesn't accept the same language as another object.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 204 of file dfa.cpp.

◆ operator=() [1/2]

dfa & reg::dfa::operator= ( dfa const & d )

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

Definition at line 112 of file dfa.cpp.

◆ operator=() [2/2]

dfa & reg::dfa::operator= ( dfa && d )

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

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

Definition at line 122 of file dfa.cpp.

◆ operator==() [1/2]

bool reg::dfa::operator== ( dfa const & d ) const

Tests whether this DFA accepts exactly the same language as another one.

More specifically, checks whether this DFA's initial state is indistinguishable from the other one's.

Definition at line 146 of file dfa.cpp.

◆ operator==() [2/2]

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

Tests whether this DFA accepts exactly the same language as another object.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 198 of file dfa.cpp.

◆ subtract()

fabuilder reg::dfa::subtract	(	dfa const &	d1,
		dfa const &	d2
	)

static

Creates a builder for a DFA accepting the set difference of the languages of two DFAs.

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

Parameters

d1	the first DFA
d2	the other DFA

Returns: builder for a DFA accepting all the words accepted by the first but not the other input DFA

Definition at line 528 of file dfa.cpp.

◆ unite()

fabuilder reg::dfa::unite	(	dfa const &	d1,
		dfa const &	d2
	)

static

Creates a builder for a DFA accepting the union of the languages of two DFAs.

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

Parameters

d1	the first DFA
d2	the other DFA

Returns: builder for a DFA accepting all the words accepted by any of the input DFAs

Definition at line 498 of file dfa.cpp.

Friends And Related Function Documentation

◆ findShortestWord

std::string findShortestWord ( dfa const & d )

friend

Searches the shortest UTF-8-encoded word accepted by a given DFA.

This calls findShortestWord_() and converts the result to UTF-8. If you don't want that overhead and can handle UTF-32-encoded strings, use that function.

Parameters

d the DFA

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

Exceptions

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

Definition at line 483 of file dfa.cpp.

◆ findShortestWord_

std::u32string findShortestWord_ ( dfa const & d )

friend

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

Parameters

d the DFA

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

Exceptions

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

Definition at line 447 of file dfa.cpp.

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

Classes

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ dfa() [1/5]

◆ dfa() [2/5]

◆ dfa() [3/5]

◆ dfa() [4/5]

◆ dfa() [5/5]

Member Function Documentation

◆ complement()

◆ delta() [1/3]

◆ delta() [2/3]

◆ delta() [3/3]

◆ delta_() [1/2]

◆ delta_() [2/2]

◆ deltaHat() [1/2]

◆ deltaHat() [2/2]

◆ deltaHat_() [1/2]

◆ deltaHat_() [2/2]

◆ getAlphabet()

◆ getAlphabet_()

◆ getInitialState()

◆ getStates()

◆ indistinguishableStates()

◆ intersect()

◆ isAccepting() [1/2]

◆ isAccepting() [2/2]

◆ operator nfa const &()

◆ operator!=() [1/2]

◆ operator!=() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==() [1/2]

◆ operator==() [2/2]

◆ subtract()

◆ unite()

Friends And Related Function Documentation

◆ findShortestWord

◆ findShortestWord_