reg::nfa Class Reference

Represents nondeterministic finite automata with ε-moves. More...

#include <nfa.h>

Classes
class	builder
	Constructs NFAs step by step. More...
struct	equal_to_reference_string_const
	Provides std::unordered_set::key_eq for state_set. More...
struct	hash_reference_string_const
	Provides std::unordered_set::hash_function for state_set. More...
struct	pImpl
	Private implementation details of NFAs. More...

Public Types
typedef std::unordered_set< std::reference_wrapper< std::string const >, hash_reference_string_const, equal_to_reference_string_const >	state_set
	Nicer name for sets of names of states. Should store references to names in getStates. More...

Public Member Functions
	nfa ()
	Constructs an NFA accepting the empty language ∅. More...
	nfa (nfa const &n)
	Copy-constructs an NFA by copying another one's private implementation object. More...
	nfa (nfa &&n)
	Move-constructs an NFA by stealing another one's private implementation object. More...
	nfa (dfa const &d)
	Constructs an NFA from a DFA. More...
	nfa (builder &b)
	Constructs an NFA from a builder. More...
nfa &	operator= (nfa const &n)
	Copy-assigns this NFA by copying another one's private implementation object. More...
nfa &	operator= (nfa &&n)
	Move-assigns this NFA by stealing another one's private implementation object. More...
bool	operator== (nfa const &n) const
	Tests whether this NFA accepts exactly the same language as another one. More...
bool	operator!= (nfa const &n) const
	Tests whether this NFA doesn't accept the same language as another one. More...
std::valarray< bool > const &	delta (size_t qi, size_t si) const
	Computes this NFA's transition function for a state index and a symbol index. More...
std::valarray< bool > const &	delta (size_t qi, char32_t symbol) const
	Computes this NFA's transition function for a state index and a symbol. More...
std::valarray< bool > const &	delta (size_t qi, std::string const &utf8Symbol) const
	Same as above for a UTF-8-encoded symbol. More...
state_set	delta (std::string const &q, char32_t symbol) const
	Computes this NFA's transition function for a state index and a symbol. More...
state_set	delta (std::string const &q, std::string const &utf8Symbol) const
	Same as above for a UTF-8-encoded symbol. More...
std::valarray< bool >	deltaHat (size_t qi, std::u32string const &word) const
	Computes this NFA's transition function recursively for a string of symbols, starting in a state specified by its index. More...
std::valarray< bool >	deltaHat (size_t qi, std::string const &utf8Word) const
	Same as above for a UTF-8-encoded string of symbols. More...
state_set	deltaHat (std::string const &q, std::u32string const &word) const
	Computes this NFA's transition function recursively for a string of symbols, starting in a state specified by its name. More...
state_set	deltaHat (std::string const &q, std::string const &utf8Word) const
	Same as above for a UTF-8-encoded string of symbols. More...
std::valarray< bool >	deltaHat (std::valarray< bool > const &qs, std::u32string const &word) const
	Computes this NFA's transition function recursively for a string of symbols, starting in multiple specified states. More...
std::valarray< bool >	deltaHat (std::valarray< bool > const &qs, std::string const &utf8Word) const
	Same as above for a UTF-8-encoded string of symbols. More...
state_set	deltaHat (state_set const &qs, std::u32string const &word) const
	Computes this NFA's transition function recursively for a string of symbols, starting in multiple states specified by their names. More...
state_set	deltaHat (state_set const &qs, std::string const &utf8Word) const
	Same as above for a UTF-8-encoded string of symbols. More...
std::valarray< bool > const &	epsilonClosure (size_t qi) const
	Computes a state's ε-closure. More...
state_set	epsilonClosure (std::string const &q) const
	Computes a state's ε-closure. More...
std::valarray< bool >	epsilonClosure (std::valarray< bool > const &qs) const
	Computes the union of multiple states' ε-closures. More...
state_set	epsilonClosure (state_set const &qs) const
	Computes the union of multiple states' ε-closures. More...
std::u32string	getShortestWord () const
	Searches the shortest UTF-32-encoded word accepted by this NFA. More...
std::string	getShortestUtf8Word () const
	Same as above for a UTF-8-encoded word. More...
std::string const &	getLabelOf (size_t q) const
	Puts a name to an index. More...
