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 &	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::string const &	getLabelOf (size_t q) const
	Puts a name to an index. More...

std::string	getLabelOf (std::valarray< bool > 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...

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/3]

reg::nfa::nfa ( )

Constructs an NFA accepting the empty language ∅.

Definition at line 82 of file nfa.cpp.

82 : 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 301 of file nfa.cpp.

301 : 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 305 of file nfa.cpp.

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

Member Function Documentation

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

                                                                 {
   size_t i = distance(
     p->alphabet.begin(),
     find(p->alphabet.begin(), p->alphabet.end(), symbol)
   );
   if (i >= p->alphabet.size()) {
     #ifdef __EXCEPTIONS
     throw std::domain_error(
       string(u8"δ is not defined for symbol ").append(1, 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 129 of file nfa.cpp.

                                                                          {
   return delta(q, expression::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 140 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 147 of file nfa.cpp.

                                                                    {
   return deltaHat(q, expression::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 158 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 175 of file nfa.cpp.

                                                                                    {
   return deltaHat(qs, expression::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 185 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 220 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 268 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 237 of file nfa.cpp.

                                             {
   return p->labels[q];
 }

◆ getLabelOf() [2/2]

string reg::nfa::getLabelOf ( std::valarray< bool > 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 246 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 286 of file nfa.cpp.

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

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

                                                  {
   return p->utf8Alphabet;
 }

◆ 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 296 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 95 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 308 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 317 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 90 of file nfa.cpp.

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

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

Classes

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ nfa() [1/3]

◆ nfa() [2/3]

◆ nfa() [3/3]

Member Function Documentation

◆ 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()

◆ getUtf8Alphabet()

◆ isAccepting()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()