Represents deterministic finite automata. More...

#include <dfa.h>

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

struct	pImpl
	Private implementation details of DFAs. More...

Public Member Functions
	dfa ()
	Constructs a DFA accepting the empty language ∅. More...

	dfa (dfa const &d)
	Copy-constructs a DFA by copying another one's private implementation object. More...

	dfa (dfa &&d)
	Move-constructs a DFA by stealing another one's private implementation object. More...

dfa &	operator= (dfa const &d)
	Copy-assigns this DFA by copying another one's private implementation object. More...

dfa &	operator= (dfa &&d)
	Move-assigns this DFA by stealing another one's private implementation object. More...

	operator nfa const & () const
	Returns an NFA accepting the same language as this DFA. More...

bool	operator== (dfa const &d) const
	Tests whether this DFA accepts exactly the same language as another one. More...

bool	operator!= (dfa const &d) const
	Tests whether this DFA doesn't accept the same language as another one. More...

bool	operator== (nfa const &d) const
	Tests whether this DFA accepts exactly the same language as another object. More...

bool	operator!= (nfa const &d) const
	Tests whether this DFA doesn't accept the same language as another object. More...

size_t	delta (size_t qi, size_t si) const
	Computes this DFA's transition function for a state index and a symbol index. More...

size_t	delta (size_t qi, char32_t symbol) const
	Computes this DFA's transition function for a state index and a symbol. More...

size_t	delta (size_t qi, std::string const &utf8Symbol) const
	Same as above for a UTF-8-encoded symbol. More...

std::string const &	delta (std::string const &q, char32_t symbol) const
	Computes this DFA's transition function for a state label and a symbol. More...

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

size_t	deltaHat (size_t qi, std::u32string const &word) const
	Computes this DFA's transition function recursively for a string of symbols, starting in a state specified by its index. More...

size_t	deltaHat (size_t qi, std::string const &utf8Word) const
	Same as above for a string of UTF-8-encoded symbols. More...

std::string const &	deltaHat (std::string const &q, std::u32string const &word) const
	Computes this DFA's transition function recursively for a string of symbols, starting in a state specified by its name. More...

std::string const &	deltaHat (std::string const &q, std::string const &utf8Word) const
	Same as above for a string of UTF-8-encoded symbols. More...

std::u32string	getShortestWord () const

std::string	getShortestUtf8Word () const

std::string const &	getLabelOf (size_t qi) const

std::string const &	getInitialState () const
	Names this DFA's initial state. More...

std::vector< std::string > const &	getStates () const
	Fetches this DFA's set of states. More...

std::vector< char32_t > const &	getAlphabet () const
	Fetches this DFA's set of processable symbols. More...

std::vector< std::string > const &	getUtf8Alphabet () const
	Fetches this DFA'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 DFA. More...

bool	isAccepting (std::string const &q) const
	Tests whether a state is an accept state within this DFA. More...

Static Public Member Functions
static dfa::builder	unite (dfa const &d1, dfa const &d2)
	Creates a builder for a DFA accepting the union of the languages of two DFAs. More...

static dfa::builder	intersect (dfa const &d1, dfa const &d2)
	Creates a builder for a DFA accepting the intersection of the languages of two DFAs. More...

static dfa::builder	subtract (dfa const &d1, dfa const &d2)
	Creates a builder for a DFA accepting the set difference of the languages of two DFAs. More...

static dfa::builder	complement (dfa const &d)
	Creates a builder for a DFA accepting the complement of the language of a DFA. More...

Friends
std::u32string	findShortestWord (dfa const &d)
	Searches the shortest UTF-32-encoded word accepted by a given DFA. More...

std::string	findShortestUtf8Word (dfa const &d)
	Same as above for a UTF-8-encoded word. More...

Detailed Description

Represents deterministic finite automata.

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

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

Definition at line 21 of file dfa.h.

Constructor & Destructor Documentation

◆ dfa() [1/3]

reg::dfa::dfa ( )

Constructs a DFA accepting the empty language ∅.

Definition at line 127 of file dfa.cpp.

127 : p(new pImpl) {}

◆ dfa() [2/3]