std::string	getLabelOf (std::valarray< bool > const &qs) const
	Puts a name to a set of indices. More...
std::string	getLabelOf (state_set const &qs) const
	Puts a name to a set of states. More...
state_set	decodeSet (std::valarray< bool > const &qs) const
	Translates a set of states from bool to set representation. More...
std::valarray< bool >	encodeSet (state_set const &qs) const
	Translates a set of states from set to bool representation. More...
std::string const &	getInitialState () const
	Names this NFA's initial state. More...
std::vector< std::string > const &	getStates () const
	Fetches this NFA's set of states in order of internal representation. More...
state_set	getStatesSet () const
	Fetches this NFA's set of states as a set of (references to) strings. More...
std::valarray< bool >	getStatesBools () const
	Fetches this NFA's set of states encoded as an array of bools. More...
std::vector< char32_t > const &	getAlphabet () const
	Fetches this NFA's set of processable symbols. More...
std::vector< std::string > const &	getUtf8Alphabet () const
	Fetches this NFA's set of processable symbols as UTF-8-encoded strings. More...
size_t	getNumberOfStates () const
	Counts this NFA's states. More...
size_t	getNumberOfSymbols () const
	Counts this NFA's alphabet symbols. More...
bool	isAccepting (size_t qi) const
	Tests whether a state is an accept state within this NFA. More...
bool	isAccepting (std::string const &q) const
	Tests whether a state is an accept state within this NFA. More...
bool	hasAccepting (std::valarray< bool > const &qs) const
	Tests whether a set of states contains an accept state within this NFA. More...
bool	hasAccepting (state_set const &qs) const
	Tests whether a set of states contains an accept state within this NFA. More...

Static Public Member Functions
static nfa::builder	unite (nfa const &n1, nfa const &n2)
	Creates a builder for an NFA accepting the union of the languages of two NFAs. More...
static nfa::builder	intersect (nfa const &n1, nfa const &n2)
	Creates a builder for an NFA accepting the intersection of the languages of two NFAs. More...
static nfa::builder	subtract (nfa const &n1, nfa const &n2)
	Creates a builder for an NFA accepting the set difference of the languages of two NFAs. More...
static nfa::builder	complement (nfa const &n)
	Creates a builder for an NFA accepting the complement of the language of an NFA. More...

Detailed Description

Represents nondeterministic finite automata with ε-moves.

Instances of this class are completely immutable. The builder class is the preferred way of constructing NFAs.

By convention, the state with index 0 is the initial state.

Definition at line 25 of file nfa.h.

Member Typedef Documentation

state_set

typedef std::unordered_set<std::reference_wrapper<std::string const>, hash_reference_string_const, equal_to_reference_string_const> reg::nfa::state_set

Nicer name for sets of names of states. Should store references to names in getStates.

Definition at line 28 of file nfa.h.

Constructor & Destructor Documentation

nfa() [1/5]

reg::nfa::nfa

(

)

Constructs an NFA accepting the empty language ∅.

Definition at line 80 of file nfa.cpp.

: p(new pImpl) {}

nfa() [2/5]

reg::nfa::nfa

(

nfa const &

n

)

Copy-constructs an NFA by copying another one's private implementation object.

Definition at line 621 of file nfa.cpp.

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

nfa() [3/5]

reg::nfa::nfa

(

nfa &&

n

)

Move-constructs an NFA by stealing another one's private implementation object.

The other NFA will be accepting the empty language ∅ afterwards.

Definition at line 625 of file nfa.cpp.

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

nfa() [4/5]

reg::nfa::nfa

(

dfa const &

d

)

Constructs an NFA from a DFA.

Definition at line 631 of file nfa.cpp.

: nfa(builder(d).build()) {}

nfa() [5/5]

reg::nfa::nfa

(

nfa::builder &

b

)

Constructs an NFA from a builder.

Definition at line 628 of file nfa.cpp.

: nfa(b.build()) {}

Member Function Documentation

complement()

nfa::builder reg::nfa::complement ( nfa const &  n )

static

Creates a builder for an NFA accepting the complement of the language of an NFA.

The input NFAs' state names will probably be mangled in the created NFA.

Parameters

n

the NFA

Returns

