reg::dfa Class Reference

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

Constructor & Destructor Documentation

dfa() [1/5]

reg::dfa::dfa

(

)

Constructs a DFA accepting the empty language ∅.

Definition at line 126 of file dfa.cpp.

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

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

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

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

dfa() [5/5]

reg::dfa::dfa

(

dfa::builder &

b

)

Constructs a DFA from a builder.

Definition at line 146 of file dfa.cpp.

: dfa(b.build()) {}

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 485 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 227 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 245 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 254 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 266 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 275 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 287 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 295 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 307 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 312 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 351 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 335 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 327 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 364 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 369 of file dfa.cpp.

                                     {
  return getAlphabet().size();
}

getShortestUtf8Word()

string reg::dfa::getShortestUtf8Word

(

)

const

Deprecated:

Old way of accessing reg::findShortestUtf8Word.

Definition at line 322 of file dfa.cpp.

                                      {
  return findShortestUtf8Word(*this);
}

getShortestWord()

u32string reg::dfa::getShortestWord

(

)

const

Deprecated:

Old way of accessing reg::findShortestWord.

Definition at line 317 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 343 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 359 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 457 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 379 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 392 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!=()

bool reg::dfa::operator!=

(

const dfa &

d

)

const

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

Definition at line 217 of file dfa.cpp.

{return !operator==(d);}

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 149 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 158 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 173 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 469 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 445 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 433 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 406 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:

• dfa.h
• dfa.cpp