Constructs NFAs step by step. More...

#include <fabuilder.h>

Classes
struct	impl
	Private implementation details of FA builders. More...

struct	nondeterminism_exception
	Signals that an operation requires full determinism and that no powerset construction was forced. More...

Public Member Functions
	fabuilder ()
	Constructs a blank builder object. More...

	fabuilder (nfa const &nfa)
	Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given NFA. More...

	fabuilder (dfa const &dfa)
	Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given DFA. More...

	fabuilder (fabuilder const &b)
	Copy-constructs a builder by copying another one's private implementation object. More...

	fabuilder (fabuilder &&b)
	Move-constructs a builder by stealing another one's private implementation object. More...

fabuilder &	operator= (fabuilder const &b)
	Copy-assigns a builder by copying another one's private implementation object. More...

fabuilder &	operator= (fabuilder &&b)
	Move-assigns a builder by stealing another one's private implementation object. More...

fabuilder &	setAccepting (std::string const &state, bool accept)
	Sets whether or not a state will be accepting within the prospective FA. More...

fabuilder &	makeInitial (std::string const &state)
	Resets the initial state for the prospective FA. More...

fabuilder &	addSymbol (std::string const &symbol)
	Adds a symbol to the prospective FA's alphabet. More...

fabuilder &	addTransition (std::string const &from, std::string const &to, std::string const &symbol="")
	Adds a transition to the prospective FA's state transition function. More...

fabuilder &	addSymbol_ (char32_t u32symbol)
	Adds a symbol to the prospective FA's alphabet. More...

fabuilder &	addTransition_ (std::string const &from, std::string const &to, char32_t u32symbol=U'\0')
	Adds a transition to the prospective FA's state transition function. More...

fabuilder &	powerset ()
	Converts the builder's prospective NFA into a DFA via powerset construction. More...

fabuilder &	complete ()
	Totalizes a partial transition function by pointing any undefined transitions towards a trash state. More...

fabuilder &	merge (bool force=false)
	Merges the prospective DFA's indistinguishable states, allowing for minimization. More...

fabuilder &	purge ()
	Purges the prospective FA of unreachable and non-producing states, possibly completing minimization. More...

fabuilder &	minimize (bool force=false)
	Convenience method for chaining purge and merge to achieve proper DFA minimization. More...

fabuilder &	unite (nfa const &other)
	Makes the prospective FA also accept every word of another FA's language. More...

fabuilder &	intersect (nfa const &other)
	Makes the prospective FA accept only words accepted also by another FA. More...

fabuilder &	complement (bool force=false)
	Inverts the prospective DFA's language with respect to all possible strings over its alphabet. More...

fabuilder &	normalizeStateNames (std::string const &prefix)
	Reduces the prospective FA's state names to consecutive numbers, prefixed with a given string. More...

nfa	buildNfa ()
	Builds an NFA as defined by previous operations. More...

dfa	buildDfa (bool force=false)
	Builds a DFA as defined by previous operations, including completion. More...

Detailed Description

Constructs NFAs step by step.

Any mention of a symbol or state will add them to the alphabet/set of states. The first state mentioned will be designated initial state.

Definition at line 31 of file fabuilder.h.

Constructor & Destructor Documentation

◆ fabuilder() [1/5]

reg::fabuilder::fabuilder ( )

Constructs a blank builder object.

Definition at line 186 of file fabuilder.cpp.

◆ fabuilder() [2/5]

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

Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given NFA.

Definition at line 190 of file fabuilder.cpp.

◆ fabuilder() [3/5]

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

Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given DFA.

Transition destinations will be converted to singleton sets of the respective reached states.

Definition at line 198 of file fabuilder.cpp.

◆ fabuilder() [4/5]

reg::fabuilder::fabuilder ( fabuilder const & b )

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

Definition at line 202 of file fabuilder.cpp.

◆ fabuilder() [5/5]

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

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

The other builder will be blank afterwards.

Definition at line 207 of file fabuilder.cpp.

Member Function Documentation

◆ addSymbol()

fabuilder & reg::fabuilder::addSymbol ( std::string const & symbol )

Adds a symbol to the prospective FA's alphabet.

Parameters

symbol the symbol to add

Returns: reference to this object, for chaining operations