builder for an NFA accepting all words not accepted by the input NFA (provided they can be built from symbols of that NFA's alphabet)

Definition at line 616 of file nfa.cpp.

                                       {
  return nfa::builder(dfa::builder(n).complement().minimize().build());
}

decodeSet()

nfa::state_set reg::nfa::decodeSet

(

std::valarray< bool > const &

qs

)

const

Translates a set of states from bool to set representation.

Parameters

qs	valarray with true at indices of states in question

Returns

set of labels of the states in question

Definition at line 405 of file nfa.cpp.

                                                          {
  state_set states;
  states.reserve(getNumberOfStates());
  size_t range = min(qs.size(), getNumberOfStates());
  for (size_t q = 0; q < range; q++) {
    if (qs[q]) {
      states.emplace(getStates()[q]);
    }
  }
  return states;
}

delta() [1/5]

valarray< bool > const & reg::nfa::delta	(	size_t	qi,
		size_t	si
	)		const

Computes this NFA's transition function for a state index and a symbol index.

Parameters

qi	the state's index (< getNumberOfStates)
si	index of the symbol to process (∈ getAlphabet)

Returns

valarray with true at reached states' indices

Exceptions

std::out_of_range	if qi ≥ getNumberOfStates
std::domain_error	if si ≥ getNumberOfSymbols

Definition at line 105 of file nfa.cpp.

                                                           {
  if (si >= p->alphabet.size()) {
    throw std::domain_error("There is no symbol with index " + to_string(si));
  }
  if (qi >= p->labels.size()) {
    throw std::out_of_range("There is no state with index " + to_string(qi));
  }
  return p->transitions[qi][si];
}

delta() [2/5]

valarray< bool > const & reg::nfa::delta	(	size_t	qi,
		char32_t	symbol
	)		const

Computes this NFA's transition function for a state index and a symbol.

Parameters

qi	the state's index (< getNumberOfStates)
symbol	the symbol to process (∈ getAlphabet)

Returns

valarray with true at reached states' indices

Exceptions

std::out_of_range	if qi ≥ getNumberOfStates
std::domain_error	if symbol ∉ getAlphabet

Definition at line 123 of file nfa.cpp.

                                                                 {
  try {
    return delta(qi, index_of(p->alphabet, symbol));
  } catch (std::domain_error e) {
    throw std::domain_error(u8"δ is not defined for symbol " + converter.to_bytes(symbol));
  }
}

delta() [3/5]

valarray< bool > const & reg::nfa::delta	(	size_t	qi,
		std::string const &	utf8Symbol
	)		const

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

                                                                          {
  return delta(qi, converter.from_bytes(utf8Symbol)[0]);
}

delta() [4/5]

nfa::state_set reg::nfa::delta	(	std::string const &	q,
		char32_t	symbol
	)		const

Computes this NFA's transition function for a state index and a symbol.

Parameters

q	the state's label (∈ getStates)
symbol	the symbol to process (∈ getAlphabet)

Returns

set of reached states' labels

Exceptions

std::out_of_range	if qi ≥ getNumberOfStates
std::domain_error	if symbol ∉ getAlphabet

Definition at line 144 of file nfa.cpp.

                                                              {
  try {
    return decodeSet(delta(index_of(getStates(), q), symbol));
  } catch (std::out_of_range e) {
    throw std::out_of_range("There is no state named " + q);
  }
}

delta() [5/5]

nfa::state_set reg::nfa::delta	(	std::string const &	q,
		std::string const &	utf8Symbol
	)		const

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

                                                                       {
  return delta(q, converter.from_bytes(utf8Symbol)[0]);
}

deltaHat() [1/8]

valarray< bool > reg::nfa::deltaHat	(	size_t	qi,
		std::u32string const &	word
	)		const

Computes this NFA's transition function recursively for a string of symbols, starting in a state specified by its index.

Parameters

qi	the starting state's index (< getNumberOfStates)
word	the string of symbols to process (all of which ∈ getAlphabet)

Returns

valarray with true at reached states' indices

Exceptions

std::out_of_range	if qi ≥ getNumberOfStates
std::domain_error	if one the word symbols ∉ getAlphabet

Definition at line 165 of file nfa.cpp.

                                                                   {
  if (qi >= p->labels.size()) {
    throw std::out_of_range("There is no state with index " + to_string(qi));
  }
  valarray<bool> qs(p->labels.size());
  qs[qi] = true;
  return deltaHat(qs, word);
}

deltaHat() [2/8]

valarray< bool > reg::nfa::deltaHat	(	size_t	qi,
		std::string const &	utf8Word
	)		const

Same as above for a UTF-8-encoded string of symbols.

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

                                                                    {
  return deltaHat(qi, converter.from_bytes(utf8Word));
}

deltaHat() [3/8]

nfa::state_set reg::nfa::deltaHat	(	std::string const &	q,
		std::u32string const &	word
	)		const

Computes this NFA's transition function recursively for a string of symbols, starting in a state specified by its name.

Parameters

q	the starting state's label (∈ getStates)
word	the string of symbols to process (all of which ∈ getAlphabet)

Returns

set of reached states' labels

Exceptions

std::out_of_range	if q ∉ getStates
std::domain_error	if one the word symbols ∉ getAlphabet

Definition at line 187 of file nfa.cpp.

                                                                       {
  try {
    return decodeSet(deltaHat(index_of(getStates(), q), word));
  } catch (std::out_of_range e) {
    throw std::out_of_range("There is no state named " + q);
  }
}

deltaHat() [4/8]

nfa::state_set reg::nfa::deltaHat	(	std::string const &	q,
		std::string const &	utf8Word
	)		const

Same as above for a UTF-8-encoded string of symbols.

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

                                                                        {
  return deltaHat(q, converter.from_bytes(utf8Word));
}

deltaHat() [5/8]

valarray< bool > reg::nfa::deltaHat	(	std::valarray< bool > const &	qs,
		std::u32string const &	word
	)		const

Computes this NFA's transition function recursively for a string of symbols, starting in multiple specified states.

Parameters

qs	valarray with true at starting states' indices
word	the string of symbols to process (all of which ∈ getAlphabet)

Returns

valarray with true at reached states' indices

Exceptions

std::domain_error

if one of the word symbols ∉ getAlphabet

Definition at line 207 of file nfa.cpp.

                                                                                  {
  valarray<bool> ps = epsilonClosure(qs);
  for (char32_t symbol : word) {
    valarray<bool> reached(p->labels.size());
    size_t qi(0);
    for (bool qb : ps) {
      if (qb) {
        reached |= epsilonClosure(delta(qi, symbol));
      }
      qi++;
    }
    ps = move(reached);
  }
  return ps;
}

deltaHat() [6/8]

valarray< bool > reg::nfa::deltaHat	(	std::valarray< bool > const &	qs,
		std::string const &	utf8Word
	)		const

Same as above for a UTF-8-encoded string of symbols.

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

                                                                                   {
  return deltaHat(qs, converter.from_bytes(utf8Word));
}

deltaHat() [7/8]

nfa::state_set reg::nfa::deltaHat	(	nfa::state_set const &	qs,
		std::u32string const &	word
	)		const

Computes this NFA's transition function recursively for a string of symbols, starting in multiple states specified by their names.

Parameters

qs	set of starting states' labels
word	the string of symbols to process (all of which ∈ getAlphabet)

Returns

set of reached states' labels

Exceptions

std::domain_error

if one of the word symbols ∉ getAlphabet

Definition at line 235 of file nfa.cpp.

                                                                              {
  return decodeSet(deltaHat(encodeSet(qs), word));
}

deltaHat() [8/8]

nfa::state_set reg::nfa::deltaHat	(	nfa::state_set const &	qs,
		std::string const &	utf8Word
	)		const

Same as above for a UTF-8-encoded string of symbols.

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

                                                                               {
  return deltaHat(qs, converter.from_bytes(utf8Word));
}

encodeSet()

valarray< bool > reg::nfa::encodeSet

(

nfa::state_set const &

qs

)

const

Translates a set of states from set to bool representation.

Parameters

qs	set of labels of the states in question

Returns

valarray with true at indices of states in question

Definition at line 422 of file nfa.cpp.

                                                          {
  valarray<bool> states(getNumberOfStates());
  for (size_t qi = 0; qi < getNumberOfStates(); qi++) {
    states[qi] = qs.count(getStates()[qi]);
  }
  return states;
}

epsilonClosure() [1/4]

valarray< bool > const & reg::nfa::epsilonClosure

(

size_t

qi

)

const

Computes a state's ε-closure.

Parameters

qi	the state's index (< getNumberOfStates)

Returns

valarray with true at indices of states reachable without actual inputs

Exceptions

std::out_of_range

if qi ≥ getNumberOfStates

Definition at line 287 of file nfa.cpp.

                                                         {
  if (qi >= p->labels.size()) {
    throw std::out_of_range(
      string("There is no state with index ").append(std::to_string(qi))
    );
  }
  if (p->epsClosures[qi].size() == 0) {
    p->epsClosures[qi].resize(p->labels.size());
    p->epsClosures[qi][qi] = true;
    int growth(1);
    while (growth > 0) {
      growth = 0;
      valarray<bool> old(p->epsClosures[qi]);
      size_t qqi(0);
      for (bool qqb : old) {
        if (qqb) {
          size_t pi(0);
          for (bool pb : p->transitions[qqi][0]) {
            if (pb) {
              if (!p->epsClosures[qi][pi]) {
                growth++;
                p->epsClosures[qi][pi] = true;
              }
            }
            pi++;
          } // going through the true bools in transitions[qqi][0]
        }
        qqi++;
      } // going through the true bools in old
    }
  }
  return p->epsClosures[qi];
}

epsilonClosure() [2/4]

nfa::state_set reg::nfa::epsilonClosure

(

std::string const &

q

)

const

Computes a state's ε-closure.

Parameters

q	the state's label (∈ getStates)

Returns

set of labels of states reachable without actual inputs

Exceptions

std::out_of_range

if q ≥ getNumberOfStates

Definition at line 327 of file nfa.cpp.

                                                      {
  try {
    return decodeSet(epsilonClosure(index_of(getStates(), q)));
  } catch (std::out_of_range e) {
    throw std::out_of_range("There is no state named " + q);
  }
}

epsilonClosure() [3/4]

valarray< bool > reg::nfa::epsilonClosure

(

std::valarray< bool > const &

qs

)

const

Computes the union of multiple states' ε-closures.

Parameters

qs	valarray with true at indices of states in question

Returns

valarray with true at indices of states reachable without actual inputs

Definition at line 340 of file nfa.cpp.

                                                                 {
  valarray<bool> closure(p->labels.size());
  size_t range = min(qs.size(), getNumberOfStates());
  for (size_t q = 0; q < range; q++) {
    if (qs[q]) {
      closure |= epsilonClosure(q);
    }
  }
  return closure;
}

epsilonClosure() [4/4]

nfa::state_set reg::nfa::epsilonClosure

(

nfa::state_set const &

qs

)

const

Computes the union of multiple states' ε-closures.

Parameters

qs	set of labels of states in question

Returns

set of labels of states reachable without actual inputs

Definition at line 356 of file nfa.cpp.

                                                             {
  return decodeSet(epsilonClosure(encodeSet(qs)));
}

getAlphabet()

vector< char32_t > const & reg::nfa::getAlphabet

(

)

const

Fetches this NFA's set of processable symbols.

Returns

a vector containing all the valid symbol inputs for delta and deltaHat

Definition at line 466 of file nfa.cpp.

                                               {
  return p->alphabet;
}

getInitialState()

string const & reg::nfa::getInitialState

(

)

const

Names this NFA's initial state.

Returns

the initial state's name

Definition at line 434 of file nfa.cpp.

                                         {
  return getStates()[0];
}

getLabelOf() [1/3]

string const & reg::nfa::getLabelOf

(

size_t

qi

)

const

Puts a name to an index.

Parameters

qi	the state's index (< getNumberOfStates)

Returns

the state's name

Exceptions

std::out_of_range

if q ≥ getNumberOfStates

Definition at line 366 of file nfa.cpp.

                                             {
  return p->labels.at(qi);
}

getLabelOf() [2/3]

string reg::nfa::getLabelOf

(

std::valarray< bool > const &

qs

)

const

Puts a name to a set of indices.

Parameters

qs	valarray with true at indices of states in question

Returns

a comma-separated list of the states' names, surrounded by curly brackets

Definition at line 375 of file nfa.cpp.

                                                     {
  string label;
  size_t range = min(qs.size(), getNumberOfStates());
  for (size_t q = 0; q < range; q++) {
    if (qs[q]) {
      label = label.append(1, label.length() == 0 ? '{' : ',');
      label = label.append(p->labels.at(q));
    }
  }
  if (label.length() == 0) {
    return string("{}");
  } else {
    return label.append(1, '}');
  }
}

getLabelOf() [3/3]

string reg::nfa::getLabelOf

(

nfa::state_set const &

qs

)

const

Puts a name to a set of states.

Parameters

qs	set of labels of states in question

Returns

a comma-separated list of the states' names, surrounded by curly brackets

Definition at line 396 of file nfa.cpp.

                                                   {
  return getLabelOf(encodeSet(qs));
}

getNumberOfStates()

size_t reg::nfa::getNumberOfStates

(

)

const

Counts this NFA's states.

Returns

the number of states this NFA has

Definition at line 482 of file nfa.cpp.

                                    {
  return getStates().size();
}

getNumberOfSymbols()

size_t reg::nfa::getNumberOfSymbols

(

)

const

Counts this NFA's alphabet symbols.

Returns

the number of symbols this DFA can process

Definition at line 490 of file nfa.cpp.

                                     {
  return getAlphabet().size();
}

getShortestUtf8Word()

string reg::nfa::getShortestUtf8Word

(

)

const

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

Definition at line 277 of file nfa.cpp.

                                      {
  return converter.to_bytes(getShortestWord());
}

getShortestWord()

u32string reg::nfa::getShortestWord

(

)

const

Searches the shortest UTF-32-encoded word accepted by this NFA.

Returns

the shortest word leading to one of this NFA's accept states

Exceptions

std::logic_error

if the NFA doesn't accept any words

Definition at line 249 of file nfa.cpp.

                                     {
  if (p->accepting[0]) {
    return U"";
  }
  unordered_map<size_t, u32string> shortestWords(p->labels.size());
  size_t oldSize = 0;
  shortestWords.emplace(0, U"");
  while (shortestWords.size() > oldSize) {
    oldSize = shortestWords.size();
    for (auto const& stateWord : shortestWords) {
      for (auto symbol : p->alphabet) {
        valarray<bool> reached = deltaHat(stateWord.first, u32string(!!symbol, symbol));
        u32string shWord = stateWord.second + u32string(!!symbol, symbol);
        for (size_t q = 0; q < reached.size(); q++) { if (reached[q]) {
          if (p->accepting[q]) {
            return shWord;
          }
          if (shortestWords.find(q) == shortestWords.end()) {
            shortestWords.emplace(q, shWord);
          }
        }}
      }
    }
  }
  throw std::logic_error("This NFA doesn't accept any words!");
}

getStates()

vector< string > const & reg::nfa::getStates

(

)

const

Fetches this NFA's set of states in order of internal representation.

Returns

a vector containing the names of states that can be used as input for delta and deltaHat

Definition at line 442 of file nfa.cpp.

                                           {
  return p->labels;
}

getStatesBools()

valarray< bool > reg::nfa::getStatesBools

(

)

const

Fetches this NFA's set of states encoded as an array of bools.

Returns

an array of length getNumberOfStates, filled with true values

Definition at line 458 of file nfa.cpp.

                                         {
  return valarray<bool>(true, getNumberOfStates());
}

getStatesSet()

nfa::state_set reg::nfa::getStatesSet

(

)

const

Fetches this NFA's set of states as a set of (references to) strings.

Returns

a set containing references to the original state names

Definition at line 450 of file nfa.cpp.

                                     {
  return state_set(getStates().begin(), getStates().end());
}

getUtf8Alphabet()

vector< string > const & reg::nfa::getUtf8Alphabet

(

)

const

Fetches this NFA's set of processable symbols as UTF-8-encoded strings.

Returns

a vector containing all the valid symbol inputs for delta and deltaHat

Definition at line 474 of file nfa.cpp.

                                                 {
  return p->utf8Alphabet;
}

hasAccepting() [1/2]

bool reg::nfa::hasAccepting

(

std::valarray< bool > const &

qs

)

const

Tests whether a set of states contains an accept state within this NFA.

Parameters

qs	valarray with true at indices of states in question

Returns

true if the set of states contains an accept states, false else

Definition at line 528 of file nfa.cpp.

                                                     {
  size_t range = min(qs.size(), getNumberOfStates());
  for (size_t q = 0; q < range; q++) {
    if (qs[q] && p->accepting[q]) {
      return true;
    }
  }
  return false;
}

hasAccepting() [2/2]

bool reg::nfa::hasAccepting

(

nfa::state_set const &

qs

)

const

Tests whether a set of states contains an accept state within this NFA.

Parameters

qs	set of labels of states in question

Returns

true if the set of states contains an accept states, false else

Definition at line 543 of file nfa.cpp.

                                                   {
  for (size_t qi = 0; qi < getNumberOfStates(); qi++) {
    if (p->accepting[qi] && qs.count(getStates()[qi])) {
      return true;
    }
  }
  return false;
}

intersect()

nfa::builder reg::nfa::intersect ( nfa const &  n1, nfa const &  n2  )

static

Creates a builder for an NFA accepting the intersection of the languages of two NFAs.

The input NFAs' state names will be concatenated and collisions resolved by appending _ in the created NFA.

Parameters

n1	the first NFA
n2	the other NFA

Returns

builder for an NFA accepting all the words accepted by both of the input NFAs

Definition at line 587 of file nfa.cpp.

                                                      {
  return builder(n1).intersect(n2);
}

isAccepting() [1/2]

bool reg::nfa::isAccepting

(

size_t

qi

)

const

Tests whether a state is an accept state within this NFA.

Parameters

qi	the state's index (< getNumberOfStates)

Returns

true if the state is in the set of accept states, false else

Exceptions

std::out_of_range

if qi ≥ getNumberOfStates

Definition at line 500 of file nfa.cpp.

                                     {
  if (qi >= p->labels.size()) {
    throw std::out_of_range(
        string("There is no state with index ").append(std::to_string(qi))
    );
  }
  return p->accepting[qi];
}

isAccepting() [2/2]

bool reg::nfa::isAccepting

(

std::string const &

q

)

const

Tests whether a state is an accept state within this NFA.

Parameters

q	the state's label (∈ getStates)

Returns

true if the state is in the set of accept states, false else

Exceptions

std::out_of_range

if q ∉ getStates

Definition at line 515 of file nfa.cpp.

                                           {
  try {
    return isAccepting(index_of(getStates(), q));
  } catch (std::out_of_range e) {
    throw std::out_of_range("There is no state named " + q);
  }
}

operator!=()

bool reg::nfa::operator!=

(

nfa const &

n

)

const

Tests whether this NFA doesn't accept the same language as another one.

Definition at line 93 of file nfa.cpp.

                                       {
  return p->getEquivalentDfa(this) != n.p->getEquivalentDfa(&n);
}

operator=() [1/2]

nfa & reg::nfa::operator=

(

nfa const &

n

)

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

Definition at line 634 of file nfa.cpp.

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

operator=() [2/2]

nfa & reg::nfa::operator=

(

nfa &&

n

)

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

The other NFA will be accepting the empty language ∅ afterwards.

Definition at line 643 of file nfa.cpp.

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

operator==()

bool reg::nfa::operator==

(

nfa const &

n

)

const

Tests whether this NFA accepts exactly the same language as another one.

Definition at line 88 of file nfa.cpp.

                                       {
  return p->getEquivalentDfa(this) == n.p->getEquivalentDfa(&n);
}

subtract()

nfa::builder reg::nfa::subtract ( nfa const &  n1, nfa const &  n2  )

static

Creates a builder for an NFA accepting the set difference of the languages of two NFAs.

The input NFAs' state names will probably be mangled in the created NFA.

Parameters

n1	the first NFA
n2	the other NFA

Returns

builder for an NFA accepting all the words accepted by the first but not the other input NFA

Definition at line 599 of file nfa.cpp.

                                                     {
  dfa::builder b2(n2);
  for (auto symbol : n1.getAlphabet()) {
    b2.addSymbol(symbol);
  }
  b2.complement().minimize();
  return builder(n1).intersect(builder(b2.build()).build());
}

unite()

nfa::builder reg::nfa::unite ( nfa const &  n1, nfa const &  n2  )

static

Creates a builder for an NFA accepting the union of the languages of two NFAs.

The input NFAs' state names will be prepended with either 1 or 2 in the created NFA.

Parameters

n1	the first NFA
n2	the other NFA

Returns

builder for an NFA accepting all the words accepted by any of the input NFAs

Definition at line 575 of file nfa.cpp.

                                                  {
  return builder(n1).unite(n2);
}

---

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

• nfa.h
• nfa.cpp