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

#include <nfa.h>

Classes
class	builder
	Constructs NFAs step by step. More...

struct	pImpl
	Private implementation details of NFAs. 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 q, char32_t symbol) const
	Computes this NFA's transition function for a state and a symbol. More...

std::valarray< bool > const &	delta (size_t q, std::string const &utf8Symbol) const
	Same as above for a UTF-8-encoded symbol. More...

std::valarray< bool >	deltaHat (size_t q, std::u32string const &word) const
	Computes this NFA's transition function recursively for a string of symbols, starting in a specified state. More...

std::valarray< bool >	deltaHat (size_t 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...

std::valarray< bool > const &	epsilonClosure (size_t 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...

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, INCLUDING POTENTIAL INFINITE LOOP. 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::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...

bool	isAccepting (size_t 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...

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

79 : 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 395 of file nfa.cpp.

395 : 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 399 of file nfa.cpp.

399 : 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 405 of file nfa.cpp.

405 : nfa(builder(n).build()) {}

reg::nfa::nfa

nfa()

Constructs an NFA accepting the empty language ∅.

Definition: nfa.cpp:79

◆ nfa() [5/5]

reg::nfa::nfa ( nfa::builder & b )

Constructs an NFA from a builder.

Definition at line 402 of file nfa.cpp.

402 : nfa(b.build()) {}

reg::nfa::nfa

nfa()

Constructs an NFA accepting the empty language ∅.

Definition: nfa.cpp:79

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

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

◆ delta() [1/2]

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

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

Parameters

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

Returns: valarray with true at reached states' indices

Definition at line 102 of file nfa.cpp.

                                                                 {
   size_t i = index_of(p->alphabet, symbol);
   if (i >= p->alphabet.size()) {
     #ifdef __EXCEPTIONS
     throw std::domain_error(
       string(u8"δ is not defined for symbol ") + converter.to_bytes(symbol)
     );
     #endif
   }
   if (q >= p->labels.size()) {
     #ifdef __EXCEPTIONS
     throw std::out_of_range(
       string("There is no state with index ").append(std::to_string(q))
     );
     #endif
   }
   return p->transitions[q][i];
 }

◆ delta() [2/2]

valarray< bool > const & reg::nfa::delta	(	size_t	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 122 of file nfa.cpp.

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

◆ deltaHat() [1/4]

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

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

Parameters

q	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

Definition at line 132 of file nfa.cpp.

                                                                      {
   valarray<bool> qs(p->labels.size());
   qs[q] = true;
   return deltaHat(qs, word);
 }

◆ deltaHat() [2/4]

valarray< bool > reg::nfa::deltaHat	(	size_t	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 139 of file nfa.cpp.

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

◆ deltaHat() [3/4]

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 (the `size` of which == getNumberOfStates)
word	the string of symbols to process (all of which ∈ getAlphabet)

Returns: valarray with true at reached states' indices

Definition at line 149 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() [4/4]

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

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

◆ epsilonClosure() [1/2]

valarray< bool > const & reg::nfa::epsilonClosure ( size_t q ) const

Computes a state's ε-closure.

Parameters

q	the state's index (< getNumberOfStates)

Returns: valarray with true at indices of states reachable without actual inputs

Definition at line 217 of file nfa.cpp.

                                                         {
   if (p->epsClosures[q].size() == 0) {
     p->epsClosures[q].resize(p->labels.size());
     p->epsClosures[q][q] = true;
     int growth(1);
     while (growth > 0) {
       growth = 0;
       valarray<bool> old(p->epsClosures[q]);
       size_t qi(0);
       for (bool qb : old) {
         if (qb) {
           size_t pi(0);
           for (bool pb : p->transitions[qi][0]) {
             if (pb) {
               if (!p->epsClosures[q][pi]) {
                 growth++;
                 p->epsClosures[q][pi] = true;
               }
             }
             pi++;
           } // going through the true bools in transitions[qi][0]
         }
         qi++;
       } // going through the true bools in old
     }
   }
   return p->epsClosures[q];
 }

◆ epsilonClosure() [2/2]

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 (the `size` of which == getNumberOfStates)

Returns: valarray with true at indices of states reachable without actual inputs

Definition at line 251 of file nfa.cpp.

                                                                  {
   valarray<bool> closure(p->labels.size());
   size_t qi(0);
   for (bool qb : qs) {
     if (qb) {
       closure |= epsilonClosure(qi);
     }
     qi++;
   } // going through the true bools in qs
   return closure;
 }

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

                                                {
   return p->alphabet;
 }

◆ getLabelOf() [1/2]

string const & reg::nfa::getLabelOf ( size_t q ) const

Puts a name to an index.

Parameters

q	the state's index (< getNumberOfStates)

Returns: the state's name

Definition at line 268 of file nfa.cpp.

                                             {
   return p->labels[q];
 }

◆ getLabelOf() [2/2]

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 (the `size` of which == getNumberOfStates)

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

Definition at line 277 of file nfa.cpp.

                                                      {
   string label;
   size_t qi(0);
   for (bool qb : qs) {
     if (qb) {
       label = label.append(1, label.length() == 0 ? '{' : ',');
       label = label.append(p->labels[qi]);
     }
     qi++;
   }
   if (label.length() == 0) {
     return string("{}");
   } else {
     return label.append(1, '}');
   }
 }

◆ getNumberOfStates()

size_t reg::nfa::getNumberOfStates ( ) const

Counts this NFA's states.

Returns: the number of states this NFA has

Definition at line 314 of file nfa.cpp.

                                     {
   return p->labels.size();
 }

◆ getShortestUtf8Word()

string reg::nfa::getShortestUtf8Word ( ) const

Same as above for a UTF-8-encoded word, INCLUDING POTENTIAL INFINITE LOOP.

Definition at line 208 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.

LOOPS INFINITELY FOR NFA WITH AN EMPTY LANGUAGE!

Hint: Compare with the empty-language nfa() before using this method:

nfa empty();
if (myNfa != empty) {
  myNfa.getShortestWord();
}

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

Definition at line 183 of file nfa.cpp.

                                      {
   if (p->accepting[0]) {
     return U"";
   }
   unordered_map<size_t, u32string> shortestWords(p->labels.size());
   shortestWords.emplace(0, U"");
   while (true) {
     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);
           }
         }}
       }
     }
   }
 }

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

                                                  {
   return p->utf8Alphabet;
 }