Definition at line 266 of file fabuilder.cpp.

◆ addSymbol_()

fabuilder & reg::fabuilder::addSymbol_ ( char32_t u32symbol )

Adds a symbol to the prospective FA's alphabet.

Parameters

u32symbol the symbol to add

Returns: reference to this object, for chaining operations

Definition at line 292 of file fabuilder.cpp.

◆ addTransition()

fabuilder & reg::fabuilder::addTransition	(	std::string const &	from,
		std::string const &	to,
		std::string const &	symbol = `""`
	)

Adds a transition to the prospective FA's state transition function.

Makes the builder nondeterministic if there is already a transition triggered by symbol originating in from or symbol is "".

Parameters

from	the starting state for the transition
to	the destination state for the transition
symbol	the symbol triggering the transition or `""` for an ε-transition

Returns: reference to this object, for chaining operations

Definition at line 281 of file fabuilder.cpp.

◆ addTransition_()

fabuilder & reg::fabuilder::addTransition_	(	std::string const &	from,
		std::string const &	to,
		char32_t	u32symbol = `U'\0'`
	)

Adds a transition to the prospective FA's state transition function.

Makes the builder nondeterministic if there is already a transition triggered by u32symbol originating in from or u32symbol is U'\0'.

Parameters

from	the starting state for the transition
to	the destination state for the transition
u32symbol	the symbol triggering the transition or `U'\0'` for an ε-transition

Returns: reference to this object, for chaining operations

Definition at line 308 of file fabuilder.cpp.

◆ buildDfa()

dfa reg::fabuilder::buildDfa ( bool force = false )

Builds a DFA as defined by previous operations, including completion.

This needs to be done on a builder without nondeterminism. If it already has nondeterministic characteristics, a purge() is tried to establish determinism and if that fails, the FA is either converted via powerset() or a nondeterminism_exception is thrown, depending on the value of force.

Preserves the builder's determinism if force is false, makes it deterministic else.

Parameters

force determines whether a nondeterministic builder should be made deterministic or an exception should be thrown

Returns: a DFA object with exactly the states, alphabet and transitions that were defined and a trash state if needed

Exceptions

nondeterminism_exception if the builder has nondeterministic characteristics and force is false

Definition at line 920 of file fabuilder.cpp.

◆ buildNfa()

nfa reg::fabuilder::buildNfa ( )

Builds an NFA as defined by previous operations.

Returns: an NFA object with exactly the states, alphabet and transitions that were defined

Definition at line 859 of file fabuilder.cpp.

◆ complement()

fabuilder & reg::fabuilder::complement ( bool force = false )

Inverts the prospective DFA's language with respect to all possible strings over its alphabet.

This needs to be done on a builder without nondeterminism. If it already has nondeterministic characteristics, a purge() is tried to establish determinism and if that fails, the FA is either converted via powerset() or a nondeterminism_exception is thrown, depending on the value of force.

Preserves the builder's determinism if force is false, makes it deterministic else.

Parameters

force determines whether a nondeterministic builder should be made deterministic or an exception should be thrown

Returns: reference to this object, for chaining operations

Exceptions

nondeterminism_exception if the builder has nondeterministic characteristics and force is false

Definition at line 780 of file fabuilder.cpp.

◆ complete()

fabuilder & reg::fabuilder::complete ( )

Totalizes a partial transition function by pointing any undefined transitions towards a trash state.

If there is no state satisfying trashiness, a new one will be generated.

Preserves the builder's determinism.

Returns: reference to this object, for chaining operations

Definition at line 376 of file fabuilder.cpp.

◆ intersect()

fabuilder & reg::fabuilder::intersect ( nfa const & other )

Makes the prospective FA accept only words accepted also by another FA.

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

Preserves the builder's determinism.

Parameters

other the FA whose language should also be accepted

Returns: reference to this object, for chaining operations

Definition at line 683 of file fabuilder.cpp.

◆ makeInitial()

fabuilder & reg::fabuilder::makeInitial ( std::string const & state )

Resets the initial state for the prospective FA.

Parameters

state the new initial state

Returns: reference to this object, for chaining operations

Definition at line 256 of file fabuilder.cpp.

◆ merge()