reg::dfa::dfa ( dfa const & d )

Copy-constructs a DFA by copying another one's private implementation object.

Definition at line 137 of file dfa.cpp.

137 : p(new pImpl(*(d.p))) {}

◆ dfa() [3/3]

reg::dfa::dfa ( dfa && d )

Move-constructs a DFA by stealing another one's private implementation object.

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

Definition at line 141 of file dfa.cpp.

141 : p(new pImpl) {p.swap(d.p);}

Member Function Documentation

◆ complement()

dfa::builder reg::dfa::complement ( dfa const & d )

static

Creates a builder for a DFA accepting the complement of the language of a DFA.

The input DFAs' state names will be retained in the created DFA.

Parameters

d the DFA

Returns: builder fo a DFA accepting all words not accepted by the input DFA (provided they can be built from symbols of that DFA's alphabet)

Definition at line 497 of file dfa.cpp.

                                        {
   return dfa::builder(d).complement();
 }

◆ delta() [1/5]

size_t reg::dfa::delta	(	size_t	qi,
		size_t	si
	)		const

Computes this DFA'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 (< getNumberOfSymbols)

Returns: the reached state's index

Exceptions

std::out_of_range	if `qi` ≥ getNumberOfStates
std::domain_error	if `si` ∉ getAlphabet

Definition at line 239 of file dfa.cpp.

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

◆ delta() [2/5]

size_t reg::dfa::delta	(	size_t	qi,
		char32_t	symbol
	)		const

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

Parameters

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

Returns: the reached state's index

Exceptions

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

Definition at line 257 of file dfa.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]

size_t reg::dfa::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 266 of file dfa.cpp.

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

◆ delta() [4/5]

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

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

Parameters

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

Returns: the reached state's label

Exceptions

std::out_of_range	if `q` ∉ getStates
std::domain_error	if `symbol` ∉ getAlphabet

