DFA.h

Go to the documentation of this file.

#pragma once

// These container hash the keys, therefore the average complexity is constant
#include <unordered_set>
// These container use a red-black tree, therefore the complexity is logarithmic
#include <map>
#include <vector>
#include <list>
#include <memory>

#include <string>
#include <sstream>

namespace gsjj {
    template<typename Sigma>
    class DFA {
    public:
        DFA(unsigned int initial, bool isAccepting = false) {
            m_states.insert(initial);
            m_initialState = initial;
            if (isAccepting) {
                m_acceptingStates.insert(initial);
            }
        }

        void addState(unsigned int state, bool isAccepting = false) {
            m_states.insert(state); // The check if the state is already in the set is automatically done in the insert function
            if (isAccepting) {
                m_acceptingStates.insert(state);
            }
        }

        void addTransition(unsigned int p, Sigma symbol, unsigned int q) {
            if (m_states.find(p) == m_states.end()) {
                std::ostringstream error;
                error << p << " is not known when adding the transition " << p << " --" << symbol << "--> " << q;
                throw std::out_of_range(error.str());
            }
            else if (m_states.find(q) == m_states.end()) {
                std::ostringstream error;
                error << q << " is not known when adding the transition " << p << " --" << symbol << "--> " << q;
                throw std::out_of_range(error.str());
            }

            m_transitions[p][symbol] = q;
        }

        bool isAccepted(const std::list<Sigma>& word) {
            unsigned int state = m_initialState;
            for (const Sigma &a : word) {
                auto itr = m_transitions.find(state);
                if (itr == m_transitions.end()) {
                    return false;
                }
                auto tran = itr->second.find(a);

                if (tran != itr->second.end()) {
                    state = tran->second;
                }
                else {
                    return false;
                }
            }

            return isAcceptingState(state);
        }

        bool isAccepted(const std::vector<Sigma> &word) {
            unsigned int state = m_initialState;
            for (const Sigma &a : word) {
                auto tran = m_transitions.find(std::make_pair(state, a));

                if (tran != m_transitions.end()) {
                    state = tran->second;
                }
                else {
                    return false;
                }
            }

            return isAcceptingState(state);
        }

        unsigned int getNumberOfStates() const {
            return m_states.size();
        }

        std::string to_dot() const {
            std::ostringstream dot;
            dot << "digraph deterministic_finite_automaton {\n";
            dot << "\trankdir=LR;\n";
            dot << "\tsize=\"8.5\"\n";
            process_states_dot(dot);
            process_transitions_dot(dot);
            dot << "}\n";
            return dot.str();
        }

        template<typename T>
        std::unique_ptr<DFA<T>> convert(const std::map<Sigma, T> &conversionMap) const {
            std::unique_ptr<DFA<T>> converted = std::make_unique<DFA<T>>(m_initialState, isAcceptingState(m_initialState));

            for (unsigned int state : m_states) {
                if (state != m_initialState) {
                    converted->addState(state, isAcceptingState(state));
                }
            }

            for (auto transition : m_transitions) {
                unsigned int p = transition.first;
                for (auto t : transition.second) {
                    T a = conversionMap.at(t.first);
                    unsigned int q = t.second;
                    converted->addTransition(p, a, q);
                }
            }

            return std::move(converted);
        }

        bool isAcceptingState(unsigned int state) const {
            return m_acceptingStates.find(state) != m_acceptingStates.end();
        }

        const std::unordered_set<unsigned int> &getStates() const {
            return m_states;
        }

        const std::unordered_set<unsigned int> &getAcceptingStates() const {
            return m_acceptingStates;
        }

        unsigned int getInitialState() const {
            return m_initialState;
        }

        const std::map<unsigned int, std::map<Sigma, unsigned int>> getTransitions() const {
            return m_transitions;
        }

        bool isState(unsigned int state) const {
            return m_states.find(state) != m_states.end();
        }

    private:
        std::unordered_set<unsigned int> m_states;
        unsigned int m_initialState;
        std::map<unsigned int, std::map<Sigma, unsigned int>> m_transitions;
        std::unordered_set<unsigned int> m_acceptingStates;

    private:
        void process_states_dot(std::ostringstream& dot) const {
            // We must add one state to create the arrow indicating the initial state
            dot << "\tnode [shape=none, label=\"\"] qi\n";
            for (int state : m_states) {
                dot << "\tnode [shape=";
                // Accepting states are double circled
                if (isAcceptingState(state)) {
                    dot << "doublecircle";
                }
                else {
                    dot << "circle";
                }

                dot << ", label=\"q" << state << "\"] q" << state << ";\n";
            }
        }

        void process_transitions_dot(std::ostringstream &dot) const {
            // The arrow indicating the initial state
            dot << "\tqi -> q" << m_initialState << ";\n";

            for (auto state : m_transitions) {
                unsigned int start = state.first;
                for (auto transition : state.second) {
                    Sigma symbol = transition.first;
                    unsigned int end = transition.second;
                    dot << "\tq" << start << " -> q" << end << " [label=\"" << symbol << "\"];\n";
                }
            }
        }
    };
}