fabuilder & reg::fabuilder::merge ( bool force = false )

Merges the prospective DFA's indistinguishable states, allowing for minimization.

This needs to be done on a builder without nondeterminism. If it already has nondeterministic characteristics, a purge() is tried to establish determinism and if that fails, the FA is either converted via powerset() or a nondeterminism_exception is thrown, depending on the value of force.

Doesn't change the prospective DFA's accepted language, but it will be built with the minimum of reachable states to fulfill that purpose. Unreachable states will be merged since they are indistinguishable, but they won't be removed, hence preventing true minimization; that's what purge() is for.

Preserves the builder's determinism if force is false, makes it deterministic else.

Parameters

force determines whether a nondeterministic builder should be made deterministic or an exception should be thrown

Returns: reference to this object, for chaining operations

Exceptions

nondeterminism_exception if the builder has nondeterministic characteristics and force is false

Definition at line 432 of file fabuilder.cpp.

◆ minimize()

fabuilder & reg::fabuilder::minimize ( bool force = false )

Convenience method for chaining purge and merge to achieve proper DFA minimization.

Forwards force to merge() and has the same guarantees regarding determinism.

Parameters

force determines whether a nondeterministic builder should be made deterministic or an exception should be thrown

Returns: reference to this object, for chaining operations

Exceptions

nondeterminism_exception if the builder has nondeterministic characteristics and force is false

Definition at line 570 of file fabuilder.cpp.

◆ normalizeStateNames()

fabuilder & reg::fabuilder::normalizeStateNames ( std::string const & prefix )

Reduces the prospective FA's state names to consecutive numbers, prefixed with a given string.

Parameters

prefix the string that should be prepended, can be empty

Returns: reference to this object, for chaining operations

Definition at line 807 of file fabuilder.cpp.

◆ operator=() [1/2]

fabuilder & reg::fabuilder::operator= ( fabuilder const & b )

Copy-assigns a builder by copying another one's private implementation object.

Definition at line 213 of file fabuilder.cpp.

◆ operator=() [2/2]

fabuilder & reg::fabuilder::operator= ( fabuilder && b )

Move-assigns a builder by stealing another one's private implementation object.

The other builder will be blank afterwards.

Definition at line 223 of file fabuilder.cpp.

◆ powerset()

fabuilder & reg::fabuilder::powerset ( )

Converts the builder's prospective NFA into a DFA via powerset construction.

Makes the builder deterministic.

Returns: reference to this object, for chaining operations

Definition at line 329 of file fabuilder.cpp.

◆ purge()

fabuilder & reg::fabuilder::purge ( )

Purges the prospective FA of unreachable and non-producing states, possibly completing minimization.

Doesn't change the prospective FA's accepted language, but it will be built without states that can never be reached nor ones that can never reach an accept state, except for a trash state in a DFA.

Preserves the builder's determinism.

Returns: reference to this object, for chaining operations

Definition at line 500 of file fabuilder.cpp.

◆ setAccepting()

fabuilder & reg::fabuilder::setAccepting	(	std::string const &	state,
		bool	accept
	)

Sets whether or not a state will be accepting within the prospective FA.

Parameters

state	the state's name
accept	`true` if the state should be an accept state afterwards, `false` else

Returns: reference to this object, for chaining operations

Definition at line 238 of file fabuilder.cpp.

◆ unite()

fabuilder & reg::fabuilder::unite ( nfa const & other )

Makes the prospective FA also accept every word of another FA's language.

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

Preserves the builder's determinism.

Parameters

other the DFA whose language should also be accepted

Returns: reference to this object, for chaining operations

Definition at line 582 of file fabuilder.cpp.

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

Classes

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ fabuilder() [1/5]

◆ fabuilder() [2/5]

◆ fabuilder() [3/5]

◆ fabuilder() [4/5]

◆ fabuilder() [5/5]

Member Function Documentation

◆ addSymbol()

◆ addSymbol_()

◆ addTransition()

◆ addTransition_()

◆ buildDfa()

◆ buildNfa()

◆ complement()

◆ complete()

◆ intersect()

◆ makeInitial()

◆ merge()

◆ minimize()

◆ normalizeStateNames()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ powerset()

◆ purge()

◆ setAccepting()

◆ unite()