reg::dfa::pImpl Struct Reference

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

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

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 46 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(expression::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 64 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 36 of file dfa.cpp.

alphabet

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

Represents the set of processable symbols.

Definition at line 37 of file dfa.cpp.

labels

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

Stores the names of states.

Definition at line 39 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 40 of file dfa.cpp.

utf8Alphabet

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

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

Definition at line 38 of file dfa.cpp.

---

The documentation for this struct was generated from the following file:

• dfa.cpp