reg::nfa::builder Class Reference

Constructs NFAs step by step. More...

#include <nfa.h>

Classes
struct	pImpl
	Private implementation details of NFA builders. More...

Public Member Functions
	builder ()
	Constructs a blank builder object. More...
	builder (nfa const &nfa)
	Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given NFA. More...
	builder (dfa const &dfa)
	Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given DFA. More...
	builder (builder &b)
	Copy-constructs a builder by copying another one's private implementation object. More...
	builder (builder &&b)
	Move-constructs a builder by stealing another one's private implementation object. More...
builder &	operator= (builder const &b)
	Copy-assigns a builder by copying another one's private implementation object. More...
builder &	operator= (builder &&b)
	Move-assigns a builder by stealing another one's private implementation object. More...
builder &	addSymbol (char32_t symbol)
	Adds a symbol to the prospective NFA's alphabet. More...
builder &	addSymbol (std::string const &utf8Symbol)
	Same as above for a UTF-8-encoded symbol. More...
builder &	setAccepting (std::string const &state, bool accept)
	Sets whether or not a state will be accepting within the prospective NFA. More...
builder &	makeInitial (std::string const &state)
	Resets the initial state for the prospective NFA. More...
builder &	addTransition (std::string const &from, std::string const &to, char32_t symbol)
	Adds a transition for the prospective NFA. More...
builder &	addTransition (std::string const &from, std::string const &to, std::string const &utf8Symbol)
	Same as above for a UTF-8-encoded symbol. More...
nfa	build ()
	Builds the NFA, as defined by previous operations. 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 52 of file nfa.h.

Constructor & Destructor Documentation

builder() [1/5]

reg::nfa::builder::builder

(

)

Constructs a blank builder object.

Definition at line 353 of file nfa.cpp.

: p(new pImpl) {}

builder() [2/5]

reg::nfa::builder::builder

