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 existing state names. 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 &	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...
	operator dfa const & () const
	Returns a DFA accepting the same language as this NFA. More...
bool	operator== (nfa const &n) const
	Checks whether this NFA describes the same regular language as another object. More...
bool	operator!= (nfa const &n) const
	Checks whether this NFA describes a different regular language than another object. 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 23 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 existing state names.

Definition at line 26 of file nfa.h.

Constructor & Destructor Documentation

nfa() [1/3]

reg::nfa::nfa

(

)

Constructs an NFA accepting the empty language ∅.

Definition at line 68 of file nfa.cpp.

: p(new pImpl) {}

nfa() [2/3]

reg::nfa::nfa

(

nfa const &

n

)

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

Definition at line 626 of file nfa.cpp.

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

nfa() [3/3]

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

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

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

                                                          {
  nfa::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 108 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 126 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 135 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 147 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 156 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 168 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 178 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 190 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 199 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 210 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 227 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 238 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 243 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 401 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 263 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 301 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 314 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 330 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 445 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 413 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 335 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 370 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 375 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 458 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 463 of file nfa.cpp.

                                     {
  return getAlphabet().size();
}

getShortestUtf8Word()

string reg::nfa::getShortestUtf8Word

(

)

const

Deprecated:

Old way of accessing reg::findShortestUtf8Word.

Definition at line 253 of file nfa.cpp.

                                      {
  return findShortestUtf8Word(*this);
}

getShortestWord()

u32string reg::nfa::getShortestWord

(

)

const

Deprecated:

Old way of accessing reg::findShortestWord.

Definition at line 248 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 421 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 437 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 429 of file nfa.cpp.

                                     {
  return nfa::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 453 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 524 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 529 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 592 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 473 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 486 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 499 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 514 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 dfa const &()

reg::nfa::operator dfa const &

(

)

const

Returns a DFA accepting the same language as this NFA.

operator!=()

bool reg::nfa::operator!=

(

nfa const &

n

)

const

Checks whether this NFA describes a different regular language than another object.

Returns

false if this NFA's language is exactly the same as the other object's, true else

Definition at line 96 of file nfa.cpp.

                                       {
  return static_cast<dfa const&>(*this).operator!=(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 633 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 642 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

Checks whether this NFA describes the same regular language as another object.

Returns

false if this NFA's language is exactly the same as the other object's, true else

Definition at line 88 of file nfa.cpp.

                                       {
  return static_cast<dfa const&>(*this).operator==(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 604 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 344 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 365 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 580 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 568 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 539 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