Constructs finite automata 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 &	subtract (nfa const &other, bool force=false)
	Makes the prospective FA reject all words accepted 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...

bool	isComplete ()
	Reports whether the prospective FA has at least one transition defined for every state-symbol combination. More...

bool	hasNondeterminism ()
	Checks whether any nondeterministic transitions have been defined. 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 finite automata 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 173 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 177 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 185 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 189 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 194 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 253 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 279 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 268 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 295 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 965 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 904 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 795 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 363 of file fabuilder.cpp.

◆ hasNondeterminism()

bool reg::fabuilder::hasNondeterminism ( )

Checks whether any nondeterministic transitions have been defined.

Definition at line 887 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 672 of file fabuilder.cpp.

◆ isComplete()

bool reg::fabuilder::isComplete ( )

Reports whether the prospective FA has at least one transition defined for every state-symbol combination.

Definition at line 871 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 243 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 421 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 559 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 822 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 200 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 210 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 316 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 489 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 225 of file fabuilder.cpp.

◆ subtract()

fabuilder & reg::fabuilder::subtract	(	nfa const &	other,
		bool	force = `false`
	)

Makes the prospective FA reject all words accepted by another FA.

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.

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

Parameters

other	the FA whose language should be rejected
force	determines whether a nondeterministic builder should be made deterministic or an exception should be thrown

Returns: reference to this object, for chaining operations

Definition at line 770 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 571 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()

◆ hasNondeterminism()

◆ intersect()

◆ isComplete()

◆ makeInitial()

◆ merge()

◆ minimize()

◆ normalizeStateNames()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ powerset()

◆ purge()

◆ setAccepting()

◆ subtract()

◆ unite()