Definition at line 278 of file dfa.cpp.

                                                                {
   try {
     return getStates()[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]

string const & reg::dfa::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 287 of file dfa.cpp.

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

◆ deltaHat() [1/4]

size_t reg::dfa::deltaHat	(	size_t	qi,
		std::u32string const &	word
	)		const

Computes this DFA'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: the reached state's index

Exceptions

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

Definition at line 299 of file dfa.cpp.

                                                            {
   for (char32_t symbol : word) {
     qi = delta(qi, symbol);
   }
   return qi;
 }

◆ deltaHat() [2/4]

size_t reg::dfa::deltaHat	(	size_t	q,
		std::string const &	utf8Word
	)		const

Same as above for a string of UTF-8-encoded 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 307 of file dfa.cpp.

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

◆ deltaHat() [3/4]

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

Computes this DFA'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: the reached state's index

Exceptions

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

Definition at line 319 of file dfa.cpp.

                                                                         {
   return p->labels[deltaHat(index_of(getStates(), q), word)];
 }

◆ deltaHat() [4/4]

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

Same as above for a string of UTF-8-encoded 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 324 of file dfa.cpp.

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

◆ getAlphabet()

vector< char32_t > const & reg::dfa::getAlphabet ( ) const

Fetches this DFA's set of processable symbols.

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

Definition at line 363 of file dfa.cpp.

                                                {
   return p->alphabet;
 }

◆ getInitialState()

string const & reg::dfa::getInitialState ( ) const

Names this DFA's initial state.

Returns: the initial state's name

Definition at line 347 of file dfa.cpp.

                                          {
   return getStates()[0];
 }

◆ getLabelOf()

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

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

Definition at line 339 of file dfa.cpp.

                                             {
   return getStates().at(q);
 }

◆ getNumberOfStates()

size_t reg::dfa::getNumberOfStates ( ) const

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

Definition at line 376 of file dfa.cpp.

                                     {
   return getStates().size();
 }

◆ getNumberOfSymbols()

size_t reg::dfa::getNumberOfSymbols ( ) const

Deprecated:: Use getAlphabet and std::vector::size instead.

Definition at line 381 of file dfa.cpp.

                                      {
   return getAlphabet().size();
 }

◆ getShortestUtf8Word()

string reg::dfa::getShortestUtf8Word ( ) const

Deprecated:: Old way of accessing reg::findShortestUtf8Word.

Definition at line 334 of file dfa.cpp.

                                       {
   return findShortestUtf8Word(*this);
 }

◆ getShortestWord()

u32string reg::dfa::getShortestWord ( ) const

Deprecated:: Old way of accessing reg::findShortestWord.

Definition at line 329 of file dfa.cpp.

                                      {
   return findShortestWord(*this);
 }

◆ getStates()

vector< string > const & reg::dfa::getStates ( ) const

Fetches this DFA's set of states.

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

Definition at line 355 of file dfa.cpp.

                                            {
   return p->labels;
 }

◆ getUtf8Alphabet()

vector< string > const & reg::dfa::getUtf8Alphabet ( ) const

Fetches this DFA'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 371 of file dfa.cpp.

                                                  {
   return p->utf8Alphabet;
 }

◆ intersect()

dfa::builder reg::dfa::intersect	(	dfa const &	d1,
		dfa const &	d2
	)

static

Creates a builder for a DFA accepting the intersection of the languages of two DFAs.

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

Parameters

d1	the first DFA
d2	the other DFA

Returns: builder for a DFA accepting all the words accepted by both of the input DFAs

Definition at line 469 of file dfa.cpp.

                                                       {
   return builder(d1).intersect(d2);
 }

◆ isAccepting() [1/2]

bool reg::dfa::isAccepting ( size_t qi ) const

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

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 391 of file dfa.cpp.

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

◆ isAccepting() [2/2]

bool reg::dfa::isAccepting ( std::string const & q ) const

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

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 404 of file dfa.cpp.

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

◆ operator nfa const &()

reg::dfa::operator nfa const & ( ) const

Returns an NFA accepting the same language as this DFA.

◆ operator!=() [1/2]

bool reg::dfa::operator!= ( dfa const & d ) const

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

Definition at line 221 of file dfa.cpp.

221 {return !operator==(d);}

reg::dfa::operator==

bool operator==(dfa const &d) const

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

Definition: dfa.cpp:177

◆ operator!=() [2/2]

bool reg::dfa::operator!= ( nfa const & n ) const

Tests whether this DFA doesn't accept the same language as another object.

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 229 of file dfa.cpp.

229 {return !operator==(n);}

reg::dfa::operator==

bool operator==(dfa const &d) const

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

Definition: dfa.cpp:177

◆ operator=() [1/2]

dfa & reg::dfa::operator= ( dfa const & d )

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

Definition at line 144 of file dfa.cpp.

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

◆ operator=() [2/2]

dfa & reg::dfa::operator= ( dfa && d )

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

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

Definition at line 153 of file dfa.cpp.

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

◆ operator==() [1/2]

bool reg::dfa::operator== ( dfa const & d ) const

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

More specifically, checks whether this DFA's initial state is indistinguishable from the other one's.

Definition at line 177 of file dfa.cpp.

                                        {
   forward_list<char32_t> unitedAlphabet(p->alphabet.begin(), p->alphabet.end());
   size_t unitedAlphabetSize(p->alphabet.size());
   for (char32_t symbol : d.getAlphabet()) {
     if (find(p->alphabet.begin(), p->alphabet.end(), symbol) == p->alphabet.end()) {
       unitedAlphabet.push_front(symbol);
       unitedAlphabetSize++;
     }
   }
   vector<vector<size_t>> tTable(getNumberOfStates()+d.getNumberOfStates()+1, vector<size_t>(unitedAlphabetSize));
   valarray<bool> accepting(false, getNumberOfStates()+d.getNumberOfStates()+1);
   for (size_t q(0); q < getNumberOfStates(); q++) {
     size_t s(0);
     vector<size_t>& row = tTable[q];
     for (char32_t symbol : unitedAlphabet) {
       try {
         row[s] = delta(q, symbol);
       } catch (std::domain_error e) {
         row[s] = getNumberOfStates()+d.getNumberOfStates();
       }
       s++;
     }
     accepting[q] = isAccepting(q);
   }
   for (size_t q(0); q < d.getNumberOfStates(); q++) {
     size_t s(0);
     vector<size_t>& row = tTable[q+getNumberOfStates()];
     for (char32_t symbol : unitedAlphabet) {
       try {
         row[s] = getNumberOfStates()+d.delta(q, symbol);
       } catch (std::domain_error e) {
         row[s] = getNumberOfStates()+d.getNumberOfStates();
       }
       s++;
     }
     accepting[q+getNumberOfStates()] = d.isAccepting(q);
   }
   for (size_t s(0); s < unitedAlphabetSize; s++) {
     tTable[getNumberOfStates()+d.getNumberOfStates()][s] = getNumberOfStates()+d.getNumberOfStates();
   }
   return pImpl::indistinguishableStates(tTable, accepting)[0][getNumberOfStates()];
 }

◆ operator==() [2/2]

bool reg::dfa::operator== ( nfa const & n ) const

Tests whether this DFA accepts exactly the same language as another object.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 224 of file dfa.cpp.

                                        {
   return operator==(static_cast<dfa const&>(n));
 }

◆ subtract()

dfa::builder reg::dfa::subtract	(	dfa const &	d1,
		dfa const &	d2
	)

static

Creates a builder for a DFA accepting the set difference of the languages of two DFAs.

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

Parameters

d1	the first DFA
d2	the other DFA

Returns: builder for a DFA accepting all the words accepted by the first but not the other input DFA

Definition at line 481 of file dfa.cpp.

                                                      {
   builder b1(d1);
   for (auto symbol : d2.getAlphabet()) {
     b1.addSymbol(symbol);
   }
   return b1.complement().unite(d2).complement();
 }

◆ unite()

dfa::builder reg::dfa::unite	(	dfa const &	d1,
		dfa const &	d2
	)

static

Creates a builder for a DFA accepting the union of the languages of two DFAs.

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

Parameters

d1	the first DFA
d2	the other DFA

Returns: builder for a DFA accepting all the words accepted by any of the input DFAs

Definition at line 457 of file dfa.cpp.

                                                   {
   return builder(d1).unite(d2);
 }

Friends And Related Function Documentation

◆ findShortestUtf8Word

std::string findShortestUtf8Word ( dfa const & d )

friend

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

Definition at line 445 of file dfa.cpp.

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

◆ findShortestWord

std::u32string findShortestWord ( dfa const & d )

friend

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

Parameters

d the DFA

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

Exceptions

std::logic_error if the DFA doesn't accept any words

Definition at line 418 of file dfa.cpp.

                                          {
   auto const& p = d.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) {
         size_t reached = d.delta(stateWord.first, symbol);
         u32string shWord = stateWord.second + symbol;
         if (p->accepting[reached]) {
           return shWord;
         }
         if (shortestWords.find(reached) == shortestWords.end()) {
           shortestWords.emplace(reached, shWord);
         }
       }
     }
   }
   throw std::logic_error("This DFA doesn't accept any words!");
 }

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

Classes

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ dfa() [1/3]

◆ dfa() [2/3]

◆ dfa() [3/3]

Member Function Documentation

◆ complement()

◆ delta() [1/5]

◆ delta() [2/5]

◆ delta() [3/5]

◆ delta() [4/5]

◆ delta() [5/5]

◆ deltaHat() [1/4]

◆ deltaHat() [2/4]

◆ deltaHat() [3/4]

◆ deltaHat() [4/4]

◆ getAlphabet()

◆ getInitialState()

◆ getLabelOf()

◆ getNumberOfStates()

◆ getNumberOfSymbols()

◆ getShortestUtf8Word()

◆ getShortestWord()

◆ getStates()

◆ getUtf8Alphabet()

◆ intersect()

◆ isAccepting() [1/2]

◆ isAccepting() [2/2]

◆ operator nfa const &()

◆ operator!=() [1/2]

◆ operator!=() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==() [1/2]

◆ operator==() [2/2]

◆ subtract()

◆ unite()

Friends And Related Function Documentation

◆ findShortestUtf8Word

◆ findShortestWord