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 &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 (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::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...

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

Constructor & Destructor Documentation

dfa() [1/4]

reg::dfa::dfa

(

)

Constructs a DFA accepting the empty language ∅.

Definition at line 107 of file dfa.cpp.

: p(new pImpl) {}

dfa() [2/4]

reg::dfa::dfa

(

dfa &

d

)

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

Definition at line 117 of file dfa.cpp.

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

dfa() [3/4]

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

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

dfa() [4/4]

reg::dfa::dfa

(

dfa::builder &

b

)

Constructs a DFA from a builder.

Definition at line 124 of file dfa.cpp.

: p(move(b.build().p)) {}

Member Function Documentation

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 223 of file dfa.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)
    );
    #else
    return SIZE_MAX;
    #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))
    );
    #else
    return SIZE_MAX-1;
    #endif
  }
  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 250 of file dfa.cpp.

                                                          {
  return delta(q, expression::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 261 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 269 of file dfa.cpp.

                                                           {
  return deltaHat(q, expression::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 287 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 278 of file dfa.cpp.

                                            {
  return p->labels[q];
}

getNumberOfStates()

size_t reg::dfa::getNumberOfStates

(

)

const

Counts this DFA's states.

Returns

the number of states this DFA has

Definition at line 305 of file dfa.cpp.

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

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

                                                 {
  return p->utf8Alphabet;
}

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

                                    {
  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 214 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 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 152 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) {
      #ifdef __EXCEPTIONS
      try {
        row[s] = delta(q, symbol);
      } catch (std::domain_error e) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      }
      #else
      size_t r(delta(q, symbol));
      if (r >= SIZE_MAX-1) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      } else {
        row[s] = r;
      }
      #endif
      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) {
      #ifdef __EXCEPTIONS
      try {
        row[s] = getNumberOfStates()+d.delta(q, symbol);
      } catch (std::domain_error e) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      }
      #else
      size_t r(delta(q, symbol));
      if (r >= SIZE_MAX-1) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      } else {
        row[s] = r;
      }
      #endif
      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()];
}

---

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

• dfa.h
• dfa.cpp