reg::gnfa Class Reference

Represents generalized nondeterministic finite automata. More...

#include <gnfa.h>

Classes
struct	pImpl
	Private implementation details of GNFAs. More...

Public Member Functions
	gnfa (dfa const &d)
	Constructs a GNFA with the same states and transitions as a given DFA. More...
	gnfa (nfa const &n)
	Constructs a GNFA with the same states and transitions as a given NFA. More...
	gnfa (expression::exptr r)
	Constructs a GNFA with only one transition. More...
	gnfa (gnfa const &n)
	Copy-constructs a GNFA by copying another one's private implementation object. More...
	gnfa (gnfa &&n)
	Move-constructs a GNFA by stealing another one's private implementation object. More...
gnfa &	operator= (gnfa const &n)
	Copy-assigns this GNFA by copying another one's private implementation object. More...
gnfa &	operator= (gnfa &&n)
	Move-assigns this GNFA by stealing another one's private implementation object. More...
	operator nfa const & () const
	Returns an NFA accepting the same language as this GNFA. More...
bool	operator== (nfa const &n) const
	Checks whether this RE describes the same regular language as another object. More...
bool	operator!= (nfa const &n) const
	Checks whether this RE describes a different regular language than another object. More...
std::string const &	getInitialState () const
	Reveals the name of this GNFA's initial state. More...
std::string const &	getAcceptingState () const
	Reveals the name of this GNFA's accept state. More...
std::vector< std::reference_wrapper< std::string const > >	getActiveStates () const
	Reveals the names of this GNFA's non-initial, non-accepting states. More...
expression::exptr	getTransition (std::string const &qLabel, std::string const &pLabel) const
	Extracts the RE labelling the transition between two states. More...
std::vector< std::pair< std::reference_wrapper< std::string const >, std::reference_wrapper< std::string const > > >	getSplittableTransitions () const
	Reveals this GNFA's splittable transitions. More...
std::vector< std::reference_wrapper< std::string const > >	splitTransition (std::string const &qLabel, std::string const &pLabel)
	Splits a transition between two states, adding new states if needed. More...
nfa	splitAllTransitions ()
	Splits all transitions until only ∅, ε, and symbol REs remain and builds the resulting NFA. More...
void	bypassTransition (std::string const &qLabel, std::string const &pLabel)
	Removes a transition between two states and replaces it with equivalent ones, bypassing its beginning state. More...
void	ripState (std::string const &qLabel)
	Removes a state, bypassing all its outgoing transitions. More...
expression::exptr	ripAllStates ()
	Removes all active states, constructing an RE semantically equivalent to this GNFA. More...

Detailed Description

Represents generalized nondeterministic finite automata.

Definition at line 17 of file gnfa.h.

Constructor & Destructor Documentation

gnfa() [1/5]

reg::gnfa::gnfa

(

dfa const &

d

)

Constructs a GNFA with the same states and transitions as a given DFA.

The following changes are applied upon conversion:

• Add a new and uniquely named initial state and connect it via an ε-transition to the DFA's start state.
• Add a new and uniquely named accept state and connect the DFA's accept states to it via ε-transitions.
• Disregard any information about initial or accept states of the DFA.
• Replace any transition with a corresponding symbol expression.
• Replace transitions with more than one label with alternations of these labels.

  Parameters

  d	the DFA to base the GNFA on

Definition at line 120 of file gnfa.cpp.

                       {
  unordered_map<string,unordered_map<string,expression::exptr>> transitions(d.getNumberOfStates()+2);
  forward_list<reference_wrapper<string const>> acceptingStates;
  for (size_t qi(0); qi < d.getNumberOfStates(); qi++) {
    auto const& qLabel = d.getLabelOf(qi);
    auto& entry = transitions[qLabel];
    if (d.isAccepting(qi)) {
      acceptingStates.push_front(qLabel);
    }
    for (size_t si(0); si < d.getNumberOfSymbols(); si++) {
      char32_t symbol = d.getAlphabet()[si];
      size_t pi = d.delta(qi, si);
      auto& dest = entry[d.getStates()[pi]];
      if (!dest) {
        dest = expression::spawnSymbol(symbol);
      } else {
        dest = expression::spawnAlternation(dest, expression::spawnSymbol(symbol));
      }
    }
  }
  p = std::make_unique<pImpl>(transitions, d.getLabelOf(0), acceptingStates, new nfa(d));
}

gnfa() [2/5]

reg::gnfa::gnfa

(

nfa const &

n

)

Constructs a GNFA with the same states and transitions as a given NFA.

The following changes are applied upon conversion:

• Add a new and uniquely named initial state and connect it via an ε-transition to the NFA's start state.
• Add a new and uniquely named accept state and connect the NFA's accept states to it via ε-transitions.
• Disregard any information about initial or accept states of the NFA.
• Replace any transition with a corresponding symbol expression.
• Replace transitions with more than one label with alternations of these labels.

  Parameters

  n	the NFA to base the GNFA on

Definition at line 153 of file gnfa.cpp.

                       {
  unordered_map<string,unordered_map<string,expression::exptr>> transitions(n.getNumberOfStates()+2);
  forward_list<reference_wrapper<string const>> acceptingStates;
  for (size_t qi(0); qi < n.getNumberOfStates(); qi++) {
    auto const& qLabel = n.getLabelOf(qi);
    auto& entry = transitions[qLabel];
    if (n.isAccepting(qi)) {
      acceptingStates.push_front(qLabel);
    }
    for (auto const& symbol : n.getAlphabet()) {
      auto& pSet = n.delta(qi, symbol);
      for (size_t pi(0); pi < pSet.size(); pi++) {
        if (pSet[pi]) {
          auto& dest = entry[n.getLabelOf(pi)];
          if (!dest) {
            dest = expression::spawnSymbol(symbol);
          } else {
            dest = expression::spawnAlternation(dest, expression::spawnSymbol(symbol));
          }
        }
      }
    }
  }
  p = std::make_unique<pImpl>(transitions, n.getLabelOf(0), acceptingStates, new nfa(n));
}

gnfa() [3/5]

reg::gnfa::gnfa

(

expression::exptr

r

)

Constructs a GNFA with only one transition.

The GNFA will have only two states: the initial and the accept state and a transition with the given label leading from the former to the latter.

Parameters

r	the transition's RE

Definition at line 185 of file gnfa.cpp.

                            : p(new pImpl) {
  p->transitions[p->initial][p->accepting] = r;
}

gnfa() [4/5]

reg::gnfa::gnfa

(

gnfa const &

n

)

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

Definition at line 401 of file gnfa.cpp.

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

gnfa() [5/5]

reg::gnfa::gnfa

(

gnfa &&

n

)

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

The other GNFA will be semantically equivalent to the ∅ RE afterwards.

Definition at line 405 of file gnfa.cpp.

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

Member Function Documentation

bypassTransition()

void reg::gnfa::bypassTransition	(	std::string const &	qLabel,
		std::string const &	pLabel
	)

Removes a transition between two states and replaces it with equivalent ones, bypassing its beginning state.

Definition at line 345 of file gnfa.cpp.

                                                                      {
  auto const& re = p->getTransition(qLabel, pLabel);
  if (re == expression::spawnEmptySet()) {
    return;
  }
  auto const& selfRe = p->getTransition(qLabel, qLabel);
  for (auto const& from : p->transitions) {
    if (from.first != qLabel) {
      auto to = from.second.find(qLabel);
      if (to != from.second.end() && to->second) {
        p->addTransition(
            from.first,
            pLabel,
            expression::spawnConcatenation(
                to->second,
                expression::spawnConcatenation(
                    expression::spawnKleene(selfRe),
                    re
                )
            )
        );
      }
    }
  }
  p->transitions[qLabel].erase(pLabel);
}

getAcceptingState()

string const & reg::gnfa::getAcceptingState

(

)

const

Reveals the name of this GNFA's accept state.

Definition at line 215 of file gnfa.cpp.

                                            {
  return p->accepting;
}

getActiveStates()

vector< reference_wrapper< string const > > reg::gnfa::getActiveStates

(

)

const

Reveals the names of this GNFA's non-initial, non-accepting states.

Definition at line 220 of file gnfa.cpp.

                                                                    {
  vector<reference_wrapper<string const>> active;
  for (auto const& entry : p->transitions) {
    if (entry.first != p->initial && entry.first != p->accepting) {
      active.push_back(std::cref(entry.first));
    }
  }
  return active;
}

getInitialState()

string const & reg::gnfa::getInitialState

(

)

const

Reveals the name of this GNFA's initial state.

Definition at line 210 of file gnfa.cpp.

                                          {
  return p->initial;
}

getSplittableTransitions()

vector< pair< reference_wrapper< string const >, reference_wrapper< string const > > > reg::gnfa::getSplittableTransitions

(

)

const

Reveals this GNFA's splittable transitions.

Returns

a vector of edges with transition labels with expression::size > 1

Definition at line 239 of file gnfa.cpp.

                                                                                                                    {
  vector<pair<reference_wrapper<string const>, reference_wrapper<string const>>> splittable;
  splittable.reserve(p->transitions.size()*p->transitions.size());
  for (pair<string const, unordered_map<string, expression::exptr>> const& from : p->transitions) {
    for (pair<string const, expression::exptr> const& to : from.second) {
      if (to.second && to.second->getOperation() > expression::operation::symbol) {
        splittable.push_back(std::make_pair(std::ref(from.first), std::ref(to.first)));
      }
    }
  }
  splittable.shrink_to_fit();
  return splittable;
}

getTransition()

expression::exptr reg::gnfa::getTransition	(	std::string const &	qLabel,
		std::string const &	pLabel
	)		const

Extracts the RE labelling the transition between two states.

Definition at line 231 of file gnfa.cpp.

                                                                                    {
  return p->getTransition(qLabel, pLabel);
}

operator nfa const &()

reg::gnfa::operator nfa const &

(

)

const

Returns an NFA accepting the same language as this GNFA.

operator!=()

bool reg::gnfa::operator!=

(

nfa const &

other

)

const

Checks whether this RE describes a different regular language than another object.

Returns

false if this RE's language is exactly the same as the other object's, true else

Definition at line 428 of file gnfa.cpp.

                                            {
  return !operator==(other);
}

operator=() [1/2]

gnfa & reg::gnfa::operator=

(

gnfa const &

n

)

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

Definition at line 433 of file gnfa.cpp.

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

operator=() [2/2]

gnfa & reg::gnfa::operator=

(

gnfa &&

n

)

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

The other GNFA will be semantically equivalent to the ∅ RE afterwards.

Definition at line 442 of file gnfa.cpp.

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

operator==()

bool reg::gnfa::operator==

(

nfa const &

other

)

const

Checks whether this RE describes the same regular language as another object.

Returns

true if this RE's language is exactly the same as the other object's, false else

Definition at line 420 of file gnfa.cpp.

                                            {
  return other.operator==(*this);
}

ripAllStates()

expression::exptr reg::gnfa::ripAllStates

(

)

Removes all active states, constructing an RE semantically equivalent to this GNFA.

Returns

exptr to the RE labelling the remaining transition between initial state and accept state

Definition at line 393 of file gnfa.cpp.

                                   {
  for (auto const& rippable : getActiveStates()) {
    ripState(rippable);
  }
  return getTransition(getInitialState(), getAcceptingState());
}

ripState()

void reg::gnfa::ripState

(

std::string const &

qLabel

)

Removes a state, bypassing all its outgoing transitions.

Definition at line 373 of file gnfa.cpp.

                                        {
  forward_list<reference_wrapper<string const>> right;
  for (auto const& to : p->transitions[qLabel]) {
    right.push_front(to.first);
  }
  for (auto const& to : right) {
    if (to.get() != qLabel) {
      bypassTransition(qLabel, to);
    }
  }
  for (auto& from : p->transitions) {
    from.second.erase(qLabel);
  }
  p->transitions.erase(qLabel);
}

splitAllTransitions()

nfa reg::gnfa::splitAllTransitions

(

)

Splits all transitions until only ∅, ε, and symbol REs remain and builds the resulting NFA.

When building the NFA, transitions with symbol and ε REs are replaced with corresponding symbol transitions and transitions with ∅ REs will be ignored.

Returns

the NFA with equivalent states and transitions to the GNFA's after splitting

Definition at line 324 of file gnfa.cpp.

                              {
  for (auto splittable = getSplittableTransitions(); !splittable.empty(); splittable = getSplittableTransitions()) {
    for (auto const& nodes : splittable) {
      splitTransition(nodes.first, nodes.second);
    }
  }
  nfa::builder b;
  auto const& empty = expression::spawnEmptySet();
  for (auto const& from : p->transitions) {
    for (auto const& to : from.second) {
      if (to.second != empty) {
        b.addTransition(from.first, to.first, to.second->extractSymbol());
      }
    }
  }
  b.makeInitial(p->initial);
  b.setAccepting(p->accepting, true);
  return b.build();
}

splitTransition()

vector< reference_wrapper< string const > > reg::gnfa::splitTransition	(	std::string const &	qLabel,
		std::string const &	pLabel
	)

Splits a transition between two states, adding new states if needed.

The transition will be broken up into pieces, according to the semantics of its label.

Parameters

qLabel	the beginning state of the transition
pLabel	the end state of the transition

Returns

a vector of states that were newly added while splitting the transition

Definition at line 261 of file gnfa.cpp.

                                                                                                        {
  vector<reference_wrapper<string const>> newStates;
  auto const& re = p->getTransition(qLabel, pLabel);
  switch (re->getOperation()) {
    case expression::operation::alternation : {
      auto sub1 = *(re->begin());
      auto sub2 = *(re->begin()+1);
      p->transitions[qLabel][pLabel] = expression::spawnEmptySet();
      newStates.reserve(4);
      for (size_t i(0); i < 4; i++) {
        newStates.push_back(p->generateState());
      }
      auto const& epsilon = expression::spawnEmptyString();
      p->transitions[qLabel][newStates[0]] = epsilon;
      p->transitions[newStates[0]][newStates[1]] = sub1;
      p->transitions[newStates[1]][pLabel] = epsilon;
      p->transitions[qLabel][newStates[2]] = epsilon;
      p->transitions[newStates[2]][newStates[3]] = sub2;
      p->transitions[newStates[3]][pLabel] = epsilon;
      break;
    }
    case expression::operation::concatenation : {
      auto sub1 = *(re->begin());
      auto sub2 = *(re->begin()+1);
      p->transitions[qLabel][pLabel] = expression::spawnEmptySet();
      newStates.reserve(2);
      for (size_t i(0); i < 2; i++) {
        newStates.push_back(p->generateState());
      }
      p->transitions[qLabel][newStates[0]] = sub1;
      p->transitions[newStates[0]][newStates[1]] = expression::spawnEmptyString();
      p->transitions[newStates[1]][pLabel] = sub2;
      break;
    }
    case expression::operation::kleene : {
      auto sub = *(re->begin());
      auto const& epsilon = expression::spawnEmptyString();
      p->transitions[qLabel][pLabel] = epsilon;
      newStates.reserve(2);
      for (size_t i(0); i < 2; i++) {
        newStates.push_back(p->generateState());
      }
      p->transitions[qLabel][newStates[0]] = epsilon;
      p->transitions[newStates[1]][pLabel] = epsilon;
      p->transitions[newStates[1]][newStates[0]] = epsilon;
      p->transitions[newStates[0]][newStates[1]] = sub;
      break;
    }
    case expression::operation::symbol :
    case expression::operation::empty :
    ;
  }
  return newStates;
}

---

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

• gnfa.h
• gnfa.cpp