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 (nfa const &n)
	Constructs a DFA from an NFA via powerset construction. More...

	dfa (builder &b)
	Constructs a DFA from a builder. More...

dfa &	operator= (const dfa &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...

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

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

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

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

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

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

std::u32string	getShortestWord () const
	Searches the shortest UTF-32-encoded word accepted by this DFA. 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::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
	Counts this DFA's states. More...

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

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 26 of file dfa.h.

Constructor & Destructor Documentation

◆ dfa() [1/5]

reg::dfa::dfa ( )

Constructs a DFA accepting the empty language ∅.

Definition at line 104 of file dfa.cpp.

104 : p(new pImpl) {}

◆ dfa() [2/5]

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

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

Definition at line 114 of file dfa.cpp.

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

◆ dfa() [3/5]

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

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

◆ dfa() [4/5]

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

Constructs a DFA from an NFA via powerset construction.

Definition at line 121 of file dfa.cpp.

121 : dfa(builder(n).build()) {}

reg::dfa::dfa

dfa()

Constructs a DFA accepting the empty language ∅.

Definition: dfa.cpp:104

◆ dfa() [5/5]

reg::dfa::dfa ( dfa::builder & b )

Constructs a DFA from a builder.

Definition at line 124 of file dfa.cpp.

124 : dfa(b.build()) {}

reg::dfa::dfa

dfa()

Constructs a DFA accepting the empty language ∅.

Definition: dfa.cpp:104

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

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

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

◆ delta() [1/2]

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

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

Parameters

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

Returns: the reached state's index

Definition at line 203 of file dfa.cpp.

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

◆ delta() [2/2]

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

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

◆ deltaHat() [1/2]

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

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

Definition at line 229 of file dfa.cpp.

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

◆ deltaHat() [2/2]

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

                                                {
   return p->alphabet;
 }

◆ getLabelOf()

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

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

◆ getNumberOfStates()

size_t reg::dfa::getNumberOfStates ( ) const

Counts this DFA's states.

Returns: the number of states this DFA has

Definition at line 310 of file dfa.cpp.

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

◆ getShortestUtf8Word()

string reg::dfa::getShortestUtf8Word ( ) const

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

Definition at line 277 of file dfa.cpp.

                                       {
   return converter.to_bytes(getShortestWord());
 }

◆ getShortestWord()

u32string reg::dfa::getShortestWord ( ) const

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

LOOPS INFINITELY FOR DFA WITH AN EMPTY LANGUAGE!

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

dfa empty();
if (myDfa != empty) {
  myDfa.getShortestWord();
}

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

Definition at line 254 of file dfa.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) {
         size_t reached = 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);
         }
       }
     }
   }
 }

◆ 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 302 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 348 of file dfa.cpp.

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

◆ isAccepting()

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

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

Parameters

q	the state's index (< getNumberOfStates)

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

Definition at line 319 of file dfa.cpp.

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

◆ operator!=()

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

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

Definition at line 195 of file dfa.cpp.

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

reg::dfa::operator==

bool operator==(const dfa &d) const

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

Definition: dfa.cpp:151

◆ operator=() [1/2]

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

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

Definition at line 127 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 136 of file dfa.cpp.

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

◆ operator==()

bool reg::dfa::operator== ( const dfa & 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 151 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()];
 }

◆ 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 360 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 336 of file dfa.cpp.

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

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

Classes

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ dfa() [1/5]

◆ dfa() [2/5]

◆ dfa() [3/5]

◆ dfa() [4/5]

◆ dfa() [5/5]

Member Function Documentation

◆ complement()

◆ delta() [1/2]

◆ delta() [2/2]

◆ deltaHat() [1/2]

◆ deltaHat() [2/2]

◆ getAlphabet()

◆ getLabelOf()

◆ getNumberOfStates()

◆ getShortestUtf8Word()

◆ getShortestWord()

◆ getUtf8Alphabet()

◆ intersect()

◆ isAccepting()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ subtract()

◆ unite()