Private implementation details of DFAs. More...

Public Member Functions
	pImpl ()
	Constructs private implementation object for a DFA accepting the empty language ∅. More...

	pImpl (vector< char32_t > &alphabet, vector< vector< size_t >> &transitions, vector< string > &labels, valarray< bool > &accepting)
	Constructs private implementation object with provided members. More...

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

Public Attributes
std::shared_ptr< nfa const >	equivalent
	Holds an equivalent NFA in case it is ever needed. More...

valarray< bool >	accepting
	A `true` value marks an index as belonging to an accept state. More...

vector< char32_t >	alphabet
	Represents the set of processable symbols. More...

vector< string >	utf8Alphabet
	Represents the set of processable symbols as UTF-8-encoded strings. More...

vector< string >	labels
	Stores the names of states. More...

vector< vector< size_t > >	transitions
	Stores the transition function as a table viz state index × symbol index → state index. More...

Detailed Description

Private implementation details of DFAs.

Definition at line 54 of file dfa.cpp.

Constructor & Destructor Documentation

◆ pImpl() [1/2]

reg::dfa::pImpl::pImpl ( )

inline

Constructs private implementation object for a DFA accepting the empty language ∅.

Definition at line 63 of file dfa.cpp.

63 : accepting(false, 1), alphabet(0), utf8Alphabet(0), labels(1), transitions(1) {}

reg::dfa::pImpl::alphabet

vector< char32_t > alphabet

Represents the set of processable symbols.

Definition: dfa.cpp:57

reg::dfa::pImpl::accepting

valarray< bool > accepting

A true value marks an index as belonging to an accept state.

Definition: dfa.cpp:56

reg::dfa::pImpl::utf8Alphabet

vector< string > utf8Alphabet

Represents the set of processable symbols as UTF-8-encoded strings.

Definition: dfa.cpp:58

reg::dfa::pImpl::labels

vector< string > labels

Stores the names of states.

Definition: dfa.cpp:59

reg::dfa::pImpl::transitions

vector< vector< size_t > > transitions

Stores the transition function as a table viz state index × symbol index → state index...

Definition: dfa.cpp:60

◆ pImpl() [2/2]

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

inline

Constructs private implementation object with provided members.

Definition at line 66 of file dfa.cpp.

                                                             :
         accepting(move(accepting)),
         alphabet(move(alphabet)),
         labels(move(labels)),
         transitions(move(transitions)) {
     utf8Alphabet.reserve(this->alphabet.size());
     for (char32_t symbol : this->alphabet) {
       utf8Alphabet.push_back(converter.to_bytes(symbol));
     }
   }

Member Function Documentation

◆ indistinguishableStates()

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

inlinestatic

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

                                                                                   {
     vector<valarray<bool>> distinguishable;
     distinguishable.reserve(transitions.size());
     for (size_t q(0); q < transitions.size(); q++) {
       bool qAcc(accepting[q]);
       distinguishable.push_back(valarray<bool>(false, transitions.size()));
       for (size_t p(0); p < q; p++) {
         bool pAcc(accepting[p]);
         distinguishable[q][p] = (qAcc != pAcc);
         distinguishable[p][q] = (qAcc != pAcc);
       }
     }
     bool changes(true);
     while (changes) {
       changes = false;
       for (size_t q(0); q < transitions.size(); q++) {
         for (size_t p(0); p < q; p++) {
           if (distinguishable[q][p]) {
             continue;
           }
           for (size_t s(0); s < transitions[q].size(); s++) {
             size_t qS(transitions[q][s]);
             size_t pS(transitions[p][s]);
             if (distinguishable[qS][pS]) {
               changes = true;
               distinguishable[q][p] = true;
               distinguishable[p][q] = true;
               break;
             }
           }
         }
       }
     }
     valarray<bool> allTrue(true, transitions.size());
     for (size_t i(0); i < distinguishable.size(); i++) {
       distinguishable[i] ^= allTrue;
     }
     return distinguishable;
   }

Member Data Documentation

◆ accepting

valarray<bool> reg::dfa::pImpl::accepting

A true value marks an index as belonging to an accept state.

Definition at line 56 of file dfa.cpp.

◆ alphabet

vector<char32_t> reg::dfa::pImpl::alphabet

Represents the set of processable symbols.

Definition at line 57 of file dfa.cpp.

◆ equivalent

std::shared_ptr<nfa const> reg::dfa::pImpl::equivalent

mutable

Holds an equivalent NFA in case it is ever needed.

Definition at line 55 of file dfa.cpp.

◆ labels

vector<string> reg::dfa::pImpl::labels

Stores the names of states.

Definition at line 59 of file dfa.cpp.

◆ transitions

vector<vector<size_t> > reg::dfa::pImpl::transitions

Stores the transition function as a table viz state index × symbol index → state index.

Definition at line 60 of file dfa.cpp.

◆ utf8Alphabet

vector<string> reg::dfa::pImpl::utf8Alphabet