(

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 356 of file nfa.cpp.

                                  : p(new pImpl) {
  makeInitial(nfa.getLabelOf(0));
  for (char32_t symbol : nfa.getAlphabet()) {
    addSymbol(symbol);
  }
  for (size_t qi = 0; qi < nfa.p->labels.size(); ++qi) {
    string const& qLabel = nfa.getLabelOf(qi);
    for (char32_t symbol : p->alphabet) {
      valarray<bool> ps = nfa.delta(qi, symbol);
      size_t pi(0);
      for (bool pb : ps) {
        if (pb) {
          addTransition(qLabel, nfa.getLabelOf(pi), symbol);
        }
        pi++;
      }
    }
    if (nfa.isAccepting(qi)) {
      setAccepting(qLabel, true);
    }
  }
}

builder() [3/5]

reg::nfa::builder::builder

(

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 381 of file nfa.cpp.

                                  {
  string initial(dfa.getLabelOf(0));
  unordered_set<string> acceptingStates;
  unordered_set<char32_t> alphabet(dfa.getAlphabet().begin(), dfa.getAlphabet().end());
  unordered_map<string,unordered_map<char32_t,unordered_set<string>>> transitions;
  for (size_t q(0); q < dfa.getNumberOfStates(); q++) {
    for (char32_t symbol : alphabet) {
      transitions[dfa.getLabelOf(q)][symbol].insert(dfa.getLabelOf(dfa.delta(q, symbol)));
    }
  }
  p = unique_ptr<pImpl>(new pImpl(initial, acceptingStates, alphabet, transitions));
}

builder() [4/5]

reg::nfa::builder::builder

(

builder &

b

)

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

Definition at line 395 of file nfa.cpp.

: p(new pImpl(*(b.p))) {}

builder() [5/5]

reg::nfa::builder::builder

(

builder &&

b

)

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

The other builder will be blank afterwards.

Definition at line 399 of file nfa.cpp.

: p(new pImpl) {p.swap(b.p);}

Member Function Documentation

addSymbol() [1/2]

nfa::builder & reg::nfa::builder::addSymbol

(

char32_t

symbol

)

Adds a symbol to the prospective NFA's alphabet.

Parameters

symbol

the symbol to add

Returns

reference to this object, for chaining operations

Definition at line 425 of file nfa.cpp.

                                                 {
  p->alphabet.insert(symbol);
  return *this;
}

addSymbol() [2/2]

nfa::builder & reg::nfa::builder::addSymbol

(

std::string const &

utf8Symbol

)

Same as above for a UTF-8-encoded symbol.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 431 of file nfa.cpp.

                                                          {
  return addSymbol(expression::converter->from_bytes(utf8Symbol)[0]);
}

addTransition() [1/2]

nfa::builder & reg::nfa::builder::addTransition	(	std::string const &	from,
		std::string const &	to,
		char32_t	symbol
	)

Adds a transition for the prospective NFA.

Parameters

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

Returns

reference to this object, for chaining operations

Definition at line 475 of file nfa.cpp.

                                                                                           {
  if (p->transitions.empty()) {
    p->initial = from;
  }
  p->transitions[to];
  p->transitions[from][symbol].insert(to);
  addSymbol(symbol);
  return *this;
}

addTransition() [2/2]

nfa::builder & reg::nfa::builder::addTransition	(	std::string const &	from,
		std::string const &	to,
		std::string const &	utf8Symbol
	)

Same as above for a UTF-8-encoded symbol.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 486 of file nfa.cpp.

                                                                                                    {
  return addTransition(from, to, expression::converter->from_bytes(utf8Symbol)[0]);
}

build()

nfa reg::nfa::builder::build

(

)

Builds the NFA, as defined by previous operations.

Returns

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

Definition at line 495 of file nfa.cpp.

                      {
  p->alphabet.insert(U'\0');
  vector<char32_t> alphabetV(p->alphabet.begin(), p->alphabet.end());
  sort(alphabetV.begin(), alphabetV.end());
  vector<string> labelV(p->transitions.size());
  labelV[0] = p->initial;
  valarray<bool> acceptingV(p->transitions.size());
  acceptingV[0] = (p->acceptingStates.find(p->initial) != p->acceptingStates.end());
  size_t i(1);
  for (auto entry : p->transitions) {
    if (entry.first == p->initial) {
      continue;
    }
    labelV[i] = entry.first;
    acceptingV[i++] = (
      p->acceptingStates.find(entry.first) != p->acceptingStates.end()
    );
  }
  vector<vector<valarray<bool>>> transitionV(
    p->transitions.size(),
    vector<valarray<bool>>(
      p->alphabet.size()+1,
      valarray<bool>(labelV.size())
    )
  );
  unordered_set<string> emptySet;
  size_t qi(0);
  for (auto const& q : labelV) {
    unordered_map<char32_t,unordered_set<string>> const& fromQ = p->transitions[q];
    size_t si(0);
    for (char32_t symbol : alphabetV) {
      auto to = fromQ.find(symbol);
      unordered_set<string> const& viaSymbol(to != fromQ.end() ? to->second : emptySet);
      i = 0;
      for (auto const& p : labelV) {
        transitionV[qi][si][i++] = (viaSymbol.count(p) != 0);
      }
      si++;
    }
    qi++;
  }
  return {alphabetV, transitionV, labelV, acceptingV};
}

makeInitial()

nfa::builder & reg::nfa::builder::makeInitial

(

std::string const &

state

)

Resets the initial state for the prospective NFA.

Parameters

state

the new initial state

Returns

reference to this object, for chaining operations

Definition at line 461 of file nfa.cpp.

                                                       {
  p->initial = state;
  p->transitions[state];
  return *this;
}

operator=() [1/2]

nfa::builder & reg::nfa::builder::operator=

(

builder const &

b

)

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

Definition at line 402 of file nfa.cpp.

                                                  {
  if (this != &b) {
    p.reset(new pImpl(*(b.p)));
  }
  return *this;
}

operator=() [2/2]

nfa::builder & reg::nfa::builder::operator=

(

nfa::builder &&

b

)

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

The other builder will be blank afterwards.

Definition at line 411 of file nfa.cpp.

                                                {
  if (this != &b) {
    p.reset(new pImpl);
    p.swap(b.p);
  }
  return *this;
}

setAccepting()

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

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

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 442 of file nfa.cpp.

                                                                     {
  if (p->transitions.empty()) {
    p->initial = state;
  }
  p->transitions[state];
  if (accept) {
    p->acceptingStates.insert(state);
  } else {
    p->acceptingStates.erase(state);
  }
  return *this;
}

---

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

• nfa.h
• nfa.cpp