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
std::string	getShortestUtf8Word () const
std::string const &	getLabelOf (size_t q) const
std::string	getLabelOf (std::valarray< bool > const &qs) const
std::string	getLabelOf (state_set const &qs) const
std::string	to_string (std::valarray< bool > const &qs) const
	Puts a name to a set of indices. More...
std::string	to_string (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
size_t	getNumberOfSymbols () const
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	isAccepting (std::valarray< bool > const &qs) const
	Tests whether a set of states contains an accept state within this NFA. More...
bool	isAccepting (state_set const &qs) const
	Tests whether a set of states contains an accept state within this NFA. More...
bool	hasAccepting (std::valarray< bool > const &qs) const
bool	hasAccepting (state_set const &qs) const

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...

Friends
std::u32string	findShortestWord (nfa const &n)
	Searches the shortest UTF-32-encoded word accepted by a given NFA. More...
std::string	findShortestUtf8Word (nfa const &n)
	Same as above for a UTF-8-encoded word. 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 79 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 622 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 626 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 632 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 629 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 617 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 380 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 104 of file nfa.cpp.

                                                           {
  if (si >= p->alphabet.size()) {
    throw std::domain_error("There is no symbol with index " + std::to_string(si));
  }
  if (qi >= p->labels.size()) {
    throw std::out_of_range("There is no state with index " + std::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 122 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 131 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 143 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 152 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 164 of file nfa.cpp.

                                                                   {
  if (qi >= p->labels.size()) {
    throw std::out_of_range("There is no state with index " + std::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 174 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 186 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 195 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 206 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 223 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 234 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 239 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 397 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 259 of file nfa.cpp.

                                                         {
  if (qi >= p->labels.size()) {
    throw std::out_of_range("There is no state with index " + 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 297 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 310 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 326 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 441 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 409 of file nfa.cpp.

                                         {
  return getStates()[0];
}

getLabelOf() [1/3]

string const & reg::nfa::getLabelOf

(

size_t

qi

)

const

Deprecated:

Use getStates and std::vector::at instead.

Definition at line 331 of file nfa.cpp.

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

getLabelOf() [2/3]

string reg::nfa::getLabelOf

(

std::valarray< bool > const &

qs

)

const

Deprecated:

Old name of to_string.

Definition at line 366 of file nfa.cpp.

                                                     {
  return to_string(qs);
}

getLabelOf() [3/3]

string reg::nfa::getLabelOf

(

nfa::state_set const &

qs

)

const

Deprecated:

Old name of to_string.

Definition at line 371 of file nfa.cpp.

                                                   {
  return to_string(qs);
}

getNumberOfStates()

size_t reg::nfa::getNumberOfStates

(

)

const

Deprecated:

Use getStates and std::vector::size instead.

Definition at line 454 of file nfa.cpp.

                                    {
  return getStates().size();
}

getNumberOfSymbols()

size_t reg::nfa::getNumberOfSymbols

(

)

const

Deprecated:

Use getStates and std::vector::size instead.

Definition at line 459 of file nfa.cpp.

                                     {
  return getAlphabet().size();
}

getShortestUtf8Word()

string reg::nfa::getShortestUtf8Word

(

)

const

Deprecated:

Old way of accessing reg::findShortestUtf8Word.

Definition at line 249 of file nfa.cpp.

                                      {
  return findShortestUtf8Word(*this);
}

getShortestWord()

u32string reg::nfa::getShortestWord

(

)

const

Deprecated:

Old way of accessing reg::findShortestWord.

Definition at line 244 of file nfa.cpp.

                                     {
  return findShortestWord(*this);
}

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 417 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 433 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 425 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 449 of file nfa.cpp.

                                                 {
  return p->utf8Alphabet;
}

hasAccepting() [1/2]

bool reg::nfa::hasAccepting

(

std::valarray< bool > const &

qs

)

const

Deprecated:

Old name of hasAccepting.

Definition at line 520 of file nfa.cpp.

                                                     {
  return isAccepting(qs);
}

hasAccepting() [2/2]

bool reg::nfa::hasAccepting

(

nfa::state_set const &

qs

)

const

Deprecated:

Old name of hasAccepting.

Definition at line 525 of file nfa.cpp.

                                                   {
  return isAccepting(qs);
}

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

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

isAccepting() [1/4]

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

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

isAccepting() [2/4]

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 482 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);
  }
}

isAccepting() [3/4]

bool reg::nfa::isAccepting

(

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 495 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;
}

isAccepting() [4/4]

bool reg::nfa::isAccepting

(

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

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

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 92 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 635 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 644 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 87 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 600 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());
}

to_string() [1/2]

string reg::nfa::to_string

(

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 340 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, '}');
  }
}

to_string() [2/2]

string reg::nfa::to_string

(

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

                                                  {
  return getLabelOf(encodeSet(qs));
}

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

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

Friends And Related Function Documentation

findShortestUtf8Word

std::string findShortestUtf8Word ( nfa const &  n )

friend

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

Definition at line 564 of file nfa.cpp.

                                          {
  return converter.to_bytes(findShortestWord(n));
}

findShortestWord

std::u32string findShortestWord ( nfa const &  n )

friend

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

Parameters

n

the NFA

Returns

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

Exceptions

std::logic_error

if the NFA doesn't accept any words

Definition at line 535 of file nfa.cpp.

                                         {
  auto const& p = n.p;
  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 = n.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!");
}

---

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

• nfa.h
• nfa.cpp