◆ hasAccepting()

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 (the `size` of which == getNumberOfStates)

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

Definition at line 332 of file nfa.cpp.

                                                      {
   for (size_t q = 0; q < getNumberOfStates(); q++) {
     if (qs[q] && p->accepting[q]) {
       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 361 of file nfa.cpp.

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

◆ isAccepting()

bool reg::nfa::isAccepting ( size_t q ) const

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

Parameters

q	the state's index (< getNumberOfStates)

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

Definition at line 323 of file nfa.cpp.

                                     {
   return p->accepting[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 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 408 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 417 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 373 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 349 of file nfa.cpp.

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

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

Classes

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ nfa() [1/5]

◆ nfa() [2/5]

◆ nfa() [3/5]

◆ nfa() [4/5]

◆ nfa() [5/5]

Member Function Documentation

◆ complement()

◆ delta() [1/2]

◆ delta() [2/2]

◆ deltaHat() [1/4]

◆ deltaHat() [2/4]

◆ deltaHat() [3/4]

◆ deltaHat() [4/4]

◆ epsilonClosure() [1/2]

◆ epsilonClosure() [2/2]

◆ getAlphabet()

◆ getLabelOf() [1/2]

◆ getLabelOf() [2/2]

◆ getNumberOfStates()

◆ getShortestUtf8Word()

◆ getShortestWord()

◆ getUtf8Alphabet()

◆ hasAccepting()

◆ intersect()

◆ isAccepting()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ subtract()

◆ unite()