Represents generalized nondeterministic finite automata. More...

#include <gnfa.h>

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

Public Types
typedef std::vector< std::reference_wrapper< std::string const > >	state_vector
	Nicer name for arrays of names of states. Should store references to existing state names. More...

typedef std::vector< std::pair< std::reference_wrapper< std::string const >, std::reference_wrapper< std::string const > > >	state_pair_vector
	Nicer name for arrays of pairs names of states. Should store pairs of references to existing state names. More...

Public Member Functions
	gnfa (dfa const &d)
	Constructs a GNFA with the same states and transitions as a given DFA. More...

	gnfa (nfa const &n)
	Constructs a GNFA with the same states and transitions as a given NFA. More...

	gnfa (expression::exptr r)
	Constructs a GNFA with only one transition. More...

	gnfa (gnfa const &n)
	Copy-constructs a GNFA by copying another one's private implementation object. More...

	gnfa (gnfa &&n)
	Move-constructs a GNFA by stealing another one's private implementation object. More...

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

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

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

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

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

std::string const &	getInitialState () const
	Reveals the name of this GNFA's initial state. More...

std::string const &	getAcceptingState () const
	Reveals the name of this GNFA's accept state. More...

state_vector	getActiveStates () const
	Reveals the names of this GNFA's non-initial, non-accepting states. More...

expression::exptr	getTransition (std::string const &q, std::string const &p) const
	Extracts the RE labelling the transition between two states. More...

state_pair_vector	getSplittableTransitions () const
	Reveals this GNFA's splittable transitions. More...

state_vector	splitTransition (std::string const &q, std::string const &p)
	Splits a transition between two states, adding new states if needed. More...

nfa	splitAllTransitions ()
	Splits all transitions until only ∅, ε, and symbol REs remain and builds the resulting NFA. More...

void	bypassTransition (std::string const &q, std::string const &p)
	Removes a transition between two states and replaces it with equivalent ones, bypassing its beginning state. More...

void	ripState (std::string const &q)
	Removes a state, bypassing all its outgoing transitions. More...

expression::exptr	ripAllStates ()
	Removes all active states, constructing an RE semantically equivalent to this GNFA. More...

Detailed Description

Represents generalized nondeterministic finite automata.

Definition at line 35 of file gnfa.h.

Member Typedef Documentation

◆ state_pair_vector

typedef std::vector<std::pair<std::reference_wrapper<std::string const>, std::reference_wrapper<std::string const> > > reg::gnfa::state_pair_vector

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

Definition at line 44 of file gnfa.h.

◆ state_vector

typedef std::vector<std::reference_wrapper<std::string const> > reg::gnfa::state_vector

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

Definition at line 39 of file gnfa.h.

Constructor & Destructor Documentation

◆ gnfa() [1/5]

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

Constructs a GNFA with the same states and transitions as a given DFA.

The following changes are applied upon conversion:

Add a new and uniquely named initial state and connect it via an ε-transition to the DFA's start state.
Add a new and uniquely named accept state and connect the DFA's accept states to it via ε-transitions.
Disregard any information about initial or accept states of the DFA.
Replace any transition with a corresponding symbol expression.
Replace transitions with more than one label with alternations of these labels.
Parameters

d the DFA to base the GNFA on

Definition at line 156 of file gnfa.cpp.

◆ gnfa() [2/5]

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

Constructs a GNFA with the same states and transitions as a given NFA.

The following changes are applied upon conversion:

Add a new and uniquely named initial state and connect it via an ε-transition to the NFA's start state.
Add a new and uniquely named accept state and connect the NFA's accept states to it via ε-transitions.
Disregard any information about initial or accept states of the NFA.
Replace any transition with a corresponding symbol expression.
Replace transitions with more than one label with alternations of these labels.
Parameters

n the NFA to base the GNFA on

Definition at line 196 of file gnfa.cpp.

◆ gnfa() [3/5]

reg::gnfa::gnfa ( expression::exptr r )

Constructs a GNFA with only one transition.

The GNFA will have only two states: the initial and the accept state and a transition with the given label leading from the former to the latter.

Parameters

r	the transition's RE

Definition at line 231 of file gnfa.cpp.

◆ gnfa() [4/5]

reg::gnfa::gnfa ( gnfa const & n )

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

Definition at line 454 of file gnfa.cpp.

◆ gnfa() [5/5]

reg::gnfa::gnfa ( gnfa && n )

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

The other GNFA will be semantically equivalent to the ∅ RE afterwards.

Definition at line 462 of file gnfa.cpp.

Member Function Documentation

◆ bypassTransition()

void reg::gnfa::bypassTransition	(	std::string const &	q,
		std::string const &	p
	)

Removes a transition between two states and replaces it with equivalent ones, bypassing its beginning state.

Definition at line 401 of file gnfa.cpp.

◆ getAcceptingState()

string const & reg::gnfa::getAcceptingState ( ) const

Reveals the name of this GNFA's accept state.

Definition at line 264 of file gnfa.cpp.

◆ getActiveStates()

gnfa::state_vector reg::gnfa::getActiveStates ( ) const

Reveals the names of this GNFA's non-initial, non-accepting states.

Definition at line 267 of file gnfa.cpp.

◆ getInitialState()

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

Reveals the name of this GNFA's initial state.

Definition at line 261 of file gnfa.cpp.

◆ getSplittableTransitions()

gnfa::state_pair_vector reg::gnfa::getSplittableTransitions ( ) const

Reveals this GNFA's splittable transitions.

Returns: a vector of edges with transition labels with expression::size() > 1

Definition at line 288 of file gnfa.cpp.

◆ getTransition()

expression::exptr reg::gnfa::getTransition	(	std::string const &	q,
		std::string const &	p
	)		const

Extracts the RE labelling the transition between two states.

Definition at line 278 of file gnfa.cpp.

◆ operator nfa const &()

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

Returns an NFA accepting the same language as this GNFA.

◆ operator!=()

bool reg::gnfa::operator!= ( nfa const & other ) const

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

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

Definition at line 490 of file gnfa.cpp.

◆ operator=() [1/2]

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

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

Definition at line 494 of file gnfa.cpp.

◆ operator=() [2/2]

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

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

The other GNFA will be semantically equivalent to the ∅ RE afterwards.

Definition at line 507 of file gnfa.cpp.

◆ operator==()

bool reg::gnfa::operator== ( nfa const & other ) const

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

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

Definition at line 480 of file gnfa.cpp.

◆ ripAllStates()

expression::exptr reg::gnfa::ripAllStates ( )

Removes all active states, constructing an RE semantically equivalent to this GNFA.

Returns: exptr to the RE labelling the remaining transition between initial state and accept state

Definition at line 445 of file gnfa.cpp.

◆ ripState()

void reg::gnfa::ripState ( std::string const & q )

Removes a state, bypassing all its outgoing transitions.

Definition at line 423 of file gnfa.cpp.

◆ splitAllTransitions()

nfa reg::gnfa::splitAllTransitions ( )

Splits all transitions until only ∅, ε, and symbol REs remain and builds the resulting NFA.

When building the NFA, transitions with symbol and ε REs are replaced with corresponding symbol transitions and transitions with ∅ REs will be ignored.

Returns: the NFA with equivalent states and transitions to the GNFA's after splitting

Definition at line 378 of file gnfa.cpp.

◆ splitTransition()

gnfa::state_vector reg::gnfa::splitTransition	(	std::string const &	q,
		std::string const &	p
	)

Splits a transition between two states, adding new states if needed.

The transition will be broken up into pieces, according to the semantics of its label.