reg Namespace Reference

Where this library lives. More...

Classes
class	dfa
	Represents deterministic finite automata. More...
class	expression
	Represents formal regular expressions. More...
class	gnfa
	Represents generalized nondeterministic finite automata. More...
class	nfa
	Represents nondeterministic finite automata with ε-moves. More...

Typedefs
using	Dtransitionmap = unordered_map< string, unordered_map< char32_t, string > >
	Shorthand for the map from state name and transition symbol to target state. More...
using	Ntransitionmap = unordered_map< string, unordered_map< char32_t, unordered_set< string > >>
	Shorthand for the map from state name and transition symbol to set of target states. More...

Functions
u32string	findShortestWord (dfa const &d)
	Searches the shortest UTF-32-encoded word accepted by a given DFA. More...
string	findShortestUtf8Word (dfa const &d)
	Same as above for a UTF-8-encoded word. More...
template<class C , class T >
size_t	index_of (C const &container, T const &element)
	Basically Java's List interface's indexOf, but as a non-member function and returning the container's size upon failure. More...
u32string	findShortestWord (nfa const &n)
	Searches the shortest UTF-32-encoded word accepted by a given NFA. More...
string	findShortestUtf8Word (nfa const &n)
	Same as above for a UTF-8-encoded word. More...

Variables
std::wstring_convert< std::codecvt_utf8< char32_t >, char32_t >	converter
	Converts between UTF-8-encoded and UTF-32-encoded strings. More...

Detailed Description

Where this library lives.

Typedef Documentation

Dtransitionmap

using reg::Dtransitionmap = typedef unordered_map<string, unordered_map<char32_t, string> >

Shorthand for the map from state name and transition symbol to target state.

Definition at line 490 of file dfa.cpp.

Ntransitionmap

using reg::Ntransitionmap = typedef unordered_map<string, unordered_map<char32_t, unordered_set<string> >>

Shorthand for the map from state name and transition symbol to set of target states.

Definition at line 655 of file nfa.cpp.

Function Documentation

findShortestUtf8Word() [1/2]

std::string reg::findShortestUtf8Word

(

dfa const &

d

)

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

Definition at line 433 of file dfa.cpp.

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

findShortestUtf8Word() [2/2]

std::string reg::findShortestUtf8Word

(

nfa const &

n

)

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

Definition at line 564 of file nfa.cpp.

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

findShortestWord() [1/2]

std::u32string reg::findShortestWord

(

dfa const &

d

)

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!");
}

findShortestWord() [2/2]

std::u32string reg::findShortestWord

(

nfa const &

n

)

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

Parameters

n

the NFA

Returns

the shortest word leading to one of the NFA's accept states

Exceptions

std::logic_error

if the NFA doesn't accept any words

Definition at line 535 of file nfa.cpp.

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

index_of()

template<class C , class T >

size_t reg::index_of	(	C const &	container,
		T const &	element
	)

Basically Java's List interface's indexOf, but as a non-member function and returning the container's size upon failure.

Parameters

container	the container to search through
element	the element to find the index of

Returns

the first i with container.begin()[i]==element or container.size() if none is found

Definition at line 120 of file dfa.h.

                                                                                {
  static_assert(std::is_same<typename C::value_type,T>::value, "C must be a container with T as value_type.");
  return static_cast<size_t>(std::distance(container.begin(), std::find(container.begin(), container.end(), element)));
}

Variable Documentation

converter

std::wstring_convert< std::codecvt_utf8< char32_t >, char32_t > reg::converter

Converts between UTF-8-encoded and UTF-32-encoded strings.

Definition at line 1060 of file dfa.cpp.