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

Friends
class	expression

Detailed Description

Represents generalized nondeterministic finite automata.

Definition at line 18 of file gnfa.h.

Constructor & Destructor Documentation

gnfa() [1/4]

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 125 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 = unique_ptr<pImpl>(new pImpl(transitions, n.getLabelOf(0), acceptingStates));
}

gnfa() [2/4]

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 158 of file gnfa.cpp.

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

gnfa() [3/4]

reg::gnfa::gnfa

(

gnfa const &

n

)

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

Definition at line 378 of file gnfa.cpp.

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

gnfa() [4/4]

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 382 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 321 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 188 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 193 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(entry.first);
    }
  }
  return active;
}

getInitialState()

string const & reg::gnfa::getInitialState

(

)

const

Reveals the name of this GNFA's initial state.

Definition at line 183 of file gnfa.cpp.

                                          {
  return p->initial;
}

getSplittableTransitions()

vector< pair< string const &, 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 213 of file gnfa.cpp.

                                                                                {
  vector<pair<string const&, 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 204 of file gnfa.cpp.

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

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 385 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 394 of file gnfa.cpp.

                              {
  if (this != &n) {
    p.reset(new pImpl);
    p.swap(n.p);
  }
  return *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 370 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 349 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 300 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